Publication:5437181
From MaRDI portal
zbMath1143.68434MaRDI QIDQ5437181
Wang, Ming-wei, Bryan Krawetz, Keith Ellul, Jeffrey O. Shallit
Publication date: 18 January 2008
68Q45: Formal languages and automata
Related Items
Unnamed Item, Unnamed Item, On the Length of Shortest Strings Accepted by Two-way Finite Automata, Decidability and Shortest Strings in Formal Languages, Optimal Lower Bounds on Regular Expression Size Using Communication Complexity, The State Complexity of Permutations on Finite Languages over Binary Alphabets, Further Remarks on the Operational Nonterminal Complexity, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, Shortest accepted strings for two-way finite automata: approaching the \(2^n\) lower bound, On the sizes of DPDAs, PDAs, LBAs, Series parallel digraphs with loops, Decision problems for convex languages, Multi-tilde-bar expressions and their automata, Succinctness of regular expressions with interleaving, intersection and counting, State complexity of unique rational operations, On NFAs where all states are final, initial, or both, Lower bounds for context-free grammars, Acyclic automata and small expressions using multi-tilde-bar operators, Complexity of universality and related problems for partially ordered NFAs, Operational complexity and right linear grammars, Reversibility for stateless ordered RRWW-automata, Descriptional complexity of regular languages, Enumerating regular expressions and their languages, Defining long words succinctly in FO and MSO, Efficient enumeration of regular expressions for faster regular expression synthesis, On minimizing regular expressions without Kleene star, Language operations with regular expressions of polynomial size, On Boolean combinations forming piecewise testable languages, A hitchhiker's guide to descriptional complexity through analytic combinatorics, State Complexity of Kleene-Star Operations on Trees, Finite Automata, Digraph Connectivity, and Regular Expression Size, The Frobenius Problem and Its Generalizations, The Average State Complexity of the Star of a Finite Set of Words Is Linear, Provably Shorter Regular Expressions from Deterministic Finite Automata, A New Family of Regular Operators Fitting with the Position Automaton Computation, Antimirov and Mosses’s Rewrite System Revisited, Multi-tilde Operators and Their Glushkov Automata, Closures in Formal Languages and Kuratowski’s Theorem, Tight Bounds on the Descriptional Complexity of Regular Expressions, Short Regular Expressions from Finite Automata: Empirical Results, Small Extended Expressions for Acyclic Automata
