The state complexity of L^2 and L^k

DOI10.1016/J.IPL.2005.06.011zbMATH Open1187.68298OpenAlexW1482663448MaRDI QIDQ844206FDOQ844206

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

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

zbMATH Keywords

formal languagesstate complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

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

Cited In (25)

• 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
• Square on Ideal, Closed and Free Languages
• Title not available (Why is that?)
• State Complexity of Operations on Two-Way Deterministic Finite Automata over a Unary Alphabet
• State Complexity of Combined Operations for Prefix-Free Regular Languages
• State complexity of power
• State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages
• Operational State Complexity of Subtree-Free Regular Tree Languages
• State complexity of union and intersection of square and reversal on \(k\) regular languages
• Square on Deterministic, Alternating, and Boolean Finite Automata
• Investigations on Automata and Languages Over a Unary Alphabet
• State complexity of deletion and bipolar deletion
• State complexity of operations on two-way finite automata over a unary alphabet
• Operational complexity: NFA-to-DFA trade-off
• State complexity of operations on input-driven pushdown automata
• State complexity of unique rational operations
• STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-UNION AND CATENATION-INTERSECTION
• 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
• Operations on Permutation Automata
• Complexity in union-free regular languages
• On the state complexity of operations on two-way finite automata

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)