Comparing the size of NFAs with and without -transitions

DOI10.1016/J.TCS.2007.02.063MaRDI QIDQ2373739zbMATH OpenOpenAlexFDO

Authors 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

descriptional complexityfinite automatalower bounds on complexity

Mathematics Subject Classification ID

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

Recommendations

• Automata, Languages and Programming
• Regular Expressions and NFAs Without ε-Transitions
• Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
• A lower bound on the size of \(\varepsilon\)-free NFA corresponding to a regular expression
• Translating regular expressions into small -free nondeterministic finite automata

Cites work

• A lower bound on the size of \(\varepsilon\)-free NFA corresponding to a regular expression
• Ambiguity in Graphs and Expressions
• Communication Complexity
• scientific article; zbMATH DE number 193480 (Why is no real title available?)
• scientific article; zbMATH DE number 1011685 (Why is no real title available?)
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Programming Techniques: Regular expression search algorithm
• Regular Expressions and NFAs Without ε-Transitions
• Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
• Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions

Cited in

(12)

• 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
• Algorithms for path-constrained sequence alignment
• The tractability frontier for NFA minimization
• scientific article; zbMATH DE number 1927179 (Why is no real title available?)
• Implementation and Application of Automata
• Automata, Languages and Programming
• scientific article; zbMATH DE number 5181726 (Why is no real title available?)
• Probabilism versus Alternation for Automata
• Lower bounds for the transition complexity of NFAs

This page was built for publication: Comparing the size of NFAs with and without \(\epsilon\)-transitions

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