{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,12]],"date-time":"2026-08-12T04:41:04Z","timestamp":1786509664534,"version":"3.56.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2004,7,1]],"date-time":"2004-07-01T00:00:00Z","timestamp":1088640000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2004,7]]},"abstract":"<jats:p>Motivated by formal models recently proposed in the context of XML, we study automata and logics on strings over infinite alphabets. These are conservative extensions of classical automata and logics defining the regular languages on finite alphabets. Specifically, we consider register and pebble automata, and extensions of first-order logic and monadic second-order logic. For each type of automaton we consider one-way and two-way variants, as well as deterministic, nondeterministic, and alternating control. We investigate the expressiveness and complexity of the automata and their connection to the logics, as well as standard decision problems. Some of our results answer open questions of Kaminski and Francez on register automata.<\/jats:p>","DOI":"10.1145\/1013560.1013562","type":"journal-article","created":{"date-parts":[[2004,10,7]],"date-time":"2004-10-07T17:38:56Z","timestamp":1097170736000},"page":"403-435","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":194,"title":["Finite state machines for strings over infinite alphabets"],"prefix":"10.1145","volume":"5","author":[{"given":"Frank","family":"Neven","sequence":"first","affiliation":[{"name":"Limburgs Universitair Centrum, Diepenbeek, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[{"name":"Philipps-Universit\u00e4t Marburg, Marburg, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Victor","family":"Vianu","sequence":"additional","affiliation":[{"name":"University of California, San Diego, La Jolla, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2004,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Web: From Relations to Semistructured Data and XML. Morgan Kaufmann","author":"Abiteboul S.","year":"1999","unstructured":"Abiteboul , S. , Buneman , P. , and Suciu , D . 1999 . Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann , San Francisco, CA . Abiteboul, S., Buneman, P., and Suciu, D. 1999. Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann, San Francisco, CA."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1598"},{"key":"e_1_2_1_3_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley Reading MA.   Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley Reading MA."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1691"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 20th Symposium on Principles of Database Systems (PODS","author":"Alon N.","year":"2001","unstructured":"Alon , N. , Milo , T. , Neven , F. , Suciu , D. , and Vianu , V . 2001. XML with data values: Typechecking revisited . In Proceedings of the 20th Symposium on Principles of Database Systems (PODS 2001 ). ACM Press, New York, NY, 560--572. 10.1145\/375551.375570 Alon, N., Milo, T., Neven, F., Suciu, D., and Vianu, V. 2001. XML with data values: Typechecking revisited. In Proceedings of the 20th Symposium on Principles of Database Systems (PODS 2001). ACM Press, New York, NY, 560--572. 10.1145\/375551.375570"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0306-4379(01)00033-3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"e_1_2_1_8_1","volume-title":"Handbook of Theoretical Computer Science","author":"Courcelle B.","unstructured":"Courcelle , B. 1990. Graph rewriting: An algebraic and logic approach . In Handbook of Theoretical Computer Science , vol. B, chap. 5 , J. van Leeuwen, Ed. Elsevier , Amsterdam, The Netherlands. Courcelle, B. 1990. Graph rewriting: An algebraic and logic approach. In Handbook of Theoretical Computer Science, vol. B, chap. 5, J. van Leeuwen, Ed. Elsevier, Amsterdam, The Netherlands."},{"key":"e_1_2_1_9_1","unstructured":"Ebbinghaus H.-D. and Flum J. 1999. Finite Model Theory 2nd ed. Springer Berlin Germany.  Ebbinghaus H.-D. and Flum J. 1999. Finite Model Theory 2nd ed. Springer Berlin Germany."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00119-3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2675"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Greenlaw R. Hoover H. and Ruzzo W. L. 1995. Limits to Parallel Computation. P-Completeness Theory. Oxford University Press Oxford U.K.   Greenlaw R. Hoover H. and Ruzzo W. L. 1995. Limits to Parallel Computation. P-Completeness Theory. Oxford University Press Oxford U.K.","DOI":"10.1093\/oso\/9780195085914.001.0001"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1016\/S0019-9958(65)90399-2","article-title":"One-tape, off-line turing machine computations","volume":"8","author":"Hennie F. C.","year":"1965","unstructured":"Hennie , F. C. 1965 . One-tape, off-line turing machine computations . Inform. Contr. 8 , 6, 553 -- 578 . Hennie, F. C. 1965. One-tape, off-line turing machine computations. Inform. Contr. 8, 6, 553--578.","journal-title":"Inform. Contr."},{"key":"e_1_2_1_14_1","unstructured":"Hopcroft J. and Ullman J. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley Reading MA.   Hopcroft J. and Ullman J. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley Reading MA."},{"key":"e_1_2_1_15_1","series-title":"Texts in Theoretical Computer Science---An EATCS Series","volume-title":"Communication Complexity and Parallel Computing","author":"Hromkovic J.","unstructured":"Hromkovic , J. 2000. Communication Complexity and Parallel Computing . Texts in Theoretical Computer Science---An EATCS Series . Springer-Verlag , Berlin, Germany . Hromkovic, J. 2000. Communication Complexity and Parallel Computing. Texts in Theoretical Computer Science---An EATCS Series. Springer-Verlag, Berlin, Germany."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of 31th IEEE Symposium on Foundations of Computer Science (FOCS). 683--688","author":"Kaminski M.","unstructured":"Kaminski , M. and Francez , N . 1990. Finite-memory automata . In Proceedings of 31th IEEE Symposium on Foundations of Computer Science (FOCS). 683--688 . Kaminski, M. and Francez, N. 1990. Finite-memory automata. In Proceedings of 31th IEEE Symposium on Foundations of Computer Science (FOCS). 683--688."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90242-9"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1137\/0213010","article-title":"Alternating pushdown and stack automata","volume":"13","author":"Ladner R. E.","year":"1984","unstructured":"Ladner , R. E. , Lipton , R. J. , and Stockmeyer , L. J. 1984 . Alternating pushdown and stack automata . SIAM J. Comput. 13 , 1, 135 -- 155 . Ladner, R. E., Lipton, R. J., and Stockmeyer, L. J. 1984. Alternating pushdown and stack automata. SIAM J. Comput. 13, 1, 135--155.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the Nineteenth ACM Symposium on Principles of Database Systems. ACM Press","author":"Milo T.","unstructured":"Milo , T. , Suciu , D. , and Vianu , V . 2000. Type checking for XML transformers . In Proceedings of the Nineteenth ACM Symposium on Principles of Database Systems. ACM Press , New York, NY, 11--22. 10.1145\/335168.335171 Milo, T., Suciu, D., and Vianu, V. 2000. Type checking for XML transformers. In Proceedings of the Nineteenth ACM Symposium on Principles of Database Systems. ACM Press, New York, NY, 11--22. 10.1145\/335168.335171"},{"key":"e_1_2_1_20_1","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, logic, and XML","author":"Neven F.","unstructured":"Neven , F. 2002a. Automata, logic, and XML . In CSL, J. C. Bradfield, Ed. Lecture Notes in Computer Science , vol. 2471 . Springer , Berlin, Germany , 2--26. Neven, F. 2002a. Automata, logic, and XML. In CSL, J. C. Bradfield, Ed. Lecture Notes in Computer Science, vol. 2471. Springer, Berlin, Germany, 2--26."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 21th Symposium on Principles of Database Systems (PODS","author":"Neven F.","year":"2002","unstructured":"Neven , F. 2002 b. On the power of walking for querying tree-structured data . In Proceedings of the 21th Symposium on Principles of Database Systems (PODS 2002). ACM Press, New York, NY, 77--84. 10.1145\/543613.543624 Neven, F. 2002b. On the power of walking for querying tree-structured data. In Proceedings of the 21th Symposium on Principles of Database Systems (PODS 2002). ACM Press, New York, NY, 77--84. 10.1145\/543613.543624"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 19th Symposium on Principles of Database Systems (PODS","author":"Neven F.","year":"2000","unstructured":"Neven , F. and Schwentick , T . 2000. Expressive and efficient pattern languages for tree-structured data . In Proceedings of the 19th Symposium on Principles of Database Systems (PODS 2000 ). New York, NY, 145--156. 10.1145\/335168.335217 Neven, F. and Schwentick, T. 2000. Expressive and efficient pattern languages for tree-structured data. In Proceedings of the 19th Symposium on Principles of Database Systems (PODS 2000). New York, NY, 145--156. 10.1145\/335168.335217"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00301-2"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0166-218X(85)90039-3","article-title":"Classes of regular and context-free languages over countably infinite alphabets","volume":"12","author":"Otto F.","year":"1985","unstructured":"Otto , F. 1985 . Classes of regular and context-free languages over countably infinite alphabets . Discrete Appl. Math. 12 , 41 -- 56 . Otto, F. 1985. Classes of regular and context-free languages over countably infinite alphabets. Discrete Appl. Math. 12, 41--56.","journal-title":"Discrete Appl. Math."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 20th Symposium on Principles of Database Systems (PODS","author":"Papakonstantinou Y.","year":"2001","unstructured":"Papakonstantinou , Y. and Vianu , V . 2001. DTD inference for views of XML data . In Proceedings of the 20th Symposium on Principles of Database Systems (PODS 2001 ). ACM Press, New York, NY, 35--46. 10.1145\/335168.335173 Papakonstantinou, Y. and Vianu, V. 2001. DTD inference for views of XML data. In Proceedings of the 20th Symposium on Principles of Database Systems (PODS 2001). ACM Press, New York, NY, 35--46. 10.1145\/335168.335173"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00105-X"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1147\/rd.32.0198","article-title":"The reduction of two-way automata to one-way automata","volume":"3","author":"Shepherdson J. C.","year":"1959","unstructured":"Shepherdson , J. C. 1959 . The reduction of two-way automata to one-way automata . IBM J. Res. Develop. 3 , 198 -- 200 . Shepherdson, J. C. 1959. The reduction of two-way automata to one-way automata. IBM J. Res. Develop. 3, 198--200.","journal-title":"IBM J. Res. Develop."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/0304-3975(80)90053-5","article-title":"Halting space-bounded computations","volume":"10","author":"Sipser M.","year":"1980","unstructured":"Sipser , M. 1980 . Halting space-bounded computations . Theoret. Comput. Sci. 10 , 335 -- 338 . Sipser, M. 1980. Halting space-bounded computations. Theoret. Comput. Sci. 10, 335--338.","journal-title":"Theoret. Comput. Sci."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/S0022-0000(75)80014-6","article-title":"On tape-bounded complexity classes and multihead finite automata","volume":"10","author":"Sudborough I. H.","year":"1975","unstructured":"Sudborough , I. H. 1975 . On tape-bounded complexity classes and multihead finite automata . J. Comput. Syst. Sci. 10 , 1, 62 -- 76 . Sudborough, I. H. 1975. On tape-bounded complexity classes and multihead finite automata. J. Comput. Syst. Sci. 10, 1, 62--76.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_30_1","volume-title":"Handbook of Formal Languages","author":"Thomas W.","unstructured":"Thomas , W. 1997. Languages , automata, and logic . In Handbook of Formal Languages , vol. 3 , chap. 7, G. Rozenberg and A. Salomaa, Eds . Springer , Berlin, Germany, 389--456. Thomas, W. 1997. Languages, automata, and logic. In Handbook of Formal Languages, vol. 3, chap. 7, G. Rozenberg and A. Salomaa, Eds. Springer, Berlin, Germany, 389--456."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 20th Symposium on Principles of Database Systems (PODS","author":"Vianu V.","year":"2001","unstructured":"Vianu , V. 2001 . A Web odyssey: From Codd to XML . In Proceedings of the 20th Symposium on Principles of Database Systems (PODS 2001). ACM Press, New York, NY, 1--15. 10.1145\/375551.375554 Vianu, V. 2001. A Web odyssey: From Codd to XML. In Proceedings of the 20th Symposium on Principles of Database Systems (PODS 2001). ACM Press, New York, NY, 1--15. 10.1145\/375551.375554"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1013560.1013562","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1013560.1013562","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:19:03Z","timestamp":1750263543000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1013560.1013562"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,7]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2004,7]]}},"alternative-id":["10.1145\/1013560.1013562"],"URL":"https:\/\/doi.org\/10.1145\/1013560.1013562","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,7]]},"assertion":[{"value":"2004-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}