{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:57:21Z","timestamp":1725544641529},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540323013"},{"type":"electronic","value":"9783540322887"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"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":[[2006]]},"DOI":"10.1007\/11672142_39","type":"book-chapter","created":{"date-parts":[[2006,2,28]],"date-time":"2006-02-28T03:27:54Z","timestamp":1141097274000},"page":"477-488","source":"Crossref","is-referenced-by-count":6,"title":["Nested Pebbles and Transitive Closure"],"prefix":"10.1007","author":[{"given":"Joost","family":"Engelfriet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hendrik Jan","family":"Hoogeboom","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"39_CR1","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/S0019-9958(71)90706-6","volume":"19","author":"A.V. Aho","year":"1971","unstructured":"Aho, A.V., Ullman, J.D.: Translations on a context free grammar. Inform. Control.\u00a019, 439\u2013475 (1971)","journal-title":"Inform. Control."},{"key":"39_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BFb0023754","volume-title":"Computer Science Logic","author":"Y. Bargury","year":"1992","unstructured":"Bargury, Y., Makowsky, J.A.: The expressive power of transitive closure and 2-way multihead automata. In: Kleine B\u00fcning, H., J\u00e4ger, G., B\u00f6rger, E., Richter, M.M. (eds.) CSL 1991. LNCS, vol.\u00a0626, pp. 1\u201314. Springer, Heidelberg (1992)"},{"key":"39_CR3","doi-asserted-by":"crossref","unstructured":"Blum, M., Hewitt, C.: Automata on a 2-dimensional tape. In: Proceedings 8th IEEE SWAT, pp. 155\u2013160 (1967)","DOI":"10.1109\/FOCS.1967.6"},{"key":"39_CR4","doi-asserted-by":"crossref","unstructured":"Blum, M., Kozen, D.: On the power of the compass (or, why mazes are easier to search than graphs). In: Proceedings 19th FOCS, pp. 132\u2013142 (1978)","DOI":"10.1109\/SFCS.1978.30"},{"key":"39_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/978-3-540-27836-8_23","volume-title":"Automata, Languages and Programming","author":"M. Boja\u0144czyk","year":"2004","unstructured":"Boja\u0144czyk, M., Colcombet, T.: Tree-walking automata cannot be determinized. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 246\u2013256. Springer, Heidelberg (2004)"},{"key":"39_CR6","doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M., Colcombet, T.: Tree-walking automata do not recognize all regular languages. In: Gabow, H.N., Fagin, R. (eds.) Proceedings 37th STOC (2005)","DOI":"10.1145\/1060590.1060626"},{"key":"39_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. Markup Languages\u00a02, 81\u2013106 (2000)","journal-title":"Markup Languages"},{"key":"39_CR8","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/mana.19780860120","volume":"86","author":"L. Budach","year":"1978","unstructured":"Budach, L.: Automata and labyrinths. Math. Nachr.\u00a086, 195\u2013282 (1978)","journal-title":"Math. Nachr."},{"key":"39_CR9","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1137\/0209048","volume":"9","author":"S.A. Cook","year":"1980","unstructured":"Cook, S.A., Rackoff, C.W.: Space lower bounds for maze threadability on restricted machines. SIAM J. Comput.\u00a09, 636\u2013652 (1980)","journal-title":"SIAM J. Comput."},{"key":"39_CR10","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/S0022-0000(70)80041-1","volume":"4","author":"J. Doner","year":"1970","unstructured":"Doner, J.: Tree acceptors and some of their applications. J. Comp. Syst. Sci.\u00a04, 406\u2013451 (1970)","journal-title":"J. Comp. Syst. Sci."},{"key":"39_CR11","series-title":"Perspectives in Mathematical Logic","volume-title":"Finite Model Theory","author":"H.-D. Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, 2nd edn. Perspectives in Mathematical Logic. Springer, Berlin (1999)","edition":"2"},{"key":"39_CR12","unstructured":"Engelfriet, J.: Context-free grammars with storage, Leiden University, Technical Report 86\u201311 (1986)"},{"key":"39_CR13","doi-asserted-by":"publisher","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., et al. (eds.) Jewels are forever, pp. 72\u201383. Springer, Heidelberg (1999)"},{"key":"39_CR14","unstructured":"Engelfriet, J., Hoogeboom, H.J.: Automata with nested pebbles capture first-order logic with transitive closure. LIACS Tech. Rep. 2005-02, Leiden University (2005)"},{"key":"39_CR15","first-page":"51","volume":"14","author":"J. Engelfriet","year":"1999","unstructured":"Engelfriet, J., Hoogeboom, H.J., van Best, J.-P.: Trips on trees. Acta Cyb.\u00a014, 51\u201364 (1999)","journal-title":"Acta Cyb."},{"key":"39_CR16","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/s00236-003-0120-0","volume":"39","author":"J. Engelfriet","year":"2003","unstructured":"Engelfriet, J., Maneth, S.: A comparison of pebble tree transducers with macro tree transducers. Acta Inf.\u00a039, 613\u2013698 (2003)","journal-title":"Acta Inf."},{"key":"39_CR17","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(80)90058-6","volume":"20","author":"J. Engelfriet","year":"1980","unstructured":"Engelfriet, J., Rozenberg, G., Slutzki, G.: Tree transducers, L systems, and two-way machines. J. Comp. Syst. Sci.\u00a020, 150\u2013202 (1980)","journal-title":"J. Comp. Syst. Sci."},{"key":"39_CR18","volume-title":"Handbook of Formal Languages","author":"D. Giammarresi","year":"1997","unstructured":"Giammarresi, D., Restivo, A.: Two-dimensional languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.\u00a03, Springer, Heidelberg (1997)"},{"key":"39_CR19","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/S0304-3975(96)00119-3","volume":"169","author":"N. Globerman","year":"1996","unstructured":"Globerman, N., Harel, D.: Complexity results for two-way and multi-pebble automata and their logics. TCS\u00a0169, 161\u2013184 (1996)","journal-title":"TCS"},{"key":"39_CR20","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"Immerman, N.: Languages that capture complexity classes. SIAM J. Comput.\u00a016, 760\u2013778 (1987)","journal-title":"SIAM J. Comput."},{"key":"39_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"N. Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive Complexity. Springer, New York (1999)"},{"key":"39_CR22","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1016\/S0019-9958(81)90438-1","volume":"49","author":"T. Kamimura","year":"1981","unstructured":"Kamimura, T., Slutzki, G.: Parallel and two-way automata on directed ordered acyclic graphs. Inform. Control.\u00a049, 10\u201351 (1981)","journal-title":"Inform. Control."},{"key":"39_CR23","first-page":"1","volume-title":"Logics for Emerging Applications of Databases","author":"N. Klarlund","year":"2004","unstructured":"Klarlund, N., Schwentick, T., Suciu, D.: XML: Model, Schemas, Types, Logics, and Queries. In: Chomicki, J., et al. (eds.) Logics for Emerging Applications of Databases, pp. 1\u201341. Springer, Heidelberg (2004)"},{"key":"39_CR24","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1006\/inco.2002.2955","volume":"179","author":"O. Matz","year":"2002","unstructured":"Matz, O., Schweikardt, N., Thomas, W.: The monadic quantifier alternation hierarchy over grids and graphs. Inform. Comput.\u00a0179, 356\u2013383 (2002)","journal-title":"Inform. Comput."},{"key":"39_CR25","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/S0022-0000(02)00030-2","volume":"66","author":"T. Milo","year":"2003","unstructured":"Milo, T., Suciu, D., Vianu, V.: Typechecking for XML transformers. J. Comp. Syst. Sci.\u00a066, 66\u201397 (2003)","journal-title":"J. Comp. Syst. Sci."},{"key":"39_CR26","first-page":"67","volume":"14","author":"B. Monien","year":"1980","unstructured":"Monien, B.: Two-way multihead automata over a one-letter alphabet. RAIRO \u2013 ITA\u00a014, 67\u201382 (1980)","journal-title":"RAIRO \u2013 ITA"},{"key":"39_CR27","unstructured":"Muscholl, A., Samuelides, M., Segoufin, L.: Complementing deterministic tree-walking automata, Manuscript. In: IPL (To appear, 2005)"},{"key":"39_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/3-540-45793-3_2","volume-title":"Computer Science Logic","author":"F. Neven","year":"2002","unstructured":"Neven, F.: Automata, logic, and XML. In: Bradfield, J.C. (ed.) CSL 2002 and EACSL 2002. LNCS, vol.\u00a02471, pp. 2\u201326. Springer, Heidelberg (2002)"},{"key":"39_CR29","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. Comput.\u00a0183, 86\u2013103 (2003)","journal-title":"Inform. Comput."},{"key":"39_CR30","first-page":"361","volume":"52","author":"A. Okhotin","year":"2002","unstructured":"Okhotin, A., Salomaa, K., Domaratzki, M.: One-visit caterpillar tree automata. Fund. Inf.\u00a052, 361\u2013375 (2002)","journal-title":"Fund. Inf."},{"key":"39_CR31","unstructured":"Potthoff, A.: Logische Klassifizierung regul\u00e4rer Baumsprachen, PhD thesis, Institut f\u00fcr Informatik und Praktische Mathematik, Universit\u00e4t Kiel (1994)"},{"key":"39_CR32","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/0304-3975(80)90053-5","volume":"10","author":"M. Sipser","year":"1980","unstructured":"Sipser, M.: Halting space-bounded computations. TCS\u00a010, 335\u2013338 (1980)","journal-title":"TCS"},{"key":"39_CR33","first-page":"57","volume":"2","author":"J.W. Thatcher","year":"1968","unstructured":"Thatcher, J.W., Wright, J.B.: Generalized finite automata theory with an application to a decision problem of second-order logic. MST\u00a02, 57\u201381 (1968)","journal-title":"MST"},{"key":"39_CR34","volume-title":"Handbook of Formal Languages","author":"W. Thomas","year":"1997","unstructured":"Thomas, W.: Languages, automata, and logic. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.\u00a03, Springer, Heidelberg (1997)"}],"container-title":["Lecture Notes in Computer Science","STACS 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11672142_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,16]],"date-time":"2019-04-16T23:31:32Z","timestamp":1555457492000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11672142_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540323013","9783540322887"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/11672142_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}