Lower Bounds for the Transition Complexity of NFAs
From MaRDI portal
Publication:5756712
DOI10.1007/11821069_28zbMath1132.68441OpenAlexW1620393779MaRDI QIDQ5756712
Michael Domaratzki, Kai Salomaa
Publication date: 5 September 2007
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11821069_28
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (3)
On the average state and transition complexity of finite languages ⋮ Lower bounds for the transition complexity of NFAs ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
This page was built for publication: Lower Bounds for the Transition Complexity of NFAs
