The complexity of regular(-like) expressions

DOI10.1007/978-3-642-14455-4_3MaRDI QIDQ3584879zbMATH OpenOpenAlexFDO

Authors Markus Holzer, Martin Kutrib

Publication date 31 August 2010

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-14455-4_3

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• The complexity of regular(-like) expressions
• Tight Bounds on the Descriptional Complexity of Regular Expressions
• Descriptional complexity of regular languages
• From finite automata to regular expressions and back -- a summary on descriptional complexity
• From finite automata to regular expressions and back -- a summary on descriptional complexity

Cited in

(15)

• The complexity of regular(-like) expressions
• A hitchhiker's guide to descriptional complexity through analytic combinatorics
• scientific article; zbMATH DE number 2201362 (Why is no real title available?)
• On classes of tractable unrestricted regular expressions
• Succinctness of the complement and intersection of regular expressions
• Descriptional complexity of two-way pushdown automata with restricted head reversals
• Descriptional complexity of two-way pushdown automata with restricted head reversals
• Descriptional complexity of deterministic regular expressions
• Implication of regular expressions
• Regular expressions: new results and open problems
• On regular expression proof complexity
• Language operations with regular expressions of polynomial size
• Tight Bounds on the Descriptional Complexity of Regular Expressions
• Descriptional complexity of regular languages
• Extended regular expressions: succinctness and decidability

This page was built for publication: The complexity of regular(-like) expressions

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