Re-examining regular expressions with backreferences

DOI10.1016/J.TCS.2022.10.041MaRDI QIDQ2699953zbMATH OpenOpenAlexFDO

Authors Martin Berglund, Brink van der Merwe

Publication date 20 April 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2022.10.041

zbMATH Keywords

backreferencesregular expressions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Deterministic regular expressions with back-references
• Deterministic regular expressions with back-references
• Inside the class of REGEX languages
• Inside the Class of REGEX Languages
• Regular expressions with nested levels of back referencing form a hierarchy

Cites work

• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
• A helpful result for proving inherent ambiguity
• Analyzing catastrophic backtracking behavior in practical regular expression matching
• Analyzing matching time behavior of backtracking regular expression matchers by using ambiguity of NFA
• Characterising REGEX languages by regular languages equipped with factor-referencing
• Deterministic regular expressions with back-references
• Extended regular expressions: succinctness and decidability
• scientific article; zbMATH DE number 1629861 (Why is no real title available?)
• scientific article; zbMATH DE number 1142294 (Why is no real title available?)
• Inside the Class of REGEX Languages
• On Extended Regular Expressions
• On the semantics of atomic subgroups in practical regular expressions
• Pattern matching with variables: a multivariate complexity analysis
• Programming Techniques: Regular expression search algorithm
• Regular expressions with nested levels of back referencing form a hierarchy
• Synchronized regular expressions

Cited in

(6)

• On the undecidability and descriptional complexity of synchronized regular expressions
• On lookaheads in regular expressions with backreferences
• Regular expressions with backreferences and lookaheads capture NLOG
• Measuring the expressive power of practical regular expressions by classical stacking automata models
• Disambiguation of regular expressions with backreferences via term rewriting
• Efficient matching of some fundamental regular expressions with backreferences

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Re-examining regular expressions with backreferences

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