State Complexity of Regular Tree Languages for Tree Matching

Sang Ki Ko; Ha Rim Lee; Yo Sub Han

doi:10.1142/S0129054116500398

State Complexity of Regular Tree Languages for Tree Matching

Sang Ki Ko, Ha Rim Lee, Yo Sub Han

Department of Artificial Intelligence

Yonsei University

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

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 language	English
Pages (from-to)	965-979
Number of pages	15
Journal	International Journal of Foundations of Computer Science
Volume	27
Issue number	8
DOIs	https://doi.org/10.1142/S0129054116500398
State	Published - 1 Dec 2016

Keywords

State complexity
path-closed languages
regular tree languages
tree matching

Access to Document

10.1142/S0129054116500398

Cite this

@article{089d55264de64a40b9fdea8c7e2dcd12,

title = "State Complexity of Regular Tree Languages for Tree Matching",

abstract = "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.",

keywords = "State complexity, path-closed languages, regular tree languages, tree matching",

author = "Ko, {Sang Ki} and Lee, {Ha Rim} and Han, {Yo Sub}",

note = "Publisher Copyright: {\textcopyright} 2016 World Scientific Publishing Company.",

year = "2016",

month = dec,

day = "1",

doi = "10.1142/S0129054116500398",

language = "English",

volume = "27",

pages = "965--979",

journal = "International Journal of Foundations of Computer Science",

issn = "0129-0541",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "8",

}

TY - JOUR

T1 - State Complexity of Regular Tree Languages for Tree Matching

AU - Ko, Sang Ki

AU - Lee, Ha Rim

AU - Han, Yo Sub

PY - 2016/12/1

Y1 - 2016/12/1

N2 - 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.

AB - 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.

KW - State complexity

KW - path-closed languages

KW - regular tree languages

KW - tree matching

UR - http://www.scopus.com/inward/record.url?scp=85013422174&partnerID=8YFLogxK

U2 - 10.1142/S0129054116500398

DO - 10.1142/S0129054116500398

M3 - Article

AN - SCOPUS:85013422174

SN - 0129-0541

VL - 27

SP - 965

EP - 979

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

IS - 8

ER -

State Complexity of Regular Tree Languages for Tree Matching

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this