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

DOI10.1142/s0129054115500124zbMath1327.68155OpenAlexW2178095809MaRDI QIDQ5261608

Yo-Sub Han, Hae-Sung Eom, 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)

Related Items

Operational State Complexity of Subtree-Free Regular Tree Languages, A pumping lemma for regular closure of prefix-free languages

Cites Work

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