Regular Expressions and NFAs Without ε-Transitions

DOI10.1007/11672142_35zbMath1136.68422OpenAlexW81175699MaRDI QIDQ5449819

Georg Schnitger

Publication date: 19 March 2008

Published in: STACS 2006 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11672142_35

zbMATH Keywords

regular expressionsdescriptional complexitynondeterministic automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (15)

Comparing the size of NFAs with and without \(\epsilon\)-transitions ⋮ Deciding determinism of caterpillar expressions ⋮ Efficient testing and matching of deterministic regular expressions ⋮ Deterministic Caterpillar Expressions ⋮ Deciding determinism of unary languages ⋮ The tractability frontier for NFA minimization ⋮ Finite Automata, Digraph Connectivity, and Regular Expression Size ⋮ On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes ⋮ Regular Language Constrained Sequence Alignment Revisited ⋮ Transition complexity of language operations ⋮ Lower bounds for the transition complexity of NFAs ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ Sublinear DTD Validity ⋮ Optimal Lower Bounds on Regular Expression Size Using Communication Complexity ⋮ Descriptional complexity of regular languages

This page was built for publication: Regular Expressions and NFAs Without ε-Transitions