The state complexities of some basic operations on regular languages
From MaRDI portal
Publication:1318694
DOI10.1016/0304-3975(92)00011-FzbMath0795.68112OpenAlexW2006629323WikidataQ57380768 ScholiaQ57380768MaRDI QIDQ1318694
Kai Salomaa, Qingyu Zhuang, Sheng Yu
Publication date: 5 April 1994
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(92)00011-f
Related Items (only showing first 100 items - show all)
Closure properties and descriptional complexity of deterministic regular expressions ⋮ State complexity of permutation on finite languages over a binary alphabet ⋮ State Complexity of Kleene-Star Operations on Trees ⋮ State complexity of projection on languages recognized by permutation automata and commuting letters ⋮ Generating all permutations by context-free grammars in Chomsky normal form ⋮ Descriptional Complexity of Input-Driven Pushdown Automata ⋮ Undecidability of State Complexities Using Mirror Images ⋮ The state complexity of \(L^{2}\) and \(L^k\) ⋮ State Complexity of Boundary of Prefix-Free Regular Languages ⋮ COMPLEXITY IN UNION-FREE REGULAR LANGUAGES ⋮ STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-STAR AND CATENATION-REVERSAL ⋮ State complexity of combined operations ⋮ On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs ⋮ The Degree of Irreversibility in Deterministic Finite Automata ⋮ An approximation algorithm for state minimization in 2-MDFAs ⋮ Performing regular operations with 1-limited automata ⋮ On the state complexity of reversals of regular languages ⋮ Complexity of suffix-free regular languages ⋮ Operational complexity and pumping lemmas ⋮ Boolean language operations on nondeterministic automata with a pushdown of constant height ⋮ Quotient complexity of closed languages ⋮ State complexity of star of union and square of union on \textit{k} regular languages ⋮ State complexity of combined operations for suffix-free regular languages ⋮ Complexity of Suffix-Free Regular Languages ⋮ Succinctness of descriptions of SBTA-languages ⋮ STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-UNION AND CATENATION-INTERSECTION ⋮ ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION ⋮ State complexity of pattern matching in regular languages ⋮ Kleene closure and state complexity ⋮ State complexity of inversion operations ⋮ Prefix-free languages: left and right quotient and reversal ⋮ Operational state complexity of unary NFAs with finite nondeterminism ⋮ Unambiguous finite automata over a unary alphabet ⋮ Ordering regular languages and automata: complexity ⋮ State complexity of union and intersection of star on \(k\) regular languages ⋮ State complexity of the concatenation of regular tree languages ⋮ Unnamed Item ⋮ On the gap between separating words and separating their reversals ⋮ State complexity of cyclic shift ⋮ State Complexity of Insertion ⋮ On the descriptional complexity of stateless deterministic ordered restarting automata ⋮ Concatenation of regular languages and descriptional complexity ⋮ State complexity of combined operations with two basic operations ⋮ A finite state intersection approach to propositional satisfiability ⋮ State Complexity of Regular Tree Languages for Tree Matching ⋮ The size-cost of Boolean operations on constant height deterministic pushdown automata ⋮ Reversal of binary regular languages ⋮ State complexity of operations on two-way finite automata over a unary alphabet ⋮ The Frobenius Problem and Its Generalizations ⋮ The Average State Complexity of the Star of a Finite Set of Words Is Linear ⋮ On the State Complexity of Complements, Stars, and Reversals of Regular Languages ⋮ STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES ⋮ Operations on Unambiguous Finite Automata ⋮ Incomplete operational transition complexity of regular languages ⋮ STATE COMPLEXITY AND APPROXIMATION ⋮ On the average state and transition complexity of finite languages ⋮ State complexity of basic language operations combined with reversal ⋮ On the state complexity of operations on two-way finite automata ⋮ Two double-exponential gaps for automata with a limited pushdown ⋮ UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION ⋮ State complexity of deterministic Watson-Crick automata and time varying Watson-Crick automata ⋮ QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES ⋮ On the descriptional complexity of finite automata with modified acceptance conditions ⋮ State complexity of some operations on binary regular languages ⋮ Acyclic networks maximizing the printing complexity ⋮ THE AVERAGE STATE COMPLEXITY OF RATIONAL OPERATIONS ON FINITE LANGUAGES ⋮ Some properties of iterated languages ⋮ State-complexity hierarchies of uniform languages of alphabet-size length ⋮ Estimation of state complexity of combined operations ⋮ State complexity of union and intersection of square and reversal on \(k\) regular languages ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ Power, positive closure, and quotients on convex languages ⋮ Enumeration and random generation of accessible automata ⋮ State Complexity of Combined Operations for Prefix-Free Regular Languages ⋮ State Complexity of Catenation Combined with Union and Intersection ⋮ Operations on Unambiguous Finite Automata ⋮ State complexity of power ⋮ State complexity of unique rational operations ⋮ Concatenation of Regular Languages and Descriptional Complexity ⋮ NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY ⋮ Self-Verifying Finite Automata and Descriptional Complexity ⋮ Unrestricted State Complexity of Binary Operations on Regular Languages ⋮ Descriptional Complexity of Bounded Regular Languages ⋮ The Complexity of Languages Resulting from the Concatenation Operation ⋮ The Degree of Irreversibility in Deterministic Finite Automata ⋮ State complexity of basic operations on suffix-free regular languages ⋮ Nondeterministic complexity in subclasses of convex languages ⋮ Descriptional complexity of regular languages ⋮ Primitivity, uniform minimality, and state complexity of Boolean operations ⋮ State complexity of combined operations involving catenation and binary Boolean operations: beyond the Brzozowski conjectures ⋮ State complexity of unambiguous operations on finite automata ⋮ Composition and orbits of language operations: finiteness and upper bounds ⋮ Undecidability of state complexity ⋮ Commutative regular languages with product-form minimal automata ⋮ State complexity investigations on commutative languages -- the upward and downward closure, commutative aperiodic and commutative group languages ⋮ Simulating finite automata with context-free grammars. ⋮ On the boundary of regular languages ⋮ On Simon's congruence closure of a string ⋮ State complexity of GF(2)-operations on unary languages ⋮ State complexity of permutation and related decision problems on alphabetical pattern constraints
Cites Work
This page was built for publication: The state complexities of some basic operations on regular languages
