Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions

DOI10.1016/S0022-0000(03)00036-9zbMath1055.68068MaRDI QIDQ1401956

Viliam Geffert

Publication date: 19 August 2003

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

Regular languagesDescriptional complexityFormal languagesRegular expressionsFinite-state automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Comparing the size of NFAs with and without \(\epsilon\)-transitions ⋮ Deciding determinism of caterpillar expressions ⋮ THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS ⋮ Deterministic Caterpillar Expressions ⋮ 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 ⋮ From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity ⋮ Conversion of regular expressions into realtime automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity measures for regular expressions
• Optimal Simulations between Unary Automata
• Ambiguity in Graphs and Expressions
• Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata