Comparing the size of NFAs with and without \(\epsilon\)-transitions
From MaRDI portal
Publication:2373739
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
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