{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:03:52Z","timestamp":1760079832708},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,1,14]],"date-time":"2015-01-14T00:00:00Z","timestamp":1421193600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,8]]},"DOI":"10.1007\/s00224-014-9603-3","type":"journal-article","created":{"date-parts":[[2015,1,13]],"date-time":"2015-01-13T01:26:11Z","timestamp":1421112371000},"page":"180-208","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Walking on Data Words"],"prefix":"10.1007","volume":"59","author":[{"given":"Amaldev","family":"Manuel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anca","family":"Muscholl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabriele","family":"Puppis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,1,14]]},"reference":[{"issue":"4-5","key":"9603_CR1","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1016\/j.tcs.2009.10.009","volume":"411","author":"H Bj\u00f6rklund","year":"2010","unstructured":"Bj\u00f6rklund, H., Schwentick, T.: On notions of regularity for data languages. Theor. Comput. Sci. 411(4-5), 702\u2013715 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"2-3","key":"9603_CR2","doi-asserted-by":"crossref","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. 350(2-3), 164\u2013173 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9603_CR3","doi-asserted-by":"crossref","first-page":"658","DOI":"10.1137\/050645427","volume":"38","author":"M Boja\u0144czyk","year":"2008","unstructured":"Boja\u0144czyk, M., Colcombet, T.: Tree-walking automata do not recognize all regular languages. SIAM J. 38(2), 658\u2013701 (2008)","journal-title":"SIAM J."},{"issue":"4","key":"9603_CR4","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1145\/1970398.1970403","volume":"12","author":"M Boja\u0144czyk","year":"2011","unstructured":"Boja\u0144czyk, M., David, C., Muscholl, A., Schwentick, T., Segoufin, L.: Two-variable logic on data words. ACM Trans. Comput. Log. 12(4), 27 (2011)","journal-title":"ACM Trans. Comput. Log."},{"key":"9603_CR5","doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M., Muscholl, A., Schwentick, T., Segoufin, L.: Two-variable logic on data trees and XML reasoning. J. Assoc. Comput. Mach. 56(3) (2009)","DOI":"10.1145\/1516512.1516515"},{"key":"9603_CR6","doi-asserted-by":"crossref","unstructured":"Engelfriet, J., Hoogeboom, H.: Tree-walking pebble automata. In: Jewels are forever, contributions to Theoretical Computer Science in honor of Arto Salomaa, pp 72\u201383. Springer (1999)","DOI":"10.1007\/978-3-642-60207-8_7"},{"issue":"3","key":"9603_CR7","doi-asserted-by":"crossref","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: a survey. Inf. Comput. 209(3), 456\u2013470 (2011)","journal-title":"Inf. Comput."},{"issue":"2","key":"9603_CR8","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/0304-3975(94)90242-9","volume":"134","author":"M Kaminski","year":"1994","unstructured":"Kaminski, M., Francez, N.: Finite-memory automata. Theor. Comput. Sci. 134(2), 329\u2013363 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"9603_CR9","unstructured":"Kara, A., Schwentick, T., Zeume, T.: Temporal logics on words with multiple data values. In: Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 481\u2013492.Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2010)"},{"key":"9603_CR10","doi-asserted-by":"crossref","unstructured":"Libkin, L., Vrgoc, D.: Regular expressions for data words. In: Proceedings of the 18th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR), LNCS, vol. 7180, pp 274\u2013288. Springer (012)","DOI":"10.1007\/978-3-642-28717-6_22"},{"key":"9603_CR11","unstructured":"Manuel, A., Zeume, T.: Two-variable logic on 2-dimensional structures. In: Proceedings of the 22th EACSL Annual Conference on Computer Science Logic (CSL), LIPIcs, vol. 23, pp. 484\u2013499. Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik (2013)"},{"key":"9603_CR12","unstructured":"McNaughton, R., Papert, S.: Counter-free automata. MIT (1971)"},{"issue":"3","key":"9603_CR13","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1145\/1013560.1013562","volume":"5","author":"F Neven","year":"2004","unstructured":"Neven, F., Schwentick, T., Vianu, V.: Finite state machines for strings over infinite alphabets. ACM Trans. Comput. Log. 5(3), 403\u2013435 (2004)","journal-title":"ACM Trans. Comput. Log."},{"issue":"2","key":"9603_CR14","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M Rabin","year":"1959","unstructured":"Rabin, M., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3(2), 114\u2013125 (1959)","journal-title":"IBM J. Res. Dev."},{"key":"9603_CR15","doi-asserted-by":"crossref","unstructured":"Schwentick, T., Zeume, T.: Two-variable logic with two order relations. In: Proceedings of the 19th EACSL Annual Conference on Computer Science Logic (CSL), LNCS, vol. 6247, pp 499\u2013513. Springer (2010)","DOI":"10.1007\/978-3-642-15205-4_38"},{"key":"9603_CR16","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 10, 335\u2013338 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"9603_CR17","doi-asserted-by":"crossref","unstructured":"Thomas, W.: Elements of an automata theory over partial orders. In: Partial Order Methods in Verification, pp 25\u201340. American Mathematical Society (1997)","DOI":"10.1090\/dimacs\/029\/02"},{"key":"9603_CR18","doi-asserted-by":"crossref","unstructured":"Vollmer, H.: Introduction to Circuit Complexity: a uniform approach. Texts in Theoretical Computer Science. An EATCS Series. Springer (1999)","DOI":"10.1007\/978-3-662-03927-4"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9603-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9603-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9603-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:54:27Z","timestamp":1558698867000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9603-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,14]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,8]]}},"alternative-id":["9603"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9603-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1,14]]}}}