The complexity of restricted regular expressions and the synthesis problem for finite automata

DOI10.1016/0022-0000(81)90070-2zbMath0516.68051OpenAlexW2036210786MaRDI QIDQ1052825

Ernst L. Leiss

Publication date: 1981

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

Full work available at URL: https://doi.org/10.1016/0022-0000(81)90070-2

zbMATH Keywords

deterministic finite automatonregular expression

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (9)

THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS ⋮ Manipulation of regular expressions using derivatives: an overview ⋮ The validation of SGML content models ⋮ One-unambiguous regular languages ⋮ One-unambiguous regular languages ⋮ From regular expressions to finite automata^∗ ⋮ From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity ⋮ Descriptional complexity of regular languages ⋮ On classes of tractable unrestricted regular expressions

Cites Work

• Programming Techniques: Regular expression search algorithm
• Automatic generation of efficient lexical processors using finite state techniques
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of restricted regular expressions and the synthesis problem for finite automata