Characterising REGEX languages by regular languages equipped with factor-referencing

DOI10.1016/j.ic.2016.02.003zbMath1344.68130OpenAlexW2286758035MaRDI QIDQ2629848

Markus L. Schmid

Publication date: 7 July 2016

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2016.02.003

zbMATH Keywords

regular languagesmemory automataREGEX languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Theory of programming languages (68N15)

Related Items

Enumerating grammar-based extractions ⋮ Languages generated by conjunctive query fragments of FC[REG] ⋮ On the undecidability and descriptional complexity of synchronized regular expressions ⋮ Detecting One-Variable Patterns ⋮ Unnamed Item ⋮ Deterministic regular expressions with back-references ⋮ A logic for document spanners

Uses Software

• PERL
• Python

Cites Work

• Unnamed Item
• Extended regular expressions: succinctness and decidability
• Pattern expressions and pattern automata
• On the intersection of regex languages with regular languages
• Languages with homomorphic replacements
• Synchronized regular expressions
• Parsing Beyond Context-Free Grammars
• Characterising REGEX Languages by Regular Languages Equipped with Factor-Referencing
• Extending regular expressions with homomorphic replacement
• On Extended Regular Expressions
• INSIDE THE CLASS OF REGEX LANGUAGES
• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
• On the nonexistence of a phrase structure grammar for ALGOL 60