Extended regular expressions: succinctness and decidability

DOI10.1007/s00224-012-9389-0zbMath1286.68281OpenAlexW2067443406MaRDI QIDQ372977

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/

zbMATH Keywords

decidabilityextended regular expressionsnon-recursive tradeoffsregex

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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