On Complementation of Nondeterministic Finite Automata Without
Full Determinization

D 2026

On Complementation of Nondeterministic Finite Automata Without Full Determinization

HOLÍK, Lukáš; Ondřej LENGÁL; Juraj MAJOR; Adéla ŠTĚPKOVÁ; Jan STREJČEK et al.

Základní údaje

Originální název

On Complementation of Nondeterministic Finite Automata Without Full Determinization

Autoři

HOLÍK, Lukáš; Ondřej LENGÁL; Juraj MAJOR; Adéla ŠTĚPKOVÁ a Jan STREJČEK

Vydání

Cham (Švýcarsko), Fundamentals of Computation Theory - 25th International Symposium, FCT 2025, Wrocław, Poland, September 15-17, 2025, Proceedings, od s. 221-237, 17 s. 2026

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

URL

Impakt faktor

Impact factor: 0.402 v roce 2005

Označené pro přenos do RIV

Ano

Organizační jednotka

Fakulta informatiky

ISBN

978-3-032-04699-4

ISSN

Klíčová slova anglicky

finite automata; complementation; nondeterministic finite automata; determinization

Štítky

automata, AVELAB, core_B, firank_B

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 1. 4. 2026 11:09, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.

Návaznosti

MUNI/A/1600/2024, interní kód MU

Název: Modelování, analýza a verifikace (2025)

Investor: Masarykova univerzita, Modelování, analýza a verifikace (2025)

101087529, interní kód MU

Název: Cyber-security Excellence Hub in Estonia and South Moravia (CHESS)

Investor: Evropská unie, Cyber-security Excellence Hub in Estonia and South Moravia (CHESS), Rozšiřování účasti a posílení ERA

Citovat

HOLÍK, Lukáš; Ondřej LENGÁL; Juraj MAJOR; Adéla ŠTĚPKOVÁ a Jan STREJČEK. On Complementation of Nondeterministic Finite Automata Without Full Determinization. Online. In Artur Jeż, Jan Otop. Fundamentals of Computation Theory - 25th International Symposium, FCT 2025, Wrocław, Poland, September 15-17, 2025, Proceedings. Cham (Švýcarsko): Springer, 2026, s. 221-237. ISBN 978-3-032-04699-4. Dostupné z: https://doi.org/10.1007/978-3-032-04700-7_17.

@inproceedings{2520901,
   author = {Holík, Lukáš and Lengál, Ondřej and Major, Juraj and Štěpková, Adéla and Strejček, Jan},
   address = {Cham (Švýcarsko)},
   booktitle = {Fundamentals of Computation Theory - 25th International Symposium, FCT 2025, Wrocław, Poland, September 15-17, 2025, Proceedings},
   doi = {https://doi.org/10.1007/978-3-032-04700-7_17},
   editor = {Artur Jeż, Jan Otop},
   keywords = {finite automata; complementation; nondeterministic finite automata; determinization},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Cham (Švýcarsko)},
   isbn = {978-3-032-04699-4},
   pages = {221-237},
   publisher = {Springer},
   title = {On Complementation of Nondeterministic Finite Automata Without Full Determinization},
   url = {https://link.springer.com/chapter/10.1007/978-3-032-04700-7_17},
   year = {2026}
}

TY  - CONF
ID  - 2520901
AU  - Holík, Lukáš - Lengál, Ondřej - Major, Juraj - Štěpková, Adéla - Strejček, Jan
PY  - 2026
TI  - On Complementation of Nondeterministic Finite Automata Without Full Determinization
PB  - Springer
CY  - Cham (Švýcarsko)
SN  - 9783032046994
KW  - finite automata
KW  - complementation
KW  - nondeterministic finite automata
KW  - determinization
UR  - https://link.springer.com/chapter/10.1007/978-3-032-04700-7_17
N2  - 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.
ER  -

HOLÍK, Lukáš; Ondřej LENGÁL; Juraj MAJOR; Adéla ŠTĚPKOVÁ a Jan STREJČEK. On Complementation of Nondeterministic Finite Automata Without Full Determinization. Online. In Artur Je\.z, Jan Otop. \textit{Fundamentals of Computation Theory - 25th International Symposium, FCT 2025, Wrocław, Poland, September 15-17, 2025, Proceedings}. Cham (Švýcarsko): Springer, 2026, s.~221-237. ISBN~978-3-032-04699-4. Dostupné z: https://doi.org/10.1007/978-3-032-04700-7\_{}17.

Přehled o publikaci