Publication Details

On Complementation of Nondeterministic Finite Automata without Full Determinization

HOLíK Lukáš, LENGáL Ondřej, MAJOR Juraj, STREJčEK Jan and ŠTěPKOVá Adéla. On Complementation of Nondeterministic Finite Automata without Full Determinization. In: 25th International Symposium on Fundamentals of Computation Theory. Wroclaw: Springer Verlag, 2025. ISSN 0302-9743.
Czech title
Komplementace nedeterministického konečného automatu bez plné determinizace
Type
conference paper
Language
english
Authors
Holík Lukáš, doc. Mgr., Ph.D. (DITS FIT BUT)
Lengál Ondřej, Ing., Ph.D. (DITS FIT BUT)
Major Juraj (MUNI)
Strejček Jan, prof. RNDr., Ph.D. (FI MUNI)
Štěpková Adéla (MUNI)
Keywords

nondeterministic finite automaton,NFA,complementation, determinization,component

Abstract

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.

Published
2025 (in print)
Journal
Lecture Notes in Computer Science, ISSN 0302-9743
Proceedings
25th International Symposium on Fundamentals of Computation Theory
Conference
25th International Symposium on Fundamentals of Computation Theory --- FCT'25, Wroclaw, PL
Publisher
Springer Verlag
Place
Wroclaw, PL
BibTeX 
@INPROCEEDINGS{FITPUB13549,
   author = "Luk\'{a}\v{s} Hol\'{i}k and Ond\v{r}ej Leng\'{a}l and Juraj Major and Jan Strej\v{c}ek and Ad\'{e}la \v{S}t\v{e}pkov\'{a}",
   title = "On Complementation of Nondeterministic Finite Automata without Full Determinization",
   booktitle = "25th International Symposium on Fundamentals of Computation Theory",
   journal = "Lecture Notes in Computer Science",
   year = 2025,
   location = "Wroclaw, PL",
   publisher = "Springer Verlag",
   ISSN = "0302-9743",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/13549"
}
Back to top