Comparing the size of NFAs with and without \(\epsilon\)-transitions

DOI10.1016/j.tcs.2007.02.063zbMath1115.68098OpenAlexW1968090455MaRDI QIDQ2373739

Georg Schnitger, Juraj Hromkovič

Publication date: 16 July 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.063

zbMATH Keywords

finite automatadescriptional complexitylower bounds on complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Theory of compilers and interpreters (68N20)

Related Items

Algorithms for path-constrained sequence alignment ⋮ The tractability frontier for NFA minimization ⋮ Probabilism versus Alternation for Automata ⋮ On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes ⋮ Lower bounds for the transition complexity of NFAs ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY ⋮ Descriptional complexity of regular languages

Cites Work

• A lower bound on the size of \(\varepsilon\)-free NFA corresponding to a regular expression
• Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions
• Communication Complexity
• Regular Expressions and NFAs Without ε-Transitions
• Programming Techniques: Regular expression search algorithm
• Ambiguity in Graphs and Expressions
• Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item