Extended regular expressions: succinctness and decidability
From MaRDI portal
Recommendations
Cites work
- A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
- A lower bound technique for the size of nondeterministic finite automata
- A polynomial time match test for large classes of extended regular expressions
- Classical recursion theory. The theory of functions and sets of natural numbers
- Classical recursion theory. Vol. II
- Descriptional complexity -- an introductory survey
- Descriptional complexity of machines with limited resources
- Extended Regular Expressions: Succinctness and Decidability
- Extending regular expressions with homomorphic replacement
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3700811 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 1142294 (Why is no real title available?)
- scientific article; zbMATH DE number 3310089 (Why is no real title available?)
- Inclusion problems for patterns with a bounded number of variables
- Languages with homomorphic replacements
- On Extended Regular Expressions
- On Goedel speed-up and succinctness of language representations
- On the intersection of regex languages with regular languages
- Open Problems in Pattern Avoidance
- Pattern expressions and pattern automata
- Regular expressions with nested levels of back referencing form a hierarchy
- Synchronized regular expressions
- The complexity of regular(-like) expressions
- THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
Cited in
(30)- Succinct representation of regular sets using gotos and Boolean variables
- Document spanners: from expressive power to decision problems
- On minimizing regular expressions without Kleene star
- Deterministic regular expressions with back-references
- A logic for document spanners
- Characterising REGEX languages by regular languages equipped with factor-referencing
- Re-examining regular expressions with backreferences
- A Compact Proof of Decidability for Regular Expression Equivalence
- Succinctness of the Complement and Intersection of Regular Expressions
- Bit-coded Regular Expression Parsing
- Extended Regular Expressions: Succinctness and Decidability
- Semi-linear Parikh Images of Regular Expressions via Reduction
- On Extended Regular Expressions
- Deterministic regular expressions with back-references
- scientific article; zbMATH DE number 7315073 (Why is no real title available?)
- Graph and string parameters: connections between pathwidth, cutwidth and the locality number
- scientific article; zbMATH DE number 7278096 (Why is no real title available?)
- Cuts in regular expressions
- scientific article; zbMATH DE number 3271521 (Why is no real title available?)
- A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
- 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
- Matching patterns with variables under Simon's congruence
- Languages generated by conjunctive query fragments of FC[REG]
- Regular expressions with backreferences: polynomial-time matching techniques
- On the computational and descriptional complexity of multi-pattern languages
- Blocksequences of \(k\)-local words
- An SMT solver for regular expressions and linear arithmetic over string length
- Extended regular expressions of star degree at most two
This page was built for publication: Extended regular expressions: succinctness and decidability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q372977)
