Deterministic regular expressions with back-references
From MaRDI portal
Publication:2316926
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/
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
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
