State complexity of union and intersection of square and reversal on k regular languages

DOI10.1016/J.TCS.2012.03.046MaRDI QIDQ714820zbMATH OpenOpenAlexFDO

Authors Yuan Gao, Lila Kari, Sheng Yu

Publication date 11 October 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.03.046

zbMATH Keywords

finite automataregular languagescombined operationsstate complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• State complexity of star and square of union of \(k\) regular languages
• State complexity of star of union and square of union on \textit{k} regular languages
• State complexity of combined operations with union, intersection, star and reversal
• State complexity of four combined operations composed of union, intersection, star and reversal
• State complexity of union and intersection of star on \(k\) regular languages

Cites work

• scientific article; zbMATH DE number 1962776 (Why is no real title available?)
• scientific article; zbMATH DE number 2068872 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 1916664 (Why is no real title available?)
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• Estimation of state complexity of combined operations
• On the state complexity of star of union and star of intersection
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• State complexity of basic language operations combined with reversal
• State complexity of combined operations
• State complexity of four combined operations composed of union, intersection, star and reversal
• State complexity of power
• State complexity of regular languages
• State complexity of some operations on binary regular languages
• State complexity of two combined operations: catenation-star and catenation-reversal
• State complexity of two combined operations: catenation-union and catenation-intersection
• The state complexities of some basic operations on regular languages
• The state complexity of \(L^{2}\) and \(L^k\)
• The state complexity of two combined operations: star of catenation and star of reversal
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• Undecidability of the state complexity of composed regular operations

Cited in

(8)

• State complexity of star of union and square of union on \textit{k} regular languages
• State complexity of union and intersection of star on \(k\) regular languages
• On the state complexity of reversals of regular languages
• State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages
• State complexity of star and square of union of \(k\) regular languages
• State complexity of regular tree languages for tree matching
• Operational state complexity of subtree-free regular tree languages
• On the gap between separating words and separating their reversals

This page was built for publication: State complexity of union and intersection of square and reversal on \(k\) regular languages

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