Result Details
On Complementation of Nondeterministic Finite Automata without Full Determinization
Lengál Ondřej, doc. Ing., Ph.D., DITS (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, BUT, Vnitřní projekty VUT, FIT-S-23-8151, start: 2023-03-01, end: 2026-02-28, running
Representing Boolean Functions by a Self-Adaptable Data Structure, GACR, Standardní projekty, GA23-07565S, start: 2023-01-01, end: 2025-12-31, completed
String Constraints for Security Analysis, GACR, Standardní projekty, 25-17934S, start: 2025-08-01, end: 2028-07-31, running