{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:26:54Z","timestamp":1761611214589},"publisher-location":"Berlin, Heidelberg","reference-count":61,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540442400"},{"type":"electronic","value":"9783540457930"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45793-3_2","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T12:03:26Z","timestamp":1187265806000},"page":"2-26","source":"Crossref","is-referenced-by-count":61,"title":["Automata, Logic, and XML"],"prefix":"10.1007","author":[{"given":"Frank","family":"Neven","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,9,2]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"S. Abiteboul. Semistructured data: from practice to theory. In Proc. 16th IEEE Symposium on Logic in Computer Science (LICS 2001), pages 379\u2013386, 2001.","DOI":"10.1109\/LICS.2001.932513"},{"key":"2_CR2","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":"2_CR3","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":"2_CR4","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/S0019-9958(71)90706-6","volume":"19","author":"A.V. Aho","year":"1971","unstructured":"A.V. Aho and J. D. Ullman. Translations on a context-free grammar. Inform, and Control, 19:439\u2013475, 1971.","journal-title":"Inform, and Control"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"N. Alon, T. Milo, F. Neven, D. Suciu, and V. Vianu. XML with data values: Type-checking revisited. In Proc. 20th Symposium on Principles of Database Systems (PODS 2001), pages 560\u2013572, 2001.","DOI":"10.1145\/375551.375570"},{"issue":"1","key":"2_CR6","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0306-4379(01)00033-3","volume":"27","author":"G. J. Bex","year":"2002","unstructured":"G. J. Bex, S. Maneth, and F. Neven. A formal model for an expressive fragment of XSLT. Information Systems, 27(1):21\u201339, 2002.","journal-title":"Information Systems"},{"issue":"1","key":"2_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jcss.1999.1684","volume":"61","author":"R. Bloem","year":"2000","unstructured":"R. Bloem and J. Engelfriet. A comparison of tree transductions defined by monadic second order logic and by attribute grammars. Journal of Computer and System Sciences, 61(1):1\u201350, 2000.","journal-title":"Journal of Computer and System Sciences"},{"key":"2_CR8","unstructured":"A. Br\u00fcggemann-Klein, M. Murata, and D. Wood. Regular tree and regular hedge languages over unranked alphabets: Version 1, April 3, 2001. Technical Report HKUST-TCSC-2001-0, The Hongkong University of Science and Technology, 2001."},{"issue":"1","key":"2_CR9","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1162\/109966200750410613","volume":"2","author":"A. Br\u00fcggemann-Klein","year":"2000","unstructured":"A. Br\u00fcggemann-Klein and D. Wood. Caterpillars: A context specification technique. Markup Languages, 2(1):81\u2013106, 2000.","journal-title":"Markup Languages"},{"key":"2_CR10","unstructured":"J. Clark. XML Path Language (XPath). http:\/\/www.w3.org\/TR\/xpath ."},{"issue":"6","key":"2_CR11","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1145\/362384.362685","volume":"13","author":"E. Codd","year":"1970","unstructured":"E. Codd. A relational model for large shared databanks. Communications of the ACM, 13(6):377\u2013387, 1970.","journal-title":"Communications of the ACM"},{"key":"2_CR12","unstructured":"H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. Tree automata techniques and applications. Available on: http:\/\/www.grappa.univ-lille3.fr\/tata , 1997."},{"key":"2_CR13","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1006\/jcss.1998.1564","volume":"3","author":"M. Consens","year":"1998","unstructured":"M. Consens and T. Milo. Algebras for querying text regions: Expressive power and optimization. Journal of Computer and System Sciences, 3:272\u2013288, 1998.","journal-title":"Journal of Computer and System Sciences"},{"key":"2_CR14","unstructured":"World Wide Web Consortium. Extensible Markup Language (XML). http:\/\/www.w3.org\/XML\/ ."},{"key":"2_CR15","unstructured":"World Wide Web Consortium. XML schema. http:\/\/www.w3.org\/XML\/Schema ."},{"key":"2_CR16","series-title":"Lect Notes Comput Sci","volume-title":"Attribute Grammars: Definition, Systems and Bibliography","author":"P. Deransart","year":"1988","unstructured":"P. Deransart, M. Jourdan, and B. Lorho. Attribute Grammars: Definition, Systems and Bibliography, volume 323 of Lecture Notes in Computer Science. Springer, 1988."},{"key":"2_CR17","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/S0022-0000(70)80041-1","volume":"4","author":"J. Doner","year":"1970","unstructured":"J. Doner. Tree acceptors and some of their applications. Journal of Computer and System Sciences, 4:406\u2013451, 1970.","journal-title":"Journal of Computer and System Sciences"},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 1995.","DOI":"10.1007\/3-540-28788-4"},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"J. Engelfriet and H. J. Hoogeboom. Tree-walking pebble automata. In J. Karhum\u00e4ki, H. Maurer, G. Paun, and G. Rozenberg, editors, Jewels are forever, contributions to Theoretical Computer Science in honor of Arto Salomaa, pages 72\u201383. Springer-Verlag, 1999.","DOI":"10.1007\/978-3-642-60207-8_7"},{"key":"2_CR20","unstructured":"J. Engelfriet and H. J. Hoogeboom. Private communication. 2002."},{"key":"2_CR21","first-page":"51","volume":"14","author":"J. Engelfriet","year":"1999","unstructured":"J. Engelfriet, H. J. Hoogeboom, and J.-P. vanBest. Trips on trees. Acta Cybernetica, 14:51\u201364, 1999.","journal-title":"Acta Cybernetica"},{"key":"2_CR22","doi-asserted-by":"crossref","unstructured":"M. Frick and M. Grohe. The complexity of first-order and monadic second-order logic revisited. In Proc. 17th IEEE Symposium on Logic in Computer Science (LICS 2002), 2002.","DOI":"10.1109\/LICS.2002.1029830"},{"issue":"5\u20136","key":"2_CR23","first-page":"175","volume":"73","author":"Z. F\u00fcl\u00f6p","year":"2002","unstructured":"Z. F\u00fcl\u00f6p and S. Maneth. Domains of partial attributed tree transducers. Information Processing Letters, 73(5\u20136):175\u2013180, 2002.","journal-title":"Information Processing Letters"},{"key":"2_CR24","doi-asserted-by":"crossref","unstructured":"F. G\u00e9cseg and M. Steinby. Tree languages. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 3, chapter 1, pages 1\u201368. Springer, 1997.","DOI":"10.1007\/978-3-642-59126-6_1"},{"key":"2_CR25","doi-asserted-by":"crossref","unstructured":"G. Gottlob and C. Koch. Monadic datalog and the expresive power of languages for web information extraction. In Proc. 21th Symposium on Principles of Database Systems (PODS 2002), pages 17\u201328. ACM Press, 2002.","DOI":"10.1145\/543616.543617"},{"issue":"1","key":"2_CR26","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"},{"key":"2_CR27","doi-asserted-by":"crossref","unstructured":"H. Hosoya and B. C. Pierce. Regular expression pattern matching for XML. In Proceedings of 28th Symposium on Principles of Programming Languages (POPL 2001), pages 67\u201380. ACM Press, 2001.","DOI":"10.1145\/360204.360209"},{"key":"2_CR28","unstructured":"J. Hromkovic. Communication Complexity and Parallel Computing. Texts in Theoretical Computer Science-An EATCS Series. Springer-Verlag, 2000."},{"key":"2_CR29","doi-asserted-by":"crossref","unstructured":"N. Immerman. Descriptive Complexity. Springer, 1998.","DOI":"10.1007\/978-1-4612-0539-5"},{"issue":"2","key":"2_CR30","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":"2_CR31","unstructured":"D. Lee, M. Mani, and M. Murata. Reasoning about XML schema languages using formal language theor. Technical report, IBM Almaden Research Center, 2000. Log# 95071."},{"key":"2_CR32","unstructured":"W. Martens and F. Neven. Typechecking top-down uniform unranked tree transducers. Manuscript."},{"key":"2_CR33","doi-asserted-by":"crossref","unstructured":"G. Miklau and D. Suciu. Containment and equivalence for an XPath fragment. In Proc. 21th Symposium on Principles of Database Systems (PODS 2002), pages 65\u201376, 2002.","DOI":"10.1145\/543613.543623"},{"key":"2_CR34","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":"2_CR35","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/3-540-49654-8_12","volume-title":"Proceedings of the workshop on Principles of Digital Document Processing","author":"M. Murata","year":"1998","unstructured":"M. Murata. Data model for document transformation and assembly. In E.V. Munson, K. Nicholas, and D. Wood, editors, Proceedings of the workshop on Principles of Digital Document Processing, volume 1481 of Lecture Notes in Computer Science, pages 140\u2013152, 1998."},{"key":"2_CR36","doi-asserted-by":"crossref","unstructured":"M. Murata. Extended path expressions for xml. In Proc. 20th Symposium on Principles of Database Systems (PODS 2001), pages 126\u2013137. ACM Press, 2001.","DOI":"10.1145\/375551.375569"},{"key":"2_CR37","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/978-3-540-49382-2_12","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"A. Neumann","year":"1998","unstructured":"A. Neumann and H. Seidl. Locating matches of tree patterns in forests. In V. Arvind and R. Ramanujam, editors, Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, pages 134\u2013145. Springer, 1998."},{"key":"2_CR38","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":"2_CR39","doi-asserted-by":"crossref","unstructured":"F. Neven. On the power of walking for querying tree-structured data. In Proc. 21th Symposium on Principles of Database Systems (PODS 2002), pages 77\u201384. ACM Press, 2002.","DOI":"10.1145\/543613.543624"},{"key":"2_CR40","doi-asserted-by":"crossref","unstructured":"F. Neven and T. Schwentick. Expressive and efficient pattern languages for tree-structured data. In Proc. 19th Symposium on Principles of Database Systems (PODS 2000), pages 145\u2013156, 2000.","DOI":"10.1145\/335168.335217"},{"key":"2_CR41","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1007\/3-540-45022-X_46","volume-title":"International Colloquium on Automata, Languages and Programming (ICALP 2000)","author":"F. Neven","year":"2000","unstructured":"F. Neven and T. Schwentick. On the power of tree-walking automata. In U. Montanari, J. D.P. Rolim, and E. Welzl, editors, International Colloquium on Automata, Languages and Programming (ICALP 2000), volume 1853 of Lecture Notes in Computer Science, pages 547\u2013560. Springer, 2000."},{"key":"2_CR42","unstructured":"F. Neven and T. Schwentick. Automata-and logic-based pattern languages for tree-structured data. Unpublished, 2001."},{"key":"2_CR43","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1016\/S0304-3975(01)00301-2","volume":"275","author":"F. Neven","year":"2002","unstructured":"F. Neven and T. Schwentick. Query automata on finite trees. Theoretical Computer Science, 275:633\u2013674, 2002.","journal-title":"Theoretical Computer Science"},{"key":"2_CR44","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1007\/3-540-44683-4_49","volume-title":"Mathematical Foundations of Computer Science (MFCS 2001)","author":"F. Neven","year":"2001","unstructured":"F. Neven, T. Schwentick, and V. Vianu. Towards regular languages over infinite alphabets. In J. Sgall, A. Pultr, and P. Kolman, editors, Mathematical Foundations of Computer Science (MFCS 2001), volume 2136 of Lecture Notes in Computer Science, pages 560\u2013572. Springer, 2001."},{"key":"2_CR45","doi-asserted-by":"crossref","unstructured":"F. Neven and J. Van den Bussche. Expressiveness of structured document query languages based on attribute grammars. Journal of the ACM, 49(1), 2002.","DOI":"10.1145\/505241.505245"},{"issue":"6","key":"2_CR46","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1016\/S0019-9958(68)90999-6","volume":"13","author":"C. Pair","year":"1968","unstructured":"C. Pair and A. Quere. D\u00e9finition et etude des bilangages r\u00e9guliers. Information and Control, 13(6):565\u2013593, 1968.","journal-title":"Information and Control"},{"key":"2_CR47","doi-asserted-by":"crossref","unstructured":"Y. Papakonstantinou and V. Vianu. DTD inference for views of XML data. In Proc. 20th Symposium on Principles of Database Systems (PODS 2001), pages 35\u201346. ACM Press, 2001.","DOI":"10.1145\/335168.335173"},{"key":"2_CR48","unstructured":"A. Potthoff. Logische Klassifizierung regul\u00e4rer Baumsprachen. Doctor\u2019s thesis, Institut f\u00fcr Informatik u. Prakt. Math., Universit\u201dat Kiel, 1994."},{"key":"2_CR49","unstructured":"E.T. Ray. Learning XML. O\u2019Reilly, 2001."},{"key":"2_CR50","doi-asserted-by":"crossref","unstructured":"T. Schwentick. On diving in trees. In Proceedings of 25th Mathematical Foundations of Computer Science (MFCS 2000), pages 660\u2013669, 2000.","DOI":"10.1007\/3-540-44612-5_61"},{"key":"2_CR51","doi-asserted-by":"crossref","unstructured":"L. Segoufin and V. Vianu. Validating streaming XML documents. In Proc. 21th Symposium on Principles of Database Systems (PODS 2002), pages 53\u201364. ACM Press, 2002.","DOI":"10.1145\/543613.543622"},{"issue":"3","key":"2_CR52","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1137\/0219027","volume":"19","author":"H. Seidl","year":"1990","unstructured":"H. Seidl. Deciding equivalence of finite tree automata. SIAM Journal on Computing, 19(3):424\u2013437, 1990.","journal-title":"SIAM Journal on Computing"},{"issue":"2\u20133","key":"2_CR53","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0304-3975(85)90077-5","volume":"41","author":"G. Slutzki","year":"1985","unstructured":"G. Slutzki. Alternating tree automata. Theoretical Computer Science, 41(2\u20133):305\u2013318, 1985.","journal-title":"Theoretical Computer Science"},{"key":"2_CR54","unstructured":"D. Suciu. Typechecking for semistructured data. In Proceedings of the 8th Workshop on Data Bases and Programming Languages (DBPL 2001), 2001."},{"issue":"1","key":"2_CR55","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0019-9958(75)90058-3","volume":"27","author":"M. Takahashi","year":"1975","unstructured":"M. Takahashi. Generalizations of regular sets and their application to a study of context-free languages. Information and Control, 27(1):1\u201336, 1975.","journal-title":"Information and Control"},{"issue":"1","key":"2_CR56","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J.W. Thatcher","year":"1968","unstructured":"J.W. Thatcher and J. B. Wright. Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical Systems Theory, 2(1):57\u201381, 1968.","journal-title":"Mathematical Systems Theory"},{"key":"2_CR57","doi-asserted-by":"crossref","unstructured":"W. Thomas. Languages, automata, and logic. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 3, chapter 7, pages 389\u2013456. Springer, 1997.","DOI":"10.1007\/978-3-642-59126-6_7"},{"key":"2_CR58","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/3-540-44802-0_2","volume-title":"Computer Science Logic (CSL 2001)","author":"J. Bussche Van den","year":"2001","unstructured":"J. Van den Bussche. Applications of Alfred Tarski\u2019s ideas in database theory. In L. Fribourg, editor, Computer Science Logic (CSL 2001), volume 2142 of Lecture Notes in Computer Science, pages 20\u201337. Springer, 2001."},{"key":"2_CR59","doi-asserted-by":"crossref","unstructured":"M. Y. Vardi. Automata theory for database theoreticians. In Proceedings of the Eighth ACM Symposium on Principles of Database Systems, pages 83\u201392. ACM Press, 1989.","DOI":"10.1145\/73721.73729"},{"key":"2_CR60","doi-asserted-by":"crossref","unstructured":"V. Vianu. Databases and finite-model theory. In N. Immerman and Ph. Kolaitis, editors, Descriptive Complexity and Finite Models, volume 31 of AMS DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 97\u2013148. American Mathematical Society, 1997.","DOI":"10.1090\/dimacs\/031\/04"},{"key":"2_CR61","doi-asserted-by":"crossref","unstructured":"V. Vianu. A web odyssey: From Codd to XML. In Proc. 20th Symposium on Principles of Database Systems (PODS 2001), pages 1\u201315, 2001.","DOI":"10.1145\/375551.375554"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45793-3_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T20:23:49Z","timestamp":1684009429000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45793-3_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540442400","9783540457930"],"references-count":61,"URL":"https:\/\/doi.org\/10.1007\/3-540-45793-3_2","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}