Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
From MaRDI portal
Publication:5946055
DOI10.1006/jcss.2001.1748zbMath1014.68093OpenAlexW2039984653MaRDI QIDQ5946055
Juraj Hromkovič, Thomas Wilke, Sebastian Seibert
Publication date: 2 July 2002
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/167283803961a7216e349d27bcbfb4ee377393c8
Related Items (29)
Comparing the size of NFAs with and without \(\epsilon\)-transitions ⋮ Deciding determinism of caterpillar expressions ⋮ THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS ⋮ Passive testing with asynchronous communications and timestamps ⋮ Series parallel digraphs with loops ⋮ Deterministic Caterpillar Expressions ⋮ Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions ⋮ Efficient weighted expressions conversion ⋮ A faster algorithm for finding shortest substring matches of a regular expression ⋮ On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes ⋮ Construction of Tree Automata from Regular Expressions ⋮ Follow automata. ⋮ Reducing NFAs by invariant equivalences. ⋮ Postfix automata ⋮ A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS ⋮ Regular Language Constrained Sequence Alignment Revisited ⋮ Transition complexity of language operations ⋮ Lower bounds for the transition complexity of NFAs ⋮ On the complexity of decidable cases of the commutation problem of languages ⋮ A New Family of Regular Operators Fitting with the Position Automaton Computation ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity ⋮ Multi-tilde Operators and Their Glushkov Automata ⋮ Practical regular expression constrained sequence alignment ⋮ Construction of tree automata from regular expressions ⋮ NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY ⋮ Descriptional complexity of regular languages ⋮ Conversion of regular expressions into realtime automata ⋮ The Bottom-Up Position Tree Automaton and the Father Automaton
Cites Work
- Complexity measures for regular expressions
- Regular expressions into finite automata
- From regular expressions to DFA's using compressed NFA's
- THE ABSTRACT THEORY OF AUTOMATA
- Translating regular expressions into small ε-free nondeterministic finite automata
- Programming Techniques: Regular expression search algorithm
- Ambiguity in Graphs and Expressions
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
