Operational State Complexity of Subtree-Free Regular Tree Languages

DOI10.1142/S0129054116500246zbMath1351.68142OpenAlexW2551941547MaRDI QIDQ5298309

Sang-Ki Ko, Yo-Sub Han, Hae-Sung Eom

Publication date: 14 December 2016

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

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

zbMATH Keywords

state complexitydeterministic ranked tree automatasubtree-free regular tree languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• State complexity of star of union and square of union on \textit{k} regular languages
• State complexity of combined operations for suffix-free regular languages
• State complexity of the concatenation of regular tree 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
• 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 k-Union and k-Intersection for Prefix-Free Regular Languages
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION

This page was built for publication: Operational State Complexity of Subtree-Free Regular Tree Languages