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

DOI10.1016/j.tcs.2007.02.063zbMath1115.68098MaRDI 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 automata; descriptional complexity; lower bounds on complexity

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68N20: Theory of compilers and interpreters

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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