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