@inproceedings{f4a6fa47e93d48e8a3056c381ff633c4,
title = "State complexity of regular tree languages for tree pattern 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 = "regular tree languages, state complexity, tree automata, tree pattern matching",
author = "Ko, {Sang Ki} and Lee, {Ha Rim} and Han, {Yo Sub}",
year = "2014",
doi = "10.1007/978-3-319-09704-6_22",
language = "English",
isbn = "9783319097039",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "246--257",
booktitle = "Descriptional Complexity of Formal Systems - 16th International Workshop, DCFS 2014, Proceedings",
address = "Germany",
note = "16th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2014 ; Conference date: 05-08-2014 Through 08-08-2014",
}