The state complexity of L^2 and L^k

DOI10.1016/J.IPL.2005.06.011MaRDI QIDQ844206zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 2182451
• State complexity and approximation
• State complexity research and approximation
• State complexity and limited nondeterminism
• ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION
• Implementation and Application of Automata
• scientific article; zbMATH DE number 7301304
• On the State Complexity of Combined Operations
• scientific article; zbMATH DE number 7453075
• scientific article; zbMATH DE number 1773091

Cites work

• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Finite automata and unary languages
• Implementation and Application of Automata
• Intersection and union of regular languages and state complexity
• Linear Automaton Transformations
• State complexity of some operations on binary regular languages
• The state complexities of some basic operations on 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

Cited in

(29)

• State complexity of star of union and square of union on \textit{k} regular languages
• On the State Complexity of Operations on Two-Way Finite Automata
• scientific article; zbMATH DE number 1747444 (Why is no real title available?)
• State complexity of power
• State Complexity of Combined Operations for Prefix-Free Regular Languages
• State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages
• State complexity of union and intersection of square and reversal on \(k\) regular languages
• Square on Deterministic, Alternating, and Boolean Finite Automata
• State complexity of two combined operations: catenation-union and catenation-intersection
• State complexity of deletion and bipolar deletion
• On the state complexity of scattered substrings and superstrings
• State complexity of operations on two-way finite automata over a unary alphabet
• Square on ideal, closed and free languages
• State complexity of operations on input-driven pushdown automata
• Operational complexity: NFA-to-DFA trade-off
• State complexity of operations on two-way deterministic finite automata over a unary alphabet
• Operational complexity: NFA-to-DFA trade-off
• State complexity of unique rational operations
• Operational state complexity of subtree-free regular tree languages
• Investigations on automata and languages over a unary alphabet
• The state complexity of random DFAs
• Square, power, positive closure, and complementation on ordered and star-free languages
• ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION
• Descriptional complexity of regular languages
• State complexity of unambiguous operations on finite automata
• Undecidability of state complexity
• On the state complexity of operations on two-way finite automata
• Operations on Permutation Automata
• Complexity in union-free regular languages

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q844206)