{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T14:36:00Z","timestamp":1648737360528},"reference-count":24,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1142\/s0129054116500246","type":"journal-article","created":{"date-parts":[[2016,11,15]],"date-time":"2016-11-15T08:52:57Z","timestamp":1479199977000},"page":"705-724","source":"Crossref","is-referenced-by-count":0,"title":["Operational State Complexity of Subtree-Free Regular Tree Languages"],"prefix":"10.1142","volume":"27","author":[{"given":"Sang-Ki","family":"Ko","sequence":"first","affiliation":[{"name":"Department of Computer Science, Yonsei University, 50, Yonsei-Ro, Seodaemun-Gu, Seoul 120-749, Republic of Korea"}]},{"given":"Hae-Sung","family":"Eom","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Yonsei University, 50, Yonsei-Ro, Seodaemun-Gu, Seoul 120-749, Republic of Korea"}]},{"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"}]}],"member":"219","published-online":{"date-parts":[[2016,11,15]]},"reference":[{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.02.025"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.09.014"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1142\/s0129054115500124"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.03.026"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.06.003"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.046"},{"issue":"1","key":"p_11","first-page":"75","volume":"83","author":"Gao Y.","year":"2008","journal-title":"Fundamenta Informaticae"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054108005838"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.054"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105003133"},{"key":"p_20","first-page":"1373","volume":"11","author":"Maslov A.","year":"1970","journal-title":"Soviet Mathematics Doklady"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1145\/1111627.1111631"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1958-0135681-9"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1145\/601858.601869"},{"issue":"4","key":"p_26","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_27","first-page":"388","author":"Piao X.","year":"2012","journal-title":"Physics and Beyond"},{"key":"p_28","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.12.048"},{"key":"p_29","doi-asserted-by":"publisher","DOI":"10.1142\/S012905410200100X"},{"key":"p_30","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0114"},{"key":"p_31","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.06.011"},{"key":"p_32","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.04.015"},{"key":"p_33","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054107004917"},{"issue":"2","key":"p_35","first-page":"221","volume":"6","author":"Yu S.","year":"2001","journal-title":"Languages and Combinatorics"},{"key":"p_36","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\/S0129054116500246","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,27]],"date-time":"2020-09-27T09:08:04Z","timestamp":1601197684000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054116500246"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9]]},"references-count":24,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2016,11,15]]},"published-print":{"date-parts":[[2016,9]]}},"alternative-id":["10.1142\/S0129054116500246"],"URL":"https:\/\/doi.org\/10.1142\/s0129054116500246","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9]]}}}