scientific article; zbMATH DE number 5228181
From MaRDI portal
Publication:5437181
zbMath1143.68434MaRDI QIDQ5437181
Wang, Ming-wei, Bryan Krawetz, Keith Ellul, Jeffrey O. Shallit
Publication date: 18 January 2008
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (41)
On Boolean combinations forming piecewise testable languages ⋮ State Complexity of Kleene-Star Operations on Trees ⋮ On the sizes of DPDAs, PDAs, LBAs ⋮ On minimizing regular expressions without Kleene star ⋮ Series parallel digraphs with loops ⋮ Unnamed Item ⋮ 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 ⋮ Lower bounds for context-free grammars ⋮ Finite Automata, Digraph Connectivity, and Regular Expression Size ⋮ A hitchhiker's guide to descriptional complexity through analytic combinatorics ⋮ Acyclic automata and small expressions using multi-tilde-bar operators ⋮ 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 ⋮ On the Length of Shortest Strings Accepted by Two-way Finite Automata ⋮ Decision problems for convex languages ⋮ Complexity of universality and related problems for partially ordered NFAs ⋮ Language operations with regular expressions of polynomial size ⋮ Succinctness of regular expressions with interleaving, intersection and counting ⋮ Multi-tilde-bar expressions and their automata ⋮ A New Family of Regular Operators Fitting with the Position Automaton Computation ⋮ Antimirov and Mosses’s Rewrite System Revisited ⋮ Unnamed Item ⋮ Decidability and Shortest Strings in Formal Languages ⋮ Multi-tilde Operators and Their Glushkov Automata ⋮ Optimal Lower Bounds on Regular Expression Size Using Communication Complexity ⋮ Operational complexity and right linear grammars ⋮ Reversibility for stateless ordered RRWW-automata ⋮ State complexity of unique rational operations ⋮ 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 ⋮ On NFAs where all states are final, initial, or both ⋮ Descriptional complexity of regular languages ⋮ Enumerating regular expressions and their languages ⋮ The State Complexity of Permutations on Finite Languages over Binary Alphabets ⋮ Defining long words succinctly in FO and MSO ⋮ Efficient enumeration of regular expressions for faster regular expression synthesis
This page was built for publication: