{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,12]],"date-time":"2026-11-12T10:52:09Z","timestamp":1794480729898,"version":"4.9.1"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319097039","type":"print"},{"value":"9783319097046","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-09704-6_22","type":"book-chapter","created":{"date-parts":[[2014,7,11]],"date-time":"2014-07-11T05:43:21Z","timestamp":1405057401000},"page":"246-257","source":"Crossref","is-referenced-by-count":0,"title":["State Complexity of Regular Tree Languages for Tree Pattern Matching"],"prefix":"10.1007","author":[{"given":"Sang-Ki","family":"Ko","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ha-Rim","family":"Lee","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yo-Sub","family":"Han","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"22_CR1","unstructured":"Comon, H., Dauchet, M., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications (2007), Electronic book available at http:\/\/www.tata.gforge.inria.fr"},{"key":"22_CR2","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/978-3-662-07675-0_9","volume-title":"Handbook of Formal Languages","author":"Maxime Crochemore","year":"1997","unstructured":"Crochemore, M., Hancart, C.: Automata for Matching Patterns. In: Handbook of formal languages, vol.\u00a02, pp. 399\u2013462 (1997)"},{"key":"22_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/978-3-642-39310-5_8","volume-title":"Descriptional Complexity of Formal Systems","author":"H.-S. Eom","year":"2013","unstructured":"Eom, H.-S., Han, Y.-S., Ko, S.-K.: State complexity of subtree-free regular tree languages. In: Jurgensen, H., Reis, R. (eds.) DCFS 2013. LNCS, vol.\u00a08031, pp. 66\u201377. Springer, Heidelberg (2013)"},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"G\u00e9cseg, F., Steinby, M.: Tree languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages. Beyond Words, vol.\u00a03, pp. 1\u201368. Springer-Verlag New York, Inc., (1997)","DOI":"10.1007\/978-3-642-59126-6_1"},{"issue":"1","key":"22_CR5","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1145\/322290.322295","volume":"29","author":"C.M. Hoffmann","year":"1982","unstructured":"Hoffmann, C.M., O\u2019Donnell, M.J.: Pattern matching in trees. Journal of the ACM\u00a029(1), 68\u201395 (1982)","journal-title":"Journal of the ACM"},{"key":"22_CR6","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/j.ic.2010.11.013","volume":"209","author":"M. Holzer","year":"2011","unstructured":"Holzer, M., Kutrib, M.: Descriptional and computational complexity of finite automata \u2013 a survey. Information and Computation\u00a0209, 456\u2013470 (2011)","journal-title":"Information and Computation"},{"key":"22_CR7","first-page":"70","volume":"111","author":"M. Kutrib","year":"2013","unstructured":"Kutrib, M., Pighizzini, G.: Recent trends in descriptional complexity of formal languages. Bulletin of the EATCS\u00a0111, 70\u201386 (2013)","journal-title":"Bulletin of the EATCS"},{"key":"22_CR8","first-page":"328","volume":"9","author":"O. Lupanov","year":"1963","unstructured":"Lupanov, O.: A comparison of two types of finite sources. Problemy Kibernetiki\u00a09, 328\u2013335 (1963)","journal-title":"Problemy Kibernetiki"},{"key":"22_CR9","first-page":"1373","volume":"11","author":"A. Maslov","year":"1970","unstructured":"Maslov, A.: Estimates of the number of states of finite automata. Soviet Mathematics Doklady\u00a011, 1373\u20131375 (1970)","journal-title":"Soviet Mathematics Doklady"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"Meyer, A., Fisher, M.: Economy of description by automata, grammars and formal systems. In: Proceedings of the 12th Annual Symposium on Switching and Automata Theory, pp. 188\u2013191 (1971)","DOI":"10.1109\/SWAT.1971.11"},{"issue":"10","key":"22_CR11","doi-asserted-by":"crossref","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"C-20","author":"F.R. Moore","year":"1971","unstructured":"Moore, F.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic and two-way finite automata. IEEE Transactions on Computers\u00a0C-20, 1211\u20131214 (1971)","journal-title":"IEEE Transactions on Computers"},{"issue":"3","key":"22_CR12","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1145\/601858.601869","volume":"31","author":"F. Neven","year":"2002","unstructured":"Neven, F.: Automata theory for XML researchers. ACM SIGMOD Record\u00a031(3), 39\u201346 (2002)","journal-title":"ACM SIGMOD Record"},{"issue":"1","key":"22_CR13","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1137\/S0097539789164078","volume":"26","author":"M. Nivat","year":"1997","unstructured":"Nivat, M., Podelski, A.: Minimal ascending and descending tree automata. SIAM Journal on Computing\u00a026(1), 39\u201358 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"22_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/978-3-642-22600-7_21","volume-title":"Descriptional Complexity of Formal Systems","author":"X. Piao","year":"2011","unstructured":"Piao, X., Salomaa, K.: State trade-offs in unranked tree automata. In: Holzer, M., Pighizzini, G., kutrib, M. (eds.) DCFS 2011. LNCS, vol.\u00a06808, pp. 261\u2013274. Springer, Heidelberg (2011)"},{"issue":"4","key":"22_CR15","doi-asserted-by":"crossref","first-page":"405","DOI":"10.3233\/FI-2011-519","volume":"109","author":"X. Piao","year":"2011","unstructured":"Piao, X., Salomaa, K.: Transformations between different models of unranked bottom-up tree automata. Fundamenta Informaticae\u00a0109(4), 405\u2013424 (2011)","journal-title":"Fundamenta Informaticae"},{"key":"22_CR16","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1007\/978-3-642-27654-5_30","volume-title":"Computation, Physics and Beyond","author":"Xiaoxue Piao","year":"2012","unstructured":"Piao, X., Salomaa, K.: State complexity of Kleene-star operations on trees. In: Dinneen, M.J., Khoussainov, B., Nies, A. (eds.) WTCS 2012 (Calude Festschrift). LNCS, vol.\u00a07160, pp. 388\u2013402. Springer, Heidelberg (2012)"},{"key":"22_CR17","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/j.tcs.2011.12.048","volume":"429","author":"X. Piao","year":"2012","unstructured":"Piao, X., Salomaa, K.: State complexity of the concatenation of regular tree languages. Theoretical Computer Science\u00a0429, 273\u2013281 (2012)","journal-title":"Theoretical Computer Science"},{"key":"22_CR18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511808876","volume-title":"A Second Course in Formal Languages and Automata Theory","author":"J. Shallit","year":"2008","unstructured":"Shallit, J.: A Second Course in Formal Languages and Automata Theory, 1st edn. Cambridge University Press, New York (2008)","edition":"1"},{"issue":"2","key":"22_CR19","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(92)00011-F","volume":"125","author":"S. Yu","year":"1994","unstructured":"Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations on regular languages. Theoretical Computer Science\u00a0125(2), 315\u2013328 (1994)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-09704-6_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,22]],"date-time":"2020-08-22T02:00:08Z","timestamp":1598061608000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-09704-6_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319097039","9783319097046"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-09704-6_22","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-319-09704-6","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}