On Complementation of Nondeterministic Finite Automata without Full Determinization (Technical Report)

Lukáš Holík, Ondřej Lengál, Juraj Major, Adéla Štěpková, Jan Strejček · 2025

Read On Complementation of Nondeterministic Finite Automata without Full Determinization (Technical Report) by Lukáš Holík, Ondřej Lengál, Juraj Major, Adéla Štěpková, Jan Strejček (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-03439.txt.

Description

Lukas Holik and co-authors look for cheaper ways to flip a finite automaton so it accepts exactly the strings it once rejected. The standard route first makes the machine deterministic, but that step can blow it up to a huge size. Their 2025 technical report tests other routes on a large data set.

Some options run the classic subset build in reverse. Two fresh options exploit a structure that many real machines share. In many test cases, these routes gave much smaller flipped machines than the classic path. Smaller complements matter because the operation sits inside many checking and analysis tools. The report offers practical guidance on when to skip full determinization.

Catalog record

CREATORLukáš Holík, Ondřej Lengál, Juraj Major, Adéla Štěpková, Jan Strejček
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE21 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-03439

Browse the full library · About the Tower of Babel