Deterministic regular expressions with back-references

DOI10.1016/j.jcss.2019.04.001zbMath1423.68251OpenAlexW2962964296WikidataQ127989400 ScholiaQ127989400MaRDI QIDQ2316926

Markus L. Schmid, Dominik D. Freydenberger

Publication date: 7 August 2019

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7000/

zbMATH Keywords

regexGlushkov automatondeterministic regular expression

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

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 ⋮ Unnamed Item

Uses Software

• PERL
• XQuery
• XPath

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Closure properties and descriptional complexity of deterministic regular expressions
• On the parameterised complexity of string morphism problems
• Finding all solutions of equations in free groups and monoids with involution
• Extended regular expressions: succinctness and decidability
• Expressiveness and static analysis of extended conjunctive regular path queries
• Deciding determinism of regular languages
• Generalizations of 1-deterministic regular languages
• Finite automata and unary languages
• Finding patterns common to a set of strings
• Regular expressions into finite automata
• Finite-memory automata
• Document spanners: from expressive power to decision problems
• Pattern matching with variables: a multivariate complexity analysis
• Deciding definability by deterministic regular expressions
• Efficient testing and matching of deterministic regular expressions
• Characterising REGEX languages by regular languages equipped with factor-referencing
• Document Spanners
• Definability by Weakly Deterministic Regular Expressions with Counters is Decidable
• More Than 1700 Years of Word Equations
• Querying Graphs with Data
• Complexity of Decision Problems for XML Schemas and Chain Regular Expressions
• On Extended Regular Expressions
• Generalized One-Unambiguity
• Finite state machines for strings over infinite alphabets
• From Monadic Logic to PSL
• INSIDE THE CLASS OF REGEX LANGUAGES
• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
• Regular Expressions with Counting: Weak versus Strong Determinism
• One-unambiguous regular languages