State complexity of some operations on binary regular languages
From MaRDI portal
Publication:1763716
DOI10.1016/j.tcs.2004.04.011zbMath1078.68088OpenAlexW2050154914MaRDI QIDQ1763716
Publication date: 22 February 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2004.04.011
Related Items (60)
A Study of a Simple Class of Modifiers: Product Modifiers ⋮ The state complexity of \(L^{2}\) and \(L^k\) ⋮ State Complexity of Catenation Combined with a Boolean Operation: A Unified Approach ⋮ COMPLEXITY IN UNION-FREE REGULAR LANGUAGES ⋮ STATE COMPLEXITY OF CODE OPERATORS ⋮ STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-STAR AND CATENATION-REVERSAL ⋮ State complexity of combined operations ⋮ Nondeterministic complexity of operations on free and convex languages ⋮ On complementing unambiguous automata and graphs with many cliques and cocliques ⋮ State complexity of star of union and square of union on \textit{k} regular languages ⋮ STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-UNION AND CATENATION-INTERSECTION ⋮ ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION ⋮ Nondeterministic operational complexity in subregular languages ⋮ Size complexity of rotating and sweeping automata ⋮ State complexity of union and intersection of star on \(k\) regular languages ⋮ State complexity of the concatenation of regular tree languages ⋮ Formal methods for NFA equivalence: QBFs, witness extraction, and encoding verification ⋮ A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity ⋮ Operational state complexity revisited: the contribution of monsters and modifiers ⋮ State complexity of cyclic shift ⋮ Concatenation of regular languages and descriptional complexity ⋮ State complexity of combined operations with two basic operations ⋮ Nondeterministic state complexity of star-free languages ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the State Complexity of Complements, Stars, and Reversals of Regular Languages ⋮ DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET ⋮ Operations on Unambiguous Finite Automata ⋮ Kernels of Sub-classes of Context-Free Languages ⋮ Descriptional complexity of unambiguous input-driven pushdown automata ⋮ Incomplete operational transition complexity of regular languages ⋮ Transition complexity of language operations ⋮ Succinct description of regular languages by weak restarting automata ⋮ THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGES ⋮ Limitations of lower bound methods for deterministic nested word automata ⋮ Nondeterministic state complexity of nested word automata ⋮ 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 ⋮ Iterative arrays with self-verifying communication cell ⋮ Nondeterministic State Complexity of Star-Free Languages ⋮ State Complexity of Four Combined Operations Composed of Union, Intersection, Star and Reversal ⋮ State Complexity of Nested Word Automata ⋮ State Complexity of Catenation Combined with Union and Intersection ⋮ STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION ⋮ Operations on Unambiguous Finite Automata ⋮ The complexity of concatenation on deterministic and alternating finite automata ⋮ Concatenation of Regular Languages and Descriptional Complexity ⋮ NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY ⋮ Unnamed Item ⋮ Self-Verifying Finite Automata and Descriptional Complexity ⋮ Nondeterministic Complexity of Operations on Closed and Ideal Languages ⋮ On NFAs where all states are final, initial, or both ⋮ Nondeterministic complexity in subclasses of convex languages ⋮ Descriptional complexity of regular languages ⋮ Complement on Free and Ideal Languages ⋮ Transducing Markov sequences ⋮ Undecidability of state complexity ⋮ Combination of roots and Boolean operations: an application to state complexity ⋮ Operations on subregular languages and nondeterministic state complexity
Cites Work
- A lower bound technique for the size of nondeterministic finite automata
- Partial orders on words, minimal elements of regular languages, and state complexity
- Succinct representation of regular languages by Boolean automata
- Intersection and union of regular languages and state complexity
- The state complexities of some basic operations on regular languages
- Communication complexity method for measuring nondeterminism in finite automata
- UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
- Nondeterminism and the size of two way finite automata
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: State complexity of some operations on binary regular languages
