Extended regular expressions: succinctness and decidability
From MaRDI portal
Publication:372977
DOI10.1007/S00224-012-9389-0zbMATH Open1286.68281OpenAlexW2067443406MaRDI QIDQ372977FDOQ372977
Authors: Dominik D. Freydenberger 
Publication date: 21 October 2013
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2011/3039/
Recommendations
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Regular expressions with nested levels of back referencing form a hierarchy
- Open Problems in Pattern Avoidance
- Classical recursion theory. The theory of functions and sets of natural numbers
- A polynomial time match test for large classes of extended regular expressions
- A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
- Classical recursion theory. Vol. II
- On the intersection of regex languages with regular languages
- Languages with homomorphic replacements
- Synchronized regular expressions
- Descriptional complexity -- an introductory survey
- Extended Regular Expressions: Succinctness and Decidability
- Extending regular expressions with homomorphic replacement
- The complexity of regular(-like) expressions
- Inclusion problems for patterns with a bounded number of variables
- On Extended Regular Expressions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Descriptional complexity of machines with limited resources
- THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
- On Goedel speed-up and succinctness of language representations
- A lower bound technique for the size of nondeterministic finite automata
- Pattern expressions and pattern automata
Cited In (28)
- Characterising REGEX languages by regular languages equipped with factor-referencing
- Blocksequences of \(k\)-local words
- An SMT solver for regular expressions and linear arithmetic over string length
- Succinct representation of regular sets using gotos and Boolean variables
- Title not available (Why is that?)
- Deterministic regular expressions with back-references
- Title not available (Why is that?)
- On minimizing regular expressions without Kleene star
- Extended Regular Expressions: Succinctness and Decidability
- Document spanners: from expressive power to decision problems
- A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
- On Extended Regular Expressions
- Matching patterns with variables under Simon's congruence
- Cuts in regular expressions
- A Compact Proof of Decidability for Regular Expression Equivalence
- A logic for document spanners
- Languages generated by conjunctive query fragments of FC[REG]
- Semi-linear Parikh Images of Regular Expressions via Reduction
- Succinctness of the Complement and Intersection of Regular Expressions
- Bit-coded Regular Expression Parsing
- Languages generated by conjunctive query fragments of FC[REG]
- Re-examining regular expressions with backreferences
- On the undecidability and descriptional complexity of synchronized regular expressions
- Extended regular expressions of star degree at most two
- Title not available (Why is that?)
- Title not available (Why is that?)
- Deterministic regular expressions with back-references
- Matching patterns with variables under edit distance
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 Q372977)
