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
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 ⋮ Operations on Permutation Automata ⋮ Rewriting regular inequalities ⋮ State Complexity of Catenation Combined with a Boolean Operation: A Unified Approach ⋮ Operational State Complexity of Subtree-Free Regular Tree Languages ⋮ State complexity of SBTA languages ⋮ The exact state complexity for the composition of root and reversal ⋮ Completely distinguishable automata and the set of synchronizing words ⋮ State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs ⋮ Further Remarks on the Operational Nonterminal Complexity ⋮ Formal methods for NFA equivalence: QBFs, witness extraction, and encoding verification ⋮ Cellular Automata: Descriptional Complexity and Decidability ⋮ Operational state complexity revisited: the contribution of monsters and modifiers ⋮ Operational complexity: NFA-to-DFA trade-off ⋮ Binary and circular automata having maximal state complexity for the set of synchronizing words ⋮ Operational complexity in subregular classes ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Descriptional Complexity of the Forever Operator ⋮ NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES ⋮ THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS ⋮ IN SEARCH OF MOST COMPLEX REGULAR LANGUAGES ⋮ THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGES ⋮ NONDETERMINISTIC STATE COMPLEXITY OF PROPORTIONAL REMOVALS ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ Formal languages over GF(2) ⋮ Minimal cover-automata for finite languages ⋮ The Size-Cost of Boolean Operations on Constant Height Deterministic Pushdown Automata ⋮ State Complexity of Four Combined Operations Composed of Union, Intersection, Star and Reversal ⋮ Note on Reversal of Binary Regular Languages ⋮ State Complexity of Operations on Two-Way Deterministic Finite Automata over a Unary Alphabet ⋮ State complexity of deletion and bipolar deletion ⋮ Most Complex Non-Returning Regular Languages ⋮ One-Time Nondeterministic Computations ⋮ Square on Deterministic, Alternating, and Boolean Finite Automata ⋮ STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION ⋮ STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET ⋮ Complexity of proper prefix-convex regular languages ⋮ Complexity of proper prefix-convex regular languages ⋮ The complexity of concatenation on deterministic and alternating finite automata ⋮ Square on Ideal, Closed and Free Languages ⋮ Universal Disjunctive Concatenation and Star ⋮ The State Complexity of Permutations on Finite Languages over Binary Alphabets ⋮ Star-Complement-Star on Prefix-Free Languages ⋮ State Complexity of Overlap Assembly ⋮ The Ranges of Accepting State Complexities of Languages Resulting from Some Operations ⋮ State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages
Cites Work
This page was built for publication: The state complexities of some basic operations on regular languages
