Regular expressions: new results and open problems
From MaRDI portal
(Redirected from Publication:5437181)
Recommendations
Cited in
(61)- scientific article; zbMATH DE number 7561614 (Why is no real title available?)
- On the length of shortest strings accepted by two-way finite automata
- Defining long words succinctly in FO and MSO
- Small Extended Expressions for Acyclic Automata
- A hitchhiker's guide to descriptional complexity through analytic combinatorics
- scientific article; zbMATH DE number 2201362 (Why is no real title available?)
- Computing minimal distinguishing Hennessy-Milner formulas is NP-hard, but variants are tractable
- Multi-tilde-bar expressions and their automata
- The state complexity of permutations on finite languages over binary alphabets
- Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
- scientific article; zbMATH DE number 7318987 (Why is no real title available?)
- Operational complexity and right linear grammars
- On the Weihrauch degree of the additive Ramsey theorem
- scientific article; zbMATH DE number 5671764 (Why is no real title available?)
- Efficient enumeration of regular expressions for faster regular expression synthesis
- Incremental algorithms for solving regular expression intersection non-emptiness
- Identities and periodic oscillations of divide-and-conquer recurrences splitting at half
- 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
- Hilbert's tenth problem for term algebras with a substitution operator
- Defining long words succinctly in FO and MSO
- Further Remarks on the Operational Nonterminal Complexity
- Complemented subsets and Boolean-valued, partial functions
- Acyclic automata and small expressions using multi-tilde-bar operators
- On minimizing regular expressions without Kleene star
- Implication of regular expressions
- Short Regular Expressions from Finite Automata: Empirical Results
- Shortest accepted strings for two-way finite automata: approaching the \(2^n\) lower bound
- Extended Regular Expressions: Succinctness and Decidability
- State complexity of Kleene-star operations on trees
- State complexity of unique rational operations
- A benchmark production tool for regular expressions
- 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
- scientific article; zbMATH DE number 7350780 (Why is no real title available?)
- From regular expressions to deterministic finite automata: \(2^{\frac{n}{2}+\sqrt{n}(\log n)^{\varTheta (1)}}\) states are necessary and sufficient
- Checking whether two unambiguous context-free grammars describe the same set of strings of length n
- Closures in Formal Languages and Kuratowski’s Theorem
- Lower bounds for context-free grammars
- Games for succinctness of regular expressions
- A framework for computing upper bounds in passive learning settings
- 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
- On NFAs where all states are final, initial, or both
- A New Family of Regular Operators Fitting with the Position Automaton Computation
- Multi-tilde Operators and Their Glushkov Automata
- Regular Expressions on Average and in the Long Run
- Incremental dead state detection in logarithmic time
- 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)
