State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages

DOI10.1142/S0129054115500124MaRDI QIDQ5261608zbMATH OpenOpenAlexFDO

Authors Hae-Sung Eom, Yo-Sub Han, Kai Salomaa

Publication date 6 July 2015

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054115500124

zbMATH Keywords

state complexityprefix-free regular languages\(k\)-intersection\(k\)-union

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• State complexity of \(k\)-union and \(k\)-intersection for prefix-free regular languages
• Intersection and union of regular languages and state complexity
• STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES
• State Complexity of Union and Intersection of Finite Languages
• Operational union-complexity
• State Complexity of Combined Operations for Prefix-Free Regular Languages
• Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
• State complexity of four combined operations composed of union, intersection, star and reversal
• On state complexity of finite word and tree languages
• State complexity of combined operations for suffix-free regular languages

Cites work

• Complexity in union-free regular languages
• Estimation of state complexity of combined operations
• IMPROVED BOUNDS ON THE NUMBER OF AUTOMATA ACCEPTING FINITE LANGUAGES
• ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION
• On the state complexity of reversals of regular languages
• Reversal of binary regular languages
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES
• State complexity of basic operations on suffix-free regular languages
• State complexity of combined operations
• State complexity of power
• State complexity of star of union and square of union on \textit{k} regular languages
• State complexity of union and intersection of square and reversal on \(k\) regular languages
• The state complexities of some basic operations on regular languages
• The state complexity of \(L^{2}\) and \(L^k\)
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION

Cited in

(7)

• State complexity of union and intersection of star on \(k\) regular languages
• A pumping lemma for regular closure of prefix-free languages
• State Complexity of Union and Intersection of Finite Languages
• 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 for Two-way Nondeterministic Finite Automata
• State complexity of union and intersection on graph-walking automata

This page was built for publication: State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages

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