On regular expression proof complexity

DOI10.1007/978-3-319-62809-7_5MaRDI QIDQ2408794zbMATH OpenOpenAlexFDO

Authors Simon Beier, Markus Holzer

Publication date 13 October 2017

Full work available at URL https://doi.org/10.1007/978-3-319-62809-7_5

Mathematics Subject Classification ID

Complexity of proofs (03F20) Formal languages and automata (68Q45)

Recommendations

• A Compact Proof of Decidability for Regular Expression Equivalence
• The complexity of regular(-like) expressions
• The complexity of regular(-like) expressions
• Proof Pearl: regular expression equivalence and relation algebra
• A cut-free cyclic proof system for Kleene algebra

Cited in

(7)

• A cut-free cyclic proof system for Kleene algebra
• Complexity of regex crosswords
• Proof Pearl: regular expression equivalence and relation algebra
• The complexity of regular(-like) expressions
• Quantitative Verification of Stochastic Regular Expressions
• Regular expression containment, coinductive axiomatization and computational interpretation
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity

This page was built for publication: On regular expression proof complexity

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