{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:32:28Z","timestamp":1759638748952},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540742395"},{"type":"electronic","value":"9783540742401"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74240-1_40","type":"book-chapter","created":{"date-parts":[[2007,8,27]],"date-time":"2007-08-27T07:04:18Z","timestamp":1188198258000},"page":"458-469","source":"Crossref","is-referenced-by-count":5,"title":["Complexity of Pebble Tree-Walking Automata"],"prefix":"10.1007","author":[{"given":"Mathias","family":"Samuelides","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luc","family":"Segoufin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"40_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. Information and Control\u00a019(5), 439\u2013475 (1971)","journal-title":"Information and Control"},{"issue":"2-3","key":"40_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. Theor. Comput. Sci.\u00a0350(2-3), 164\u2013173 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"40_CR3","doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M., Colcombet, T.: Tree-walking automata do not recognize all regular languages. STOC\u00a0 (2005)","DOI":"10.1145\/1060590.1060626"},{"key":"40_CR4","doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M., Samuelides, M., Schwentick, T., Segoufin, L.: Expressive power of pebble automata. In: ICALP (2006)","DOI":"10.1007\/11786986_15"},{"key":"40_CR5","unstructured":"Comon, H., et al.: Tree Automata Techniques and Applications. at http:\/\/www.grappa.univ-lille3.fr\/tata"},{"key":"40_CR6","doi-asserted-by":"crossref","unstructured":"Cosmadakis, S.S., Gaifman, H., Kanellakis, P.C., Vardi, M.Y.: Decidable Optimization Problems for Database Logic Programs. In: STOC (1988)","DOI":"10.1145\/62212.62259"},{"key":"40_CR7","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., et al. (eds.) Jewels are forever, pp. 72\u201383. Springer, Heidelberg (1999)"},{"key":"40_CR8","doi-asserted-by":"crossref","unstructured":"Engelfriet, J., Hoogeboom, H.J.: Nested Pebbles and Transitive Closure. In: STACS (2006)","DOI":"10.1007\/11672142_39"},{"issue":"1","key":"40_CR9","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(1), 51\u201364 (1999)","journal-title":"Acta Cybern."},{"issue":"9","key":"40_CR10","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(9), 613\u2013698 (2003)","journal-title":"Acta Inf."},{"issue":"2","key":"40_CR11","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. Theor. Comput. Sci.\u00a0169(2), 161\u2013184 (1996)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"40_CR12","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. Comput. Syst. Sci.\u00a066(1), 66\u201397 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"40_CR13","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.ipl.2005.09.017","volume":"99","author":"A. Muscholl","year":"2006","unstructured":"Muscholl, A., Samuelides, M., Segoufin, L.: Complementing deterministic tree-walking automata. IPL\u00a099(1), 33\u201339 (2006)","journal-title":"IPL"},{"key":"40_CR14","doi-asserted-by":"crossref","unstructured":"Neven, F.: Extensions of Attribute Grammars for Structured Documents Queries. In: DBPL (1999)","DOI":"10.1007\/3-540-44543-9_7"},{"key":"40_CR15","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0020-0190(89)90205-6","volume":"30","author":"M.Y. Vardi","year":"1989","unstructured":"Vardi, M.Y.: A note on the reduction of two-way automata to one-way automata. IPL\u00a030, 261\u2013264 (1989)","journal-title":"IPL"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74240-1_40.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:15:25Z","timestamp":1619504125000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74240-1_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540742395","9783540742401"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74240-1_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}