State complexity of power
From MaRDI portal
Publication:1019718
DOI10.1016/J.TCS.2009.02.025zbMath1168.68024OpenAlexW2084661883MaRDI QIDQ1019718
Michael Domaratzki, Alexander Okhotin
Publication date: 4 June 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.02.025
Related Items (28)
A Study of a Simple Class of Modifiers: Product Modifiers ⋮ State Complexity of Kleene-Star Operations on Trees ⋮ Operational State Complexity of Subtree-Free Regular Tree Languages ⋮ COMPLEXITY IN UNION-FREE REGULAR LANGUAGES ⋮ STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-STAR AND CATENATION-REVERSAL ⋮ State complexity of operations on input-driven pushdown automata ⋮ 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 ⋮ Nondeterministic operational complexity in subregular languages ⋮ State complexity of union and intersection of star on \(k\) regular languages ⋮ Unnamed Item ⋮ State complexity of combined operations with two basic operations ⋮ State complexity of operations on two-way finite automata over a unary alphabet ⋮ Unnamed Item ⋮ On the State Complexity of Operations on Two-Way Finite Automata ⋮ On the state complexity of operations on two-way finite automata ⋮ 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 ⋮ State Complexity of Four Combined Operations Composed of Union, Intersection, Star and Reversal ⋮ State Complexity of Operations on Two-Way Deterministic Finite Automata over a Unary Alphabet ⋮ State complexity of deletion and bipolar deletion ⋮ Square on Deterministic, Alternating, and Boolean Finite Automata ⋮ State Complexity of Catenation Combined with Union and Intersection ⋮ Descriptional complexity of regular languages ⋮ State complexity of unambiguous operations on finite automata ⋮ Undecidability of state complexity ⋮ State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages ⋮ Operations on subregular languages and nondeterministic state complexity
Cites Work
- The state complexity of \(L^{2}\) and \(L^k\)
- State complexity of basic language operations combined with reversal
- Intersection and union of regular languages and state complexity
- The state complexities of some basic operations on regular languages
- State complexity of combined operations
- On the State Complexity of Star of Union and Star of Intersection
- UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
- ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION
- STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: State complexity of power
