The state complexity of \(L^{2}\) and \(L^k\)

DOI10.1016/j.ipl.2005.06.011zbMath1187.68298OpenAlexW1482663448MaRDI QIDQ844206

Narad Rampersad

Publication date: 18 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.06.011

zbMATH Keywords

formal languagesstate complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (24)

Operations on Permutation Automata ⋮ Operational State Complexity of Subtree-Free Regular Tree Languages ⋮ COMPLEXITY IN UNION-FREE REGULAR LANGUAGES ⋮ 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 ⋮ ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION ⋮ Operational complexity: NFA-to-DFA trade-off ⋮ State complexity of operations on two-way finite automata over a unary alphabet ⋮ On the State Complexity of Operations on Two-Way Finite Automata ⋮ On the state complexity of operations on two-way finite automata ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ State complexity of union and intersection of square and reversal on \(k\) regular languages ⋮ 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 Combined Operations for Prefix-Free Regular Languages ⋮ State complexity of power ⋮ State complexity of unique rational operations ⋮ Descriptional complexity of regular languages ⋮ Square on Ideal, Closed and Free 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

Cites Work

• Unnamed Item
• Unnamed Item
• Finite automata and unary languages
• Intersection and union of regular languages and state complexity
• The state complexities of some basic operations on regular languages
• State complexity of some operations on binary regular languages
• The state complexity of \(\overline{\varSigma ^*\overline{L}}\) and its connection with temporal logic
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• Linear Automaton Transformations
• Implementation and Application of Automata

This page was built for publication: The state complexity of \(L^{2}\) and \(L^k\)