{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T23:35:14Z","timestamp":1743032114454,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642225994"},{"type":"electronic","value":"9783642226007"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22600-7_21","type":"book-chapter","created":{"date-parts":[[2011,7,19]],"date-time":"2011-07-19T20:58:15Z","timestamp":1311109095000},"page":"261-274","source":"Crossref","is-referenced-by-count":4,"title":["State Trade-Offs in Unranked Tree Automata"],"prefix":"10.1007","author":[{"given":"Xiaoxue","family":"Piao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"unstructured":"Br\u00fcggemann-Klein, A., Murata, M., Wood, D.: Regular tree and hedge languages over unranked alphabets. HKUST Research Report, HKUST-TCSC-2001-05, http:\/\/hdl.handle.net\/1783.1\/738","key":"21_CR1"},{"key":"21_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/978-3-540-25979-4_8","volume-title":"Rewriting Techniques and Applications","author":"J. Carme","year":"2004","unstructured":"Carme, J., Niehren, J., Tommasi, M.: Querying unranked trees with stepwise tree automata. In: van Oostrom, V. (ed.) RTA 2004. LNCS, vol.\u00a03091, pp. 105\u2013118. Springer, Heidelberg (2004)"},{"unstructured":"Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., L\u00f6ding, C., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications (2007), electronic book available at tata.gforge.inria.fr","key":"21_CR3"},{"key":"21_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/11537311_7","volume-title":"Fundamentals of Computation Theory","author":"J. Cristau","year":"2005","unstructured":"Cristau, J., L\u00f6ding, C., Thomas, W.: Deterministic automata on unranked trees. In: Li\u015bkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol.\u00a03623, pp. 68\u201379. Springer, Heidelberg (2005)"},{"key":"21_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-59126-6_1","volume-title":"Handbook of Formal Languages","author":"F. G\u00e9cseg","year":"1997","unstructured":"G\u00e9cseg, F., Steinby, M.: Tree languages. In: Handbook of Formal Languages, vol.\u00a0III, pp. 1\u201368. Springer, Heidelberg (1997)"},{"key":"21_CR6","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1142\/S0129054103002199","volume":"14","author":"M. Holzer","year":"2003","unstructured":"Holzer, M., Kutrib, M.: Nondeterministic descriptional complexity of regular languages. International Journal of Foundations of Computer Science\u00a014, 1087\u20131102 (2003)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"21_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-3-642-00982-2_3","volume-title":"Language and Automata Theory and Applications","author":"M. Holzer","year":"2009","unstructured":"Holzer, M., Kutrib, M.: Descriptional and computational complexity of finite automata. In: Dediu, A.H., Ionescu, A.M., Mart\u00edn-Vide, C. (eds.) LATA 2009. LNCS, vol.\u00a05457, pp. 23\u201342. Springer, Heidelberg (2009)"},{"issue":"4","key":"21_CR8","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1142\/S0129054109006747","volume":"20","author":"M. Holzer","year":"2009","unstructured":"Holzer, M., Kutrib, M.: Nondeterministic finite automata \u2013 Recent results on the descriptional and computational complexity. International Journal of Foundations of Computer Science\u00a020(4), 563\u2013580 (2009)","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"4","key":"21_CR9","first-page":"453","volume":"6","author":"M. Holzer","year":"2001","unstructured":"Holzer, M., Salomaa, K., Yu, S.: On the state complexity of k-entry deterministic finite automata. Journal of Automata, Languages and Combinatorics\u00a06(4), 453\u2013466 (2001)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"issue":"4","key":"21_CR10","doi-asserted-by":"publisher","first-page":"270","DOI":"10.2307\/2690532","volume":"69","author":"F.E. Krause","year":"1996","unstructured":"Krause, F.E.: Maximizing the product of summands; minimizing the sum of factors. Mathematics Magazine\u00a069(4), 270\u2013278 (1996)","journal-title":"Mathematics Magazine"},{"key":"21_CR11","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1016\/j.jcss.2006.10.021","volume":"73","author":"W. Martens","year":"2007","unstructured":"Martens, W., Niehren, J.: On the minimization of XML schemas and tree automata for unranked trees. Journal of Computer and System Sciences\u00a073, 550\u2013583 (2007)","journal-title":"Journal of Computer and System Sciences"},{"key":"21_CR12","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"20","author":"F.R. Moore","year":"1971","unstructured":"Moore, F.R.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Transactions on Computers\u00a020, 1211\u20131214 (1971)","journal-title":"IEEE Transactions on Computers"},{"key":"21_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-21254-3_33","volume-title":"Language and Automata Theory and Applications","author":"A. Okhotin","year":"2011","unstructured":"Okhotin, A., Salomaa, K.: Descriptional complexity of unambiguous nested word automata. In: Dediu, A.-H., Inenaga, S., Mart\u00edn-Vide, C. (eds.) LATA 2011. LNCS, vol.\u00a06638. Springer, Heidelberg (to appear, 2011)"},{"key":"21_CR14","doi-asserted-by":"publisher","first-page":"3290","DOI":"10.1016\/j.tcs.2009.05.002","volume":"410","author":"X. Piao","year":"2009","unstructured":"Piao, X., Salomaa, K.: Operational state complexity of nested word automata. Theoretical Computer Science\u00a0410, 3290\u20133302 (2009)","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Piao, X., Salomaa, K.: Transformations between different models of unranked bottom-up tree automata. In: Proc. of DCFS 2010, pp. 193\u2013204 (2010);","key":"#cr-split#-21_CR15.1","DOI":"10.4204\/EPTCS.31.18"},{"unstructured":"Full version to appear in Fundamenta Informaticae","key":"#cr-split#-21_CR15.2"},{"doi-asserted-by":"crossref","unstructured":"Piao, X., Salomaa, K.: Operational state complexity of deterministic unranked tree automata. In: Proc. of DCFS 2010, pp. 181\u2013192 (2010)","key":"21_CR16","DOI":"10.4204\/EPTCS.31.17"},{"unstructured":"Raeymaekers, S., Bruynooghe, M.: Minimization of finite unranked tree automata (2004) (manuscript)","key":"21_CR17"},{"key":"21_CR18","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/j.jcss.2006.10.003","volume":"73","author":"T. Schwentick","year":"2007","unstructured":"Schwentick, T.: Automata for XML,\u2013 a survey. Journal of Computer and System Sciences\u00a073, 289\u2013315 (2007)","journal-title":"Journal of Computer and System Sciences"},{"key":"21_CR19","volume-title":"A Second Course in Formal Languages and Automata Theory","author":"J. Shallit","year":"2009","unstructured":"Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press, Cambridge (2009)"},{"key":"21_CR20","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-59136-5_2","volume-title":"Handbook of Formal Languages","author":"S. Yu","year":"1997","unstructured":"Yu, S.: Regular languages. In: Handbook of Formal Languages, vol.\u00a0I, pp. 41\u2013110. Springer, Heidelberg (1997)"}],"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-642-22600-7_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T00:09:22Z","timestamp":1560384562000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22600-7_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642225994","9783642226007"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22600-7_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}