Operational State Complexity of Subtree-Free Regular Tree Languages

Sang Ki Ko, Hae Sung Eom, Yo Sub Han

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


We introduce subtree-free regular tree languages that are closely related to XML schemas and investigate the state complexity of basic operations on subtree-free regular tree languages. The state complexity of an operation for regular tree languages is the number of states that are sufficient and necessary in the worst-case for the minimal deterministic ranked tree automaton that accepts the tree language obtained from the operation. We establish the precise state complexity of (sequential, parallel) concatenation, (bottom-up, top-down) star, intersection and union for subtree-free regular tree languages.

Original languageEnglish
Pages (from-to)705-724
Number of pages20
JournalInternational Journal of Foundations of Computer Science
Issue number6
StatePublished - 1 Sep 2016


  • Deterministic ranked tree automata
  • state complexity
  • subtree-free regular tree languages


Dive into the research topics of 'Operational State Complexity of Subtree-Free Regular Tree Languages'. Together they form a unique fingerprint.

Cite this