{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T14:00:07Z","timestamp":1725890407339},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642316227"},{"type":"electronic","value":"9783642316234"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31623-4_22","type":"book-chapter","created":{"date-parts":[[2012,7,9]],"date-time":"2012-07-09T05:03:34Z","timestamp":1341810214000},"page":"280-293","source":"Crossref","is-referenced-by-count":1,"title":["State Complexity of Projection and Quotient on Unranked Trees"],"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":[{"key":"22_CR1","unstructured":"Bach, E., Shallit, J.: Algorithmic number theory, vol.\u00a0I. MIT Press (1996)"},{"key":"22_CR2","unstructured":"Br\u00fcggemann-Klein, A., Murata, M., Wood, D.: Regular tree and regular hedge languages over unranked alphabets. HKUST Technical report (2001)"},{"key":"22_CR3","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, tata.gforge.inria.fr"},{"key":"22_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":"22_CR5","doi-asserted-by":"crossref","unstructured":"G\u00e9cseg, F., Steinby, M.: Tree languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.\u00a0III, pp. 1\u201368. Springer (1997)","DOI":"10.1007\/978-3-642-59126-6_1"},{"key":"22_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-642-02737-6_22","volume-title":"Developments in Language Theory","author":"H. Gruber","year":"2009","unstructured":"Gruber, H., Holzer, M.: Tight Bounds on the Descriptional Complexity of Regular Expressions. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol.\u00a05583, pp. 276\u2013287. Springer, Heidelberg (2009)"},{"key":"22_CR7","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. Internat. J. Foundations Comput. Sci.\u00a020, 563\u2013580 (2009)","journal-title":"Internat. J. Foundations Comput. Sci."},{"key":"22_CR8","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 \u2014 A survey. Inf. Comput.\u00a0209, 456\u2013470 (2011)","journal-title":"Inf. Comput."},{"key":"22_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1007\/978-3-642-22600-7_16","volume-title":"Proc. of DCFS 2011","author":"G. Jir\u00e1skov\u00e1","year":"2011","unstructured":"Jir\u00e1skov\u00e1, G., Masopust, T.: State Complexity of Projected Languages. In: Holzer, M., Kutrib, M., Pighizzini, G. (eds.) DCFS 2011. LNCS, vol.\u00a06808, pp. 198\u2013211. Springer, Heidelberg (2011)"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"Leung, H.: Descriptional complexity of NFA of different ambiguity. International Journal of Foundations of Computer Science\u00a0(16), 975\u2013984 (2005)","DOI":"10.1142\/S0129054105003418"},{"key":"22_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. J. Comput. System Sci.\u00a073, 550\u2013583 (2007)","journal-title":"J. Comput. System Sci."},{"key":"22_CR12","doi-asserted-by":"crossref","unstructured":"Neven, F.: Automata theory for XML researchers. SIGMOD Record\u00a0(31), 39\u201346 (2002)","DOI":"10.1145\/601858.601869"},{"key":"22_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1007\/978-3-642-15155-2_49","volume-title":"Mathematical Foundations of Computer Science 2010","author":"A. Okhotin","year":"2010","unstructured":"Okhotin, A.: Unambiguous Finite Automata over a Unary Alphabet. In: Hlin\u011bn\u00fd, P., Ku\u010dera, A. (eds.) MFCS 2010. LNCS, vol.\u00a06281, pp. 556\u2013567. Springer, Heidelberg (2010)"},{"key":"22_CR14","unstructured":"Piao, X.: State complexity of tree automata. PhD thesis, School of Computing, Queen\u2019s University (2011)"},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"Piao, X., Salomaa, K.: Transformations between different models of unranked bottom-up tree automata. Fundamenta Informaticae\u00a0(109), 405\u2013424 (2011)","DOI":"10.3233\/FI-2011-519"},{"key":"22_CR16","doi-asserted-by":"crossref","unstructured":"Piao, X., Salomaa, K.: State complexity of concatenation of regular tree languages. Theoretical Computer Science (accepted for publication), doi:10.1016\/j.tcs.2011.12.048","DOI":"10.1016\/j.tcs.2011.12.048"},{"key":"22_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/978-3-642-22600-7_21","volume-title":"DCFS 2011","author":"X. Piao","year":"2011","unstructured":"Piao, X., Salomaa, K.: State trade-offs in unranked tree automata. In: Holzer, M., Kutrib, M., Pighizzini, G. (eds.) DCFS 2011. LNCS, vol.\u00a06808, pp. 261\u2013274. Springer, Heidelberg (2011)"},{"key":"22_CR18","doi-asserted-by":"crossref","unstructured":"Piao, X., Salomaa, K.: Lower bounds for the size of deterministic unranked tree automata. Theoretical Computer Science, doi:10.1016\/j.tcs.2012.03.043","DOI":"10.1016\/j.tcs.2012.03.043"},{"key":"22_CR19","unstructured":"Raeymaekers, S., Bruynooghe, M.: Minimization of finite unranked tree automata (2004) (manuscript)"},{"key":"22_CR20","doi-asserted-by":"crossref","unstructured":"Rozenberg, G., Salomaa, A.: Handbook of Formal Languages, vol.\u00a0I\u2013III. Springer (1997)","DOI":"10.1007\/978-3-642-59126-6"},{"key":"22_CR21","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/j.jcss.2006.10.003","volume":"73","author":"T. Schwentick","year":"2007","unstructured":"Schwentick, T.: Automata for XML. J. Comput. System Sci.\u00a0(73), 289\u2013315 (2007)","journal-title":"J. Comput. System Sci"},{"key":"22_CR22","doi-asserted-by":"crossref","unstructured":"Schmidt, E.M.: Succinctness of descriptions of context-free, regular and finite languages. PhD thesis, Cornell University (1978)","DOI":"10.7146\/dpb.v7i84.6500"},{"key":"22_CR23","unstructured":"Wong, K.: On the complexity of projections of discrete-event systems. In: Proc. of WSDES, Cagliari, Italy, pp. 201\u2013206 (1998)"},{"key":"22_CR24","doi-asserted-by":"crossref","unstructured":"Yu, S.: Regular languages. In: [20], vol.\u00a0I, pp. 41\u2013110 (1997)","DOI":"10.1007\/978-3-642-59136-5_2"},{"key":"22_CR25","first-page":"471","volume":"64","author":"S. Yu","year":"2005","unstructured":"Yu, S.: State complexity: Recent results and open problems. Fundamenta Informaticae\u00a0(64), 471\u2013481 (2005)","journal-title":"Fundamenta Informaticae"},{"key":"22_CR26","doi-asserted-by":"crossref","unstructured":"Yu, S., Zhuang, Q., Salomaa, K.: The state complexity of some basic operations on regular languages. Theoretical Computer Science\u00a0(125), 315\u2013328 (1994)","DOI":"10.1016\/0304-3975(92)00011-F"}],"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-31623-4_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:40:38Z","timestamp":1620128438000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31623-4_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642316227","9783642316234"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31623-4_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}