Detail výsledku
On Complementation of Nondeterministic Finite Automata without Full Determinization
Lengál Ondřej, doc. Ing., Ph.D., UITS (FIT)
Major Juraj
Štěpková Adéla
Strejček Jan
Complementation of finite automata is a basic operation used in numerous
applications. The standard way to complement a nondeterministic finite automaton
(NFA) is to transform it into an equivalent deterministic finite automaton (DFA)
and complement the DFA. The DFA can, however, be exponentially larger than the
corresponding NFA. In this paper, we study several alternative approaches to
complementation, which are based either on reverse powerset construction or on
two novel constructions that exploit a commonly occurring structure of NFAs. Our
experiment on a large data set shows that using a different than the classical
approach can, in many cases, yield significantly smaller complements.
nondeterministic finite automaton,NFA,complementation, determinization,component
@inproceedings{BUT198409,
author="Lukáš {Holík} and Ondřej {Lengál} and {} and {} and {} and {} and {} and {}",
title="On Complementation of Nondeterministic Finite Automata without Full Determinization",
booktitle="25th International Symposium on Fundamentals of Computation Theory",
year="2025",
journal="Lecture Notes in Computer Science",
volume="16106",
pages="221--237",
publisher="Springer Verlag",
address="Wroclaw",
doi="10.1007/978-3-032-04700-7\{_}17",
isbn="978-3-032-04700-7",
issn="0302-9743",
url="https://link.springer.com/chapter/10.1007/978-3-032-04700-7_17"
}Reliable, Secure, and Intelligent Computer Systems, VUT, Vnitřní projekty VUT, FIT-S-23-8151, zahájení: 2023-03-01, ukončení: 2026-02-28, řešení
Reprezentace Booleovských funkcí pomocí adaptabilní datové struktury, GAČR, Standardní projekty, GA23-07565S, zahájení: 2023-01-01, ukončení: 2025-12-31, ukončen
Řetězcová omezení pro analýzu bezpečnosti, GAČR, Standardní projekty, 25-17934S, zahájení: 2025-08-01, ukončení: 2028-07-31, řešení