Lower Bounds for the Transition Complexity of NFAs

DOI10.1007/11821069_28MaRDI QIDQ5756712zbMATH OpenOpenAlexFDO

Authors 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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

Recommendations

• Lower bounds for the transition complexity of NFAs
• On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
• Transition complexity of incomplete DFAs
• Transition complexity of incomplete DFAs
• Automata, Languages and Programming

Cited in

(6)

• Transition complexity of language operations
• On the average state and transition complexity of finite languages
• Transition complexity of incomplete DFAs
• Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
• #NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes
• Lower bounds for the transition complexity of NFAs

This page was built for publication: Lower Bounds for the Transition Complexity of NFAs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5756712)