On Complementation of Nondeterministic Finite Automata without Full Determinization
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F26%3A0198409" target="_blank" >RIV/00216305:26230/26:0198409 - isvavai.cz</a>
Result on the web
<a href="https://link.springer.com/chapter/10.1007/978-3-032-04700-7_17" target="_blank" >https://link.springer.com/chapter/10.1007/978-3-032-04700-7_17</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-032-04700-7_17" target="_blank" >10.1007/978-3-032-04700-7_17</a>
Alternative languages
Result language
angličtina
Original language name
On Complementation of Nondeterministic Finite Automata without Full Determinization
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
O - Miscellaneous
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů