{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T05:26:25Z","timestamp":1737523585292,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540763352"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-76336-9_11","type":"book-chapter","created":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T05:44:48Z","timestamp":1193463888000},"page":"97-108","source":"Crossref","is-referenced-by-count":0,"title":["Deterministic Caterpillar Expressions"],"prefix":"10.1007","author":[{"given":"Kai","family":"Salomaa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sheng","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jinfeng","family":"Zan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","volume-title":"Theory of Codes","author":"J. Berstel","year":"1985","unstructured":"Berstel, J., Perrin, D.: Theory of Codes. Academic Press, Inc., London (1985)"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.tcs.2005.10.031","volume":"350","author":"M. Boja\u0144czyk","year":"2006","unstructured":"Boja\u0144czyk, M., Colcombet, T.: Tree walking automata cannot be determinized. Theoret. Comput. Sci.\u00a0350, 164\u2013173 (2006)","journal-title":"Theoret. Comput. Sci."},{"key":"11_CR3","first-page":"234","volume-title":"Proceedings of STOC 2005","author":"M. Boja\u0144czyk","year":"2005","unstructured":"Boja\u0144czyk, M., Colcombet, T.: Tree-walking automata do not recognize all regular languages. In: Proceedings of STOC 2005, pp. 234\u2013243. ACM Press, New York (2005)"},{"key":"11_CR4","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1109\/T-C.1971.223204","volume":"20","author":"R.V. Book","year":"1971","unstructured":"Book, R.V., Even, S., Greibach, S., Ott, G.: Ambiguity in graphs and expressions. IEEE Trans. on Computers\u00a020, 149\u2013153 (1971)","journal-title":"IEEE Trans. on Computers"},{"key":"11_CR5","unstructured":"Br\u00fcggemann-Klein, A., Murata, M., Wood, D.: Regular tree and regular hedge languages over unranked alphabets. Technical Report HKUST-TCSC-2001-0, The Hongkong University of Science and Technology (2001)"},{"key":"11_CR6","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1006\/inco.1997.2695","volume":"142","author":"A. Br\u00fcggemann-Klein","year":"1998","unstructured":"Br\u00fcggemann-Klein, A., Wood, D.: One-unambiguous regular languages. Inform. Computation\u00a0142, 182\u2013206 (1998)","journal-title":"Inform. Computation"},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1162\/109966200750410613","volume":"2","author":"A. Br\u00fcggemann-Klein","year":"2000","unstructured":"Br\u00fcggemann-Klein, A., Wood, D.: Caterpillars: A context-specification technique. Mark-up Languages: Theory & Practice\u00a02, 81\u2013106 (2000)","journal-title":"Mark-up Languages: Theory & Practice"},{"key":"11_CR8","first-page":"270","volume-title":"DLT 1999","author":"A. Br\u00fcggemann-Klein","year":"2000","unstructured":"Br\u00fcggemann-Klein, A., Wood, D.: Caterpillars, context, tree automata and tree pattern matching. In: Rozenberg, G., Thomas, W. (eds.) DLT 1999, pp. 270\u2013285. World Scientific, Singapore (2000)"},{"key":"11_CR9","unstructured":"Comon, H., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications (1997), http:\/\/www.grappa.univ-lille3.fr\/tata"},{"key":"11_CR10","volume-title":"Automata, Languages, and Machines","author":"S. Eilenberg","year":"1974","unstructured":"Eilenberg, S.: Automata, Languages, and Machines, vol.\u00a0A. Academic Press, New York (1974)"},{"key":"11_CR11","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1007\/978-3-642-60207-8_7","volume-title":"Jewels are forever","author":"J. Engelfriet","year":"1999","unstructured":"Engelfriet, J., Hoogeboom, H.J.: Tree-walking pebble automata. In: Karhum\u00e4ki, J., Maurer, H., P\u01ceun, Gh., Rozenberg, G. (eds.) Jewels are forever, pp. 72\u201383. Springer, Heidelberg (1999)"},{"key":"11_CR12","first-page":"51","volume":"14","author":"J. Engelfriet","year":"1999","unstructured":"Engelfriet, J., Hoogeboom, H.J., van Best, J.P.: Trips on trees. Acta Cybern.\u00a014, 51\u201364 (1999)","journal-title":"Acta Cybern."},{"key":"11_CR13","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/3-540-44596-X_7","volume-title":"Machine Learning and Data Mining in Pattern Recognition","author":"H. Fernau","year":"2001","unstructured":"Fernau, H.: Learning XML grammars. In: Perner, P. (ed.) MLDM 2001. LNCS (LNAI), vol.\u00a02123, pp. 73\u201387. Springer, Heidelberg (2001)"},{"key":"11_CR14","first-page":"1","volume-title":"Handbook of Formal Languages","author":"F. G\u00e9cseg","year":"1997","unstructured":"G\u00e9cseg, F., Steinby, M.: Tree languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.\u00a03, pp. 1\u201368. Springer, Heidelberg (1997)"},{"key":"11_CR15","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/S0022-0000(03)00036-9","volume":"66","author":"V. Geffert","year":"2003","unstructured":"Geffert, V.: Translation of binary regular expressions into nondeterministic \u03b5-free automata with O(n logn) transitions. J. Comput. System Sci.\u00a066, 451\u2013472 (2003)","journal-title":"J. Comput. System Sci."},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1051\/ita:2000116","volume":"34","author":"C. Hagenah","year":"2000","unstructured":"Hagenah, C., Muscholl, A.: Computing \u03b5-free NFA from regular expressions in O(n log2(n)) time. R.A.I.R.O. Theoret. Inform. Appl.\u00a034, 257\u2013277 (2000)","journal-title":"R.A.I.R.O. Theoret. Inform. Appl."},{"key":"11_CR17","doi-asserted-by":"crossref","first-page":"113","DOI":"10.3233\/FUN-2007-761-208","volume":"76","author":"Y.-S. Han","year":"2007","unstructured":"Han, Y.-S., Salomaa, K., Wood, D.: Intercode regular languages. Fund. Informaticae\u00a076, 113\u2013128 (2007)","journal-title":"Fund. Informaticae"},{"key":"11_CR18","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)"},{"key":"11_CR19","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1006\/jcss.2001.1748","volume":"62","author":"J. Hromkovi\u010d","year":"2001","unstructured":"Hromkovi\u010d, J., Seibert, S., Wilke, T.: Translating regular expressions into small \u03b5-free nondeterministic automata. J. Comput. System Sci.\u00a062, 565\u2013588 (2001)","journal-title":"J. Comput. System Sci."},{"key":"11_CR20","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1006\/inco.2000.2964","volume":"163","author":"P. Kilpel\u00e4inen","year":"2001","unstructured":"Kilpel\u00e4inen, P., Wood, D.: SGML and XML document grammars and exceptions. Inform. Computation\u00a0163, 230\u2013251 (2001)","journal-title":"Inform. Computation"},{"key":"11_CR21","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/S0022-0000(02)00030-2","volume":"66","author":"T. Milo","year":"2002","unstructured":"Milo, T., Suciu, D., Vianu, V.: Typechecking for XML transformers. J. Comput. System Sci.\u00a066, 66\u201397 (2002)","journal-title":"J. Comput. System Sci."},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Murata, M., Lee, D., Mani, M.: Taxonomy of XML schema languages using formal language theory. ACM Trans. Internet Technology\u00a05 (2005)","DOI":"10.1145\/1111627.1111631"},{"key":"11_CR23","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/S0890-5401(03)00013-0","volume":"183","author":"F. Neven","year":"2003","unstructured":"Neven, F., Schwentick, T.: On the power of tree walking automata. Inform. Computation\u00a0183, 86\u2013103 (2003)","journal-title":"Inform. Computation"},{"key":"11_CR24","doi-asserted-by":"crossref","first-page":"361","DOI":"10.3233\/FUN-2002-52405","volume":"52","author":"A. Okhotin","year":"2002","unstructured":"Okhotin, A., Salomaa, K., Domaratzki, M.: One-visit caterpillar tree automata. Fund. Informaticae\u00a052, 361\u2013375 (2002)","journal-title":"Fund. Informaticae"},{"key":"11_CR25","unstructured":"Salomaa, K., Yu, S., Zan, J.: Deterministic caterpillar expressions. School of Computing, Queen\u2019s University, Tech. Report No. 2007\u2013533 (2007)"},{"key":"11_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1007\/11672142_35","volume-title":"STACS 2006","author":"G. Schnitger","year":"2006","unstructured":"Schnitger, G.: Regular expressions and NFA without \u03b5-transitions. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 432\u2013443. Springer, Heidelberg (2006)"},{"key":"11_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1007\/3-540-55808-X_48","volume-title":"Mathematical Foundations of Computer Science 1992","author":"A. Szilard","year":"1992","unstructured":"Szilard, A., Yu, S., Zhang, K., Shallit, J.: Characterizing regular languages with polynomial densities. In: Havel, I.M., Koubek, V. (eds.) Mathematical Foundations of Computer Science 1992. LNCS, vol.\u00a0629, pp. 494\u2013503. Springer, Heidelberg (1992)"},{"key":"11_CR28","doi-asserted-by":"crossref","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: Rogenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.\u00a01, pp. 41\u2013110. Springer, Heidelberg (1997)"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-76336-9_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T23:16:29Z","timestamp":1737501389000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-76336-9_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540763352"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-76336-9_11","relation":{},"subject":[]}}