Regular expressions: new results and open problems
From MaRDI portal
Publication:5437181
zbMATH Open1143.68434MaRDI QIDQ5437181FDOQ5437181
Authors: Keith Ellul, Bryan Krawetz, Ming-wei Wang, Jeffrey Shallit 
Publication date: 18 January 2008
Recommendations
Cited In (52)
- Games for succinctness of regular expressions
- Title not available (Why is that?)
- On the length of shortest strings accepted by two-way finite automata
- Title not available (Why is that?)
- Small Extended Expressions for Acyclic Automata
- Defining long words succinctly in FO and MSO
- A hitchhiker's guide to descriptional complexity through analytic combinatorics
- The state complexity of permutations on finite languages over binary alphabets
- Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
- Title not available (Why is that?)
- Multi-tilde-bar expressions and their automata
- Operational complexity and right linear grammars
- Title not available (Why is that?)
- Identities and periodic oscillations of divide-and-conquer recurrences splitting at half
- Efficient enumeration of regular expressions for faster regular expression synthesis
- Decision problems for convex languages
- Rational index of languages defined by grammars with bounded dimension of parse trees
- On the quantitative semantics of regular expressions over real-valued signals
- On Boolean combinations forming piecewise testable languages
- Succinctness of regular expressions with interleaving, intersection and counting
- On the sizes of DPDAs, PDAs, LBAs
- Complexity of universality and related problems for partially ordered NFAs
- Further Remarks on the Operational Nonterminal Complexity
- Acyclic automata and small expressions using multi-tilde-bar operators
- On minimizing regular expressions without Kleene star
- Shortest accepted strings for two-way finite automata: approaching the \(2^n\) lower bound
- Short Regular Expressions from Finite Automata: Empirical Results
- Implication of regular expressions
- Extended Regular Expressions: Succinctness and Decidability
- State complexity of Kleene-star operations on trees
- A benchmark production tool for regular expressions
- State complexity of unique rational operations
- Reversibility for stateless ordered RRWW-automata
- The Average State Complexity of the Star of a Finite Set of Words Is Linear
- Decidability and shortest strings in formal languages
- Title not available (Why is that?)
- Closures in Formal Languages and Kuratowski’s Theorem
- Lower bounds for context-free grammars
- Finite Automata, Digraph Connectivity, and Regular Expression Size
- Language operations with regular expressions of polynomial size
- Tight Bounds on the Descriptional Complexity of Regular Expressions
- Descriptional complexity of regular languages
- Enumerating regular expressions and their languages
- Series parallel digraphs with loops
- A New Family of Regular Operators Fitting with the Position Automaton Computation
- On NFAs where all states are final, initial, or both
- Multi-tilde Operators and Their Glushkov Automata
- Incremental dead state detection in logarithmic time
- Regular Expressions on Average and in the Long Run
- Antimirov and Mosses’s Rewrite System Revisited
- Provably Shorter Regular Expressions from Deterministic Finite Automata
- The Frobenius Problem and Its Generalizations
This page was built for publication: Regular expressions: new results and open problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5437181)
