Extended Regular Expressions: Succinctness and Decidability

DOI10.4230/LIPICS.STACS.2011.507MaRDI QIDQ3113715zbMATH OpenOpenAlexFDO

Authors Dominik D. Freydenberger

Publication date 23 January 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_5c09.html

zbMATH Keywords

decidabilityextended regular expressionsnon-recursive tradeoffsregex

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Extended regular expressions: succinctness and decidability
• On Extended Regular Expressions
• On a generalization of regular expressions
• A Compact Proof of Decidability for Regular Expression Equivalence
• Regular expressions: new results and open problems
• scientific article; zbMATH DE number 2201362
• Succinctness of the Complement and Intersection of Regular Expressions
• Succinctness of the complement and intersection of regular expressions
• Mathematical Foundations of Computer Science 2004
• Descriptional complexity of deterministic regular expressions

Cited in

(23)

• Succinct representation of regular sets using gotos and Boolean variables
• Inclusion problems for patterns with a bounded number of variables
• Parameterized regular expressions and their languages
• On minimizing regular expressions without Kleene star
• Deterministic regular expressions with back-references
• Document spanners: a formal approach to information extraction
• Parameterized regular expressions and their languages
• A Compact Proof of Decidability for Regular Expression Equivalence
• Regular expressions with nested levels of back referencing form a hierarchy
• Succinctness of the Complement and Intersection of Regular Expressions
• Bit-coded Regular Expression Parsing
• A polynomial time match test for large classes of extended regular expressions
• Semi-linear Parikh Images of Regular Expressions via Reduction
• On Extended Regular Expressions
• Extended regular expressions: succinctness and decidability
• Expressiveness and static analysis of extended conjunctive regular path queries
• Deterministic regular expressions with back-references
• scientific article; zbMATH DE number 7315073 (Why is no real title available?)
• Cuts in regular expressions
• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
• An Effective Algorithm for the Membership Problem for Extended Regular Expressions
• An SMT solver for regular expressions and linear arithmetic over string length
• Extended regular expressions of star degree at most two

This page was built for publication: Extended Regular Expressions: Succinctness and Decidability

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