Publication Details
On Complementation of Nondeterministic Finite Automata without Full Determinization
Lengál Ondřej, Ing., Ph.D. (DITS)
ŠTĚPKOVÁ, A.
MAJOR, J.
Strejček Jan, prof. RNDr., Ph.D.
nondeterministic finite automaton,NFA,complementation, determinization,component
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.
@inproceedings{BUT198409,
author="HOLÍK, L. and LENGÁL, O. and ŠTĚPKOVÁ, A. and MAJOR, J. and STREJČEK, J.",
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",
publisher="Springer Verlag",
address="Wroclaw",
issn="0302-9743"
}