Characterising REGEX languages by regular languages equipped with factor-referencing

DOI10.1016/J.IC.2016.02.003MaRDI QIDQ2629848zbMATH OpenOpenAlexFDO

Authors 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

memory automataREGEX languagesregular languages

Mathematics Subject Classification ID

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

Recommendations

• Characterising REGEX languages by regular languages equipped with factor-referencing
• Inside the Class of REGEX Languages
• Inside the class of REGEX languages
• Deterministic regular expressions with back-references
• On the intersection of regex languages with regular languages

Cites work

• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
• Characterising REGEX languages by regular languages equipped with factor-referencing
• Extended regular expressions: succinctness and decidability
• Extending regular expressions with homomorphic replacement
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Inside the class of REGEX languages
• Languages with homomorphic replacements
• On Extended Regular Expressions
• On the intersection of regex languages with regular languages
• On the nonexistence of a phrase structure grammar for ALGOL 60
• Parsing beyond context-free grammars
• Pattern expressions and pattern automata
• Synchronized regular expressions

Cited in

(19)

• Deterministic regular expressions with back-references
• A logic for document spanners
• Characterising REGEX languages by regular languages equipped with factor-referencing
• Graph and string parameters: connections between pathwidth, cutwidth and the locality number
• Detecting one-variable patterns
• Inside the class of REGEX languages
• Enumerating grammar-based extractions
• Languages generated by conjunctive query fragments of FC[REG]
• On the undecidability and descriptional complexity of synchronized regular expressions
• Languages generated by conjunctive query fragments of FC[REG]
• Regular expressions with backreferences and lookaheads capture NLOG
• Regular expressions with backreferences: polynomial-time matching techniques
• Measuring the expressive power of practical regular expressions by classical stacking automata models
• Disambiguation of regular expressions with backreferences via term rewriting
• Refl-spanners: a purely regular approach to non-regular core spanners
• A purely regular approach to non-regular core spanners
• Grammars for document spanners
• The theory of concatenation over finite models
• Efficient matching of some fundamental regular expressions with backreferences

Describes a project that uses

Uses Software

• PERL
• Python

This page was built for publication: Characterising REGEX languages by regular languages equipped with factor-referencing

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