On Complementation of Nondeterministic Finite Automata without Full Determinization (Technical Report)
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913940756234240 |
|---|---|
| author | Holík, Lukáš Lengál, Ondřej Major, Juraj Štěpková, Adéla Strejček, Jan |
| author_facet | Holík, Lukáš Lengál, Ondřej Major, Juraj Štěpková, Adéla Strejček, Jan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_03439 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Complementation of Nondeterministic Finite Automata without Full Determinization (Technical Report) Holík, Lukáš Lengál, Ondřej Major, Juraj Štěpková, Adéla Strejček, Jan Formal Languages and Automata Theory Logic in Computer Science 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. |
| title | On Complementation of Nondeterministic Finite Automata without Full Determinization (Technical Report) |
| topic | Formal Languages and Automata Theory Logic in Computer Science |
| url | https://arxiv.org/abs/2507.03439 |