{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T12:23:27Z","timestamp":1791030207700,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540424963","type":"print"},{"value":"9783540446835","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44683-4_49","type":"book-chapter","created":{"date-parts":[[2007,8,28]],"date-time":"2007-08-28T21:32:38Z","timestamp":1188336758000},"page":"560-572","source":"Crossref","is-referenced-by-count":35,"title":["Towards Regular Languages over Infinite Alphabets"],"prefix":"10.1007","author":[{"given":"Frank","family":"Neven","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Victor","family":"Vianu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2001,9,5]]},"reference":[{"key":"49_CR1","unstructured":"S. Abiteboul, P. Buneman, and D. Suciu. Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann, 1999."},{"issue":"1","key":"49_CR2","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1006\/jcss.1998.1598","volume":"58","author":"S. Abiteboul","year":"1999","unstructured":"S. Abiteboul, L. Herr, and J. Van den Bussche. Temporal connectives versus explicit timestamps to query temporal databases. Journal of Computer and System Sciences, 58(1):54\u201368, 1999.","journal-title":"Journal of Computer and System Sciences"},{"key":"49_CR3","doi-asserted-by":"crossref","unstructured":"N. Alon, T. Milo, F. Neven, D. Suciu, and V. Vianu. XML with Data Values: Typechecking Revisited. To be presented at LICS 2001.","DOI":"10.1145\/375551.375570"},{"key":"49_CR4","unstructured":"J. Clark XSL Transformations (XSLT) specification, 1999. http:\/\/www.w3.org\/ TR\/WD-xslt ."},{"key":"49_CR5","doi-asserted-by":"crossref","unstructured":"G. Rozenberg and A. Salomaa, editors. Handbook of Formal Languages, volume 3. Springer, 1997.","DOI":"10.1007\/978-3-642-59136-5"},{"issue":"1","key":"49_CR6","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1006\/inco.1997.2675","volume":"140","author":"E. Gr\u00e4del","year":"1998","unstructured":"E. Gr\u00e4del and Y. Gurevich. Metafinite model theory. Information and Computation, 140(1):26\u201381, 1998.","journal-title":"Information and Computation"},{"issue":"2","key":"49_CR7","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/S0304-3975(96)00119-3","volume":"169","author":"N. Globerman","year":"1996","unstructured":"N. Globerman and D. Harel. Complexity results for two-way and multi-pebble automata and their logics. Theoretical Computer Science, 169(2):161\u2013184, 1996.","journal-title":"Theoretical Computer Science"},{"key":"49_CR8","unstructured":"J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979."},{"key":"49_CR9","unstructured":"J. Hromkovic. Communication Complexity and Parallel Computing. Springer-Verlag, 2000."},{"key":"49_CR10","doi-asserted-by":"crossref","unstructured":"M. Kaminski and N. Francez. Finite-memory automata. In Proceedings of 31th IEEE Symposium on Foundations of Computer Science (FOCS), pages 683\u2013688, 1990.","DOI":"10.1109\/FSCS.1990.89590"},{"issue":"2","key":"49_CR11","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/0304-3975(94)90242-9","volume":"134","author":"M. Kaminski","year":"1994","unstructured":"M. Kaminski and N. Francez. Finite-memory automata. Theoretical Computer Science, 134(2):329\u2013363, 1994.","journal-title":"Theoretical Computer Science"},{"key":"49_CR12","doi-asserted-by":"crossref","unstructured":"A. K. Chandra, L. J. Stockmeyer. Alternation. In Proceedings of 17th IEEE Symposium on Foundations of Computer Science (FOCS 1976), 98\u2013108, 1976.","DOI":"10.1109\/SFCS.1976.4"},{"key":"49_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/3-540-44543-9_6","volume-title":"Research Issues in Structured and Semistructured Database Programming (DBPL\u201999)","author":"S. Maneth","year":"2000","unstructured":"S. Maneth and F. Neven. Structured document transformations based on XSL. In R. Connor and A. Mendelzon, editors, Research Issues in Structured and Semistructured Database Programming (DBPL\u201999), volume 1949 of Lecture Notes in Computer Science, pages 79\u201396. Springer, 2000."},{"key":"49_CR14","doi-asserted-by":"crossref","unstructured":"T. Milo, D. Suciu, and V. Vianu. Type checking for XML transformers. In Proceedings of the Nineteenth ACM Symposium on Principles of Database Systems, pages 11\u201322. ACM Press, 2000.","DOI":"10.1145\/335168.335171"},{"key":"49_CR15","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/3-540-44543-9_7","volume-title":"Research Issues in Structured and Semistructured Database Programming (DBPL\u201999)","author":"F. Neven","year":"2000","unstructured":"F. Neven. Extensions of attribute grammars for structured document queries. In R. Connor and A. Mendelzon, editors, Research Issues in Structured and Semistructured Database Programming (DBPL\u201999), volume 1949 of Lecture Notes in Computer Science, pages 97\u2013114. Springer, 2000."},{"key":"49_CR16","doi-asserted-by":"crossref","unstructured":"F. Neven and T. Schwentick. Query automata. In Proceedings of the 18th ACM Symposium on Principles of Database Systems (PODS 1999), pages 205\u2013214. ACM Press, 1999.","DOI":"10.1145\/303976.303997"},{"key":"49_CR17","doi-asserted-by":"crossref","unstructured":"F. Neven and T. Schwentick. Expressive and efficient pattern languages for tree-structured data. In Proceedings of 19th ACM Symposium on Principles of Database Systems (PODS 2000), Dallas, pages 145\u2013156, 2000.","DOI":"10.1145\/335168.335217"},{"key":"49_CR18","doi-asserted-by":"crossref","unstructured":"F. Neven and J. Van den Bussche. Expressiveness of structured document query languages based on attribute grammars. In Proceedings of 17th ACM Symposium on Principles of Database Systems (PODS 1998), pages 11\u201317. ACM Press, 1998.","DOI":"10.1145\/275487.275489"},{"key":"49_CR19","doi-asserted-by":"crossref","unstructured":"Y. Papakonstantinou and V. Vianu. DTD inference for views of XML data. In Proceedings of 19th ACM Symposium on Principles of Database Systems (PODS 2000), pages 35\u201346. ACM, Press 2000.","DOI":"10.1145\/335168.335173"},{"issue":"1","key":"49_CR20","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/S0022-0000(75)80014-6","volume":"10","author":"I. H. Sudborough","year":"1975","unstructured":"I. H. Sudborough. On tape-bounded complexity classes and multihead finite automata. Journal of Computer and System Sciences, 10(1):62\u201376, 1975.","journal-title":"Journal of Computer and System Sciences"},{"key":"49_CR21","doi-asserted-by":"crossref","unstructured":"W. Thomas. Languages, automata, and logic. In A. Salomaa, editors. Handbook of Formal Languages, volume 3. Springer, 1997 Rozenberg and Salomaa [5], chapter 7.","DOI":"10.1007\/978-3-642-59126-6_7"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44683-4_49","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T13:27:42Z","timestamp":1556803662000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44683-4_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424963","9783540446835"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-44683-4_49","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2001]]}}}