Extended regular expressions: succinctness and decidability
From MaRDI portal
Publication:372977
DOI10.1007/s00224-012-9389-0zbMath1286.68281OpenAlexW2067443406MaRDI QIDQ372977
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/
Related Items
Blocksequences of \(k\)-local words, Characterising REGEX languages by regular languages equipped with factor-referencing, Document spanners: from expressive power to decision problems, Languages generated by conjunctive query fragments of FC[REG], Matching patterns with variables under edit distance, On the undecidability and descriptional complexity of synchronized regular expressions, Re-examining regular expressions with backreferences, Unnamed Item, Deterministic regular expressions with back-references, Unnamed Item, A logic for document spanners
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Regular expressions with nested levels of back referencing form a hierarchy
- 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
- On the intersection of regex languages with regular languages
- Languages with homomorphic replacements
- Classical recursion theory. The theory of functions and sets of natural numbers
- Classical recursion theory. Vol. II
- Synchronized regular expressions
- A Polynomial Time Match Test for Large Classes of Extended Regular Expressions
- 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
- Open Problems in Pattern Avoidance
- A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
- THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
