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 Citation (Scopus)


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
Publication statusPublished - 2016 Sept 1

Bibliographical note

Publisher Copyright:
© 2016 World Scientific Publishing Company.

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)


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

Cite this