{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:33:01Z","timestamp":1759638781372},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540009573"},{"type":"electronic","value":"9783540365969"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-36596-6_9","type":"book-chapter","created":{"date-parts":[[2007,10,24]],"date-time":"2007-10-24T21:23:52Z","timestamp":1193261032000},"page":"160-178","source":"Crossref","is-referenced-by-count":1,"title":["Automata- and Logic-Based Pattern Languages for Tree-Structured Data"],"prefix":"10.1007","author":[{"given":"Frank","family":"Neven","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,4,1]]},"reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1023\/A:1004275029985","volume":"27","author":"H. Andr\u00e9ka","year":"1998","unstructured":"H. Andr\u00e9ka, J. van Benthem, and I. N\u00e9meti. Modal languages and bounded fragments of predicate logic. Journal of Philosophical Logic, 27:217\u2013274, 1998.","journal-title":"Journal of Philosophical Logic"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"G. J. Bex, S. Maneth, and F. Neven. A formal model for an expressive fragment of XSLT. 1st International Conference on Computational Logic, pages 1137\u20131151, Lecture Notes in Artificial Intelligence, volume 1861. Springer, 2000.","DOI":"10.1007\/3-540-44957-4_76"},{"issue":"1","key":"9_CR3","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":"9_CR4","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-05, Hong Kong University of Science & Technology, 2001."},{"issue":"1","key":"9_CR5","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":"9_CR6","unstructured":"D. Chamberlin, D. Florescu, J. Robie, J. Sim\u00e9on, and M. Stefanescu. XQuery: a query language for XML. Latest version: http:\/\/www.w3.org\/TR\/xquery\/ ."},{"key":"9_CR7","unstructured":"J. Clark. XSL Transformations (XSLT) Version 1.0. Latest version: http:\/\/www.w3.org\/TR\/xslt ."},{"key":"9_CR8","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":"9_CR9","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":"9_CR10","doi-asserted-by":"crossref","unstructured":"H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 1995.","DOI":"10.1007\/3-540-28788-4"},{"key":"9_CR11","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":"9_CR12","first-page":"51","volume":"14","author":"J. Engelfriet","year":"1999","unstructured":"J. Engelfriet, H.J. Hoogeboom, and J.-P. van Best. Trips on trees. Acta Cybernetica, 14:51\u201364, 1999.","journal-title":"Acta Cybernetica"},{"key":"9_CR13","unstructured":"M. Fernandez, J. Sim\u00e9on, and P. Wadler, editors. XML Query languages: Experiences and Exemplars, 1999. http:\/\/www-db.research.bell-labs.com\/user\/simeon\/xquery.html ."},{"key":"9_CR14","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. Springer, 1997.","DOI":"10.1007\/978-3-642-59126-6_1"},{"issue":"2","key":"9_CR15","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"},{"issue":"2","key":"9_CR16","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01692511","volume":"2","author":"D.E. Knuth","year":"1968","unstructured":"D.E. Knuth. Semantics of context-free languages. Mathematical Systems Theory, 2(2):127\u2013145, 1968. See also Mathematical Systems Theory, 5(2):95-96, 1971.","journal-title":"Mathematical Systems Theory"},{"key":"9_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/3-540-44543-9_6","volume-title":"Research Issues in Structured and Semistructured Database Programming","author":"S. Maneth","year":"2000","unstructured":"S. Maneth and F. Neven. Structured Document Transformations Based on XSL. In R. Conner, A. Mendelzon, editors, Research Issues in Structured and Semistructured Database Programming, volume 1949 of Lecture Notes in Computer Science, pages 80\u201398. Springer 2000."},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"A. R. Meyer. Weak monadic second-order theory of successor is not elementary recursive. In R. Parikh, editors, Logic Colloquim, volume 453 of Lecture Notes in Mathematics, pages 132\u2013154. Springer, 1975.","DOI":"10.1007\/BFb0064872"},{"key":"9_CR19","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":"9_CR20","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0020-0190(94)00022-0","volume":"50","author":"E. Moriya","year":"1994","unstructured":"E. Moriya. On two-way tree automata. Information Processing Letters, 50:117\u2013121, 1994.","journal-title":"Information Processing Letters"},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"M. Murata. Extended Path Expressions for XML. To appear in Proceedings of the Twentieth ACM Symposium on Principles of Database Systems. ACM Press, 2001.","DOI":"10.1145\/375551.375569"},{"key":"9_CR22","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/3-540-44543-9_7","volume-title":"Research Issues in Structured and Semistructured Database Programming","author":"F. Neven","year":"2000","unstructured":"F. Neven. Extensions of attribute grammars for structured document queries. In R. Conner, A. Mendelzon, editor, Research Issues in Structured and Semistructured Database Programming, volume 1949 of Lecture Notes in Computer Science, pages 99\u2013116. Springer 2000."},{"key":"9_CR23","doi-asserted-by":"crossref","unstructured":"F. Neven and T. Schwentick. Query automata. To appear in Theoretical Computer Science. Extended abstrast in Proceedings of the Eighteenth ACM Symposium on Principles of Database Systems, pages 205\u2013214. ACM Press, 1999.","DOI":"10.1145\/303976.303997"},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"F. Neven and T. Schwentick. Expressive and efficient pattern languages for treestructured data. In Proc. 19th Symposium on Principles of Database Systems (PODS 2000), Dallas, pages 145\u2013156, 2000.","DOI":"10.1145\/335168.335217"},{"key":"9_CR25","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1007\/3-540-45022-X_46","volume-title":"Information and Computation","author":"F. Neven","year":"2000","unstructured":"F. Neven and T. Schwentick. On the power of tree-walking automata. To appear in Information and Computation. Extended abstract in 27th International Colloquium on Automata, Languages and Programming, pages 547\u2013560, Lecture Notes in Computer Science, volume 1853. Springer, 2000."},{"key":"9_CR26","unstructured":"F. Neven, T. Schwentick, and V. Vianu. Towards regular languages over infinte alphabets. Submitted."},{"key":"9_CR27","doi-asserted-by":"crossref","unstructured":"F. Neven and J. Van den Bussche. Expressiveness of structured document query languages based on attribute grammars. To appear in the Journal of the ACM. Extended abstract appeared in Proceedings of the Seventeenth ACM Symposium on Principles of Database Systems, pages 11\u201317. ACM Press, 1998.","DOI":"10.1145\/275487.275489"},{"key":"9_CR28","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, pages 134\u2013145, Lecture Notes in Computer Science, volume 1530. Springer, 1998."},{"key":"9_CR29","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1007\/3-540-44612-5_61","volume-title":"Mathematical Foundations of Computer Science (MFCS 2000)","author":"T. Schwentick","year":"2000","unstructured":"T. Schwentick. On Diving in Trees. In M. Nielsen and B. Rovan, editors, Mathematical Foundations of Computer Science (MFCS 2000), pages 660\u2013669, Lecture Notes in Computer Science, volume 1893. Springer, 2000"},{"key":"9_CR30","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. Springer, 1997.","DOI":"10.1007\/978-3-642-59126-6_7"},{"key":"9_CR31","unstructured":"World Wide Web Consortium. XML Query Requirements. Latest version: http:\/\/www.w3.org\/TR\/xmlquery-reg."}],"container-title":["Lecture Notes in Computer Science","Semantics in Databases"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36596-6_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T00:03:04Z","timestamp":1556928184000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36596-6_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540009573","9783540365969"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-36596-6_9","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}