{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,16]],"date-time":"2024-02-16T15:39:51Z","timestamp":1708097991402},"reference-count":17,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2016,12]]},"abstract":"<jats:p>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\u2032 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.<\/jats:p>","DOI":"10.1142\/s0129054116500398","type":"journal-article","created":{"date-parts":[[2017,2,20]],"date-time":"2017-02-20T08:57:57Z","timestamp":1487581077000},"page":"965-979","source":"Crossref","is-referenced-by-count":1,"title":["State Complexity of Regular Tree Languages for Tree Matching"],"prefix":"10.1142","volume":"27","author":[{"given":"Sang-Ki","family":"Ko","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Liverpool, Ashton Street, Liverpool, L69 3BX, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ha-Rim","family":"Lee","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Yonsei University, 50 Yonsei-Ro, Seodaemun-Gu, Seoul 120-749, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yo-Sub","family":"Han","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Yonsei University, 50 Yonsei-Ro, Seodaemun-Gu, Seoul 120-749, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2017,2,20]]},"reference":[{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.03.026"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.06.003"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.046"},{"issue":"1","key":"p_7","first-page":"75","volume":"83","author":"Gao Y.","year":"2008","journal-title":"Fundamenta Informaticae"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1145\/322290.322295"},{"key":"p_12","first-page":"111","author":"Kutrib M.","year":"2013","journal-title":"Bulletin of the EATCS"},{"key":"p_13","first-page":"321","volume":"9","author":"Lupanov O.","year":"1963","journal-title":"Problemy Kibernet"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.021"},{"key":"p_15","first-page":"1373","volume":"11","author":"Maslov A.","year":"1970","journal-title":"Soviet Mathematics Doklady"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1971.223108"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1145\/601858.601869"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539789164078"},{"issue":"4","key":"p_21","doi-asserted-by":"crossref","first-page":"405","DOI":"10.3233\/FI-2011-519","volume":"109","author":"Piao X.","year":"2011","journal-title":"Fundamenta Informaticae"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.12.048"},{"key":"p_24","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.04.015"},{"key":"p_25","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054107004917"},{"key":"p_27","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)00011-F"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054116500398","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,2]],"date-time":"2020-10-02T18:12:18Z","timestamp":1601662338000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054116500398"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12]]},"references-count":17,"journal-issue":{"issue":"08","published-online":{"date-parts":[[2017,2,20]]},"published-print":{"date-parts":[[2016,12]]}},"alternative-id":["10.1142\/S0129054116500398"],"URL":"https:\/\/doi.org\/10.1142\/s0129054116500398","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12]]}}}