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

DOI10.1016/j.ipl.2005.06.011zbMath1187.68298MaRDI 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 languages; state complexity

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

Operations on Permutation Automata, State Complexity of Operations on Two-Way Deterministic Finite Automata over a Unary Alphabet, Square on Deterministic, Alternating, and Boolean Finite Automata, State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages, Operational State Complexity of Subtree-Free Regular Tree Languages, Square on Ideal, Closed and Free Languages, Investigations on Automata and Languages Over a Unary Alphabet, State complexity of deletion and bipolar deletion, Operational complexity: NFA-to-DFA trade-off, State complexity of star of union and square of union on \textit{k} regular languages, State complexity of operations on two-way finite automata over a unary alphabet, 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, State complexity of power, State complexity of unique rational operations, Descriptional complexity of regular languages, State complexity of unambiguous operations on finite automata, State complexity of operations on input-driven pushdown automata, Undecidability of state complexity, COMPLEXITY IN UNION-FREE REGULAR LANGUAGES, STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-UNION AND CATENATION-INTERSECTION, ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION, On the State Complexity of Operations on Two-Way Finite Automata, State Complexity of Combined Operations 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