State Complexity of Regular Tree Languages for Tree Matching

Sang Ki Ko, Ha Rim Lee, Yo Sub Han

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


We study the state complexity of regular tree languages for tree matching problem. Given a tree t and a set of pattern trees L, we can decide whether or not there exists a subtree occurrence of trees in L from the tree t by considering the new language L′ which accepts all trees containing trees in L as subtrees. We consider the case when we are given a set of pattern trees as a regular tree language and investigate the state complexity. Based on the sequential and parallel tree concatenation, we define three types of tree languages for deciding the existence of different types of subtree occurrences. We also study the deterministic top-down state complexity of path-closed languages for the same problem.

Original languageEnglish
Pages (from-to)965-979
Number of pages15
JournalInternational Journal of Foundations of Computer Science
Issue number8
Publication statusPublished - 2016 Dec 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 'State Complexity of Regular Tree Languages for Tree Matching'. Together they form a unique fingerprint.

Cite this