Regular expressions: new results and open problems
From MaRDI portal
Publication:5437181
zbMATH Open1143.68434MaRDI QIDQ5437181FDOQ5437181
Jeffrey Shallit, Ming-wei Wang, Bryan Krawetz, Keith Ellul
Publication date: 18 January 2008
Recommendations
Cited In (51)
- Title not available (Why is that?)
- 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
- 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
- Decidability and Shortest Strings in Formal Languages
- 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
- Extended Regular Expressions: Succinctness and Decidability
- 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
- On the Length of Shortest Strings Accepted by Two-way Finite Automata
- Title not available (Why is that?)
- Closures in Formal Languages and Kuratowski’s Theorem
- Lower bounds for context-free grammars
- State Complexity of Kleene-Star Operations on Trees
- 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
- The State Complexity of Permutations on Finite Languages over Binary Alphabets
- 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
- Games for succinctness of regular expressions
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)
