{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:19:16Z","timestamp":1781075956022,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":91,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642284717","type":"print"},{"value":"9783642284724","type":"electronic"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-28472-4_2","type":"book-chapter","created":{"date-parts":[[2012,2,29]],"date-time":"2012-02-29T10:47:10Z","timestamp":1330512430000},"page":"23-33","source":"Crossref","is-referenced-by-count":1,"title":["Foundations of XML Based on Logic and Automata: A Snapshot"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Schwentick","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"5","key":"2_CR1","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/S0019-9958(71)90706-6","volume":"19","author":"A.V. Aho","year":"1971","unstructured":"Aho, A.V., Ullman, J.D.: Translations on a context-free grammar. Information and Control\u00a019(5), 439\u2013475 (1971)","journal-title":"Information and Control"},{"issue":"4","key":"2_CR2","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1145\/1042046.1042050","volume":"29","author":"A. Balmin","year":"2004","unstructured":"Balmin, A., Papakonstantinou, Y., Vianu, V.: Incremental validation of xml documents. ACM Trans. Database Syst.\u00a029(4), 710\u2013751 (2004)","journal-title":"ACM Trans. Database Syst."},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Barbosa, D., Mendelzon, A.O., Libkin, L., Mignet, L., Arenas, M.: Efficient incremental validation of XML documents. In: ICDE, pp. 671\u2013682. IEEE Computer Society (2004)","DOI":"10.1109\/ICDE.2004.1320036"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Fan, W., Geerts, F.: XPath satisfiability in the presence of DTDs. J. ACM\u00a055(2) (2008)","DOI":"10.1145\/1346330.1346333"},{"key":"2_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1007\/11787006_47","volume-title":"Automata, Languages and Programming","author":"M. Benedikt","year":"2006","unstructured":"Benedikt, M., Koch, C.: Interpreting Tree-to-Tree Queries. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006, Part II. LNCS, vol.\u00a04052, pp. 552\u2013564. Springer, Heidelberg (2006)"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Koch, C.: From XQuery to relational logics. ACM Trans. Database Syst.\u00a034(4) (2009)","DOI":"10.1145\/1620585.1620592"},{"issue":"9","key":"2_CR7","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1007\/s00236-002-0085-4","volume":"38","author":"J. Berstel","year":"2002","unstructured":"Berstel, J., Boasson, L.: Formal properties of XML grammars and languages. Acta Inf.\u00a038(9), 649\u2013671 (2002)","journal-title":"Acta Inf."},{"key":"2_CR8","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"1137","DOI":"10.1007\/3-540-44957-4_76","volume-title":"Computational Logic - CL 2000","author":"G.J. Bex","year":"2000","unstructured":"Bex, G.J., Maneth, S., Neven, F.: A Formal Model for an Expressive Fragment of XSLT. In: Palamidessi, C., Moniz Pereira, L., Lloyd, J.W., Dahl, V., Furbach, U., Kerber, M., Lau, K.-K., Sagiv, Y., Stuckey, P.J. (eds.) CL 2000. LNCS (LNAI), vol.\u00a01861, pp. 1137\u20131151. Springer, Heidelberg (2000)"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Bex, G.J., Gelade, W., Martens, W., Neven, F.: Simplifying xml schema: effortless handling of nondeterministic regular expressions. In: \u00c7etintemel, U., Zdonik, S.B., Kossmann, D., Tatbul, N. (eds.) SIGMOD Conference, pp. 731\u2013744. ACM (2009)","DOI":"10.1145\/1559845.1559922"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Bex, G.J., Gelade, W., Neven, F., Vansummeren, S.: Learning deterministic regular expressions for the inference of schemas from XML data. TWEB\u00a04(4) (2010)","DOI":"10.1145\/1841909.1841911"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Bex, G.J., Neven, F., Schwentick, T., Vansummeren, S.: Inference of concise regular expressions and DTDs. ACM Trans. Database Syst.\u00a035(2) (2010)","DOI":"10.1145\/1735886.1735890"},{"key":"2_CR12","unstructured":"Bex, G.J., Neven, F., Vansummeren, S.: Inferring XML schema definitions from XML data. In: VLDB, pp. 998\u20131009 (2007)"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"Bex, G.J., Neven, F., Vansummeren, S.: Schemascope: a system for inferring and cleaning xml schemas. In: Wang, J.T.-L. (ed.) SIGMOD Conference, pp. 1259\u20131262. ACM (2008)","DOI":"10.1145\/1376616.1376750"},{"key":"2_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"862","DOI":"10.1007\/978-3-540-73420-8_74","volume-title":"Automata, Languages and Programming","author":"H. Bj\u00f6rklund","year":"2007","unstructured":"Bj\u00f6rklund, H., Boja\u0144czyk, M.: Bounded Depth Data Trees. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 862\u2013874. Springer, Heidelberg (2007)"},{"issue":"4","key":"2_CR15","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1145\/1862919.1862926","volume":"35","author":"H. Bj\u00f6rklund","year":"2010","unstructured":"Bj\u00f6rklund, H., Gelade, W., Martens, W.: Incremental xpath evaluation. ACM Trans. Database Syst.\u00a035(4), 29 (2010)","journal-title":"ACM Trans. Database Syst."},{"issue":"4-5","key":"2_CR16","doi-asserted-by":"publisher","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.\u00a0411(4-5), 702\u2013715 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR17","unstructured":"Bojanczyk, M.: Data monoids. In: Schwentick, D\u00fcrr [82], pp. 105\u2013116"},{"issue":"2","key":"2_CR18","doi-asserted-by":"publisher","first-page":"658","DOI":"10.1137\/050645427","volume":"38","author":"M. Bojanczyk","year":"2008","unstructured":"Bojanczyk, M., Colcombet, T.: Tree-walking automata do not recognize all regular languages. SIAM J. Comput.\u00a038(2), 658\u2013701 (2008)","journal-title":"SIAM J. Comput."},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"Bojanczyk, M., Lasota, S.: An extension of data automata that captures xpath. In: LICS, pp. 243\u2013252. IEEE Computer Society (2010)","DOI":"10.1109\/LICS.2010.33"},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Bojanczyk, M., Muscholl, A., Schwentick, T., Segoufin, L.: Two-variable logic on data trees and xml reasoning. J. ACM\u00a056(3) (2009)","DOI":"10.1145\/1516512.1516515"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"Bojanczyk, M., Parys, P.: XPath evaluation in linear time. In: Lenzerini, M., Lembo, D. (eds.) PODS, pp. 241\u2013250. ACM (2008)","DOI":"10.1145\/1376916.1376951"},{"issue":"4","key":"2_CR22","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/1989727.1989731","volume":"58","author":"M. Bojanczyk","year":"2011","unstructured":"Bojanczyk, M., Parys, P.: XPath evaluation in linear time. J. ACM\u00a058(4), 17 (2011)","journal-title":"J. ACM"},{"key":"2_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/11786986_15","volume-title":"Automata, Languages and Programming","author":"M. Boja\u0144czyk","year":"2006","unstructured":"Boja\u0144czyk, M., Samuelides, M., Schwentick, T., Segoufin, L.: Expressive Power of Pebble Automata. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006, Part I. LNCS, vol.\u00a04051, pp. 157\u2013168. Springer, Heidelberg (2006)"},{"key":"2_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-74240-1_1","volume-title":"Fundamentals of Computation Theory","author":"A. Bouajjani","year":"2007","unstructured":"Bouajjani, A., Habermehl, P., Jurski, Y., Sighireanu, M.: Rewriting Systems with Data. In: Csuhaj-Varj\u00fa, E., \u00c9sik, Z. (eds.) FCT 2007. LNCS, vol.\u00a04639, pp. 1\u201322. Springer, Heidelberg (2007)"},{"issue":"2","key":"2_CR25","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0890-5401(03)00038-5","volume":"182","author":"P. Bouyer","year":"2003","unstructured":"Bouyer, P., Petit, A., Therien, D.: An algebraic approach to data languages and timed languages. Inf. Comput.\u00a0182(2), 137\u2013162 (2003)","journal-title":"Inf. Comput."},{"key":"2_CR26","unstructured":"Bray, T., Paoli, J., Sperberg-McQueen, C.M.: Extensible markup language (XML) working draft. Technical report, W3C (1996), www.w3.org\/TR\/WD-xml-961114"},{"key":"2_CR27","unstructured":"Bray, T., Paoli, J., Sperberg-McQueen, C.M., Maler, E., Yergeau, F.: Extensible markup language (XML) 1.0 (fifth edition). Technical report, W3C (2008), www.w3.org\/TR\/2008\/REC-xml-20081126"},{"key":"2_CR28","unstructured":"Br\u00fcggemann-Klein, A., Wood, D.: Deterministic regular languages. Technical Report Bericht 38, Universit\u00e4t Freiburg, Institut f\u00fcr Informatik (1991)"},{"issue":"2","key":"2_CR29","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1006\/inco.1997.2688","volume":"140","author":"A. Br\u00fcggemann-Klein","year":"1998","unstructured":"Br\u00fcggemann-Klein, A., Wood, D.: One-unambiguous regular languages. Information and Computation\u00a0140(2), 229\u2013253 (1998)","journal-title":"Information and Computation"},{"key":"2_CR30","unstructured":"Br\u00fcggemann-Klein, A., Murata, M., Wood, D.: Regular tree languages over non-ranked alphabets (1998), http:\/\/hdl.handle.net\/1783.1\/738"},{"key":"2_CR31","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"J.R. B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, J.R.: Weak second-order arithmetic and finite automata. Z. Math. Logik Grundl. Math.\u00a06, 66\u201392 (1960)","journal-title":"Z. Math. Logik Grundl. Math."},{"key":"2_CR32","unstructured":"Chamberlin, D., Clark, J., Florescu, D., Robie, J., Simeon, J., Stefanascu, M.: XQuery 1.0: An XML query language (2002), http:\/\/www.w3.org\/TR\/xquery\/"},{"key":"2_CR33","unstructured":"Clark, J., Murata, M.: Relax ng specification. Technical report, OASIS Committee Specification Document (2001)"},{"key":"2_CR34","unstructured":"Clark, J.: XSL transformations version 1.0 (August 1999), http:\/\/www.w3.org\/TR\/xslt"},{"key":"2_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-3-642-22993-0_24","volume-title":"Mathematical Foundations of Computer Science 2011","author":"T. Colcombet","year":"2011","unstructured":"Colcombet, T., Ley, C., Puppis, G.: On the Use of Guards for Logics with Data. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol.\u00a06907, pp. 243\u2013255. Springer, Heidelberg (2011)"},{"key":"2_CR36","unstructured":"World Wide\u00a0Web Consortium. XML Path Language (XPath), Version 1.0. W3C Recommendation, November 16 (1999), http:\/\/www.w3.org\/TR\/xpath"},{"key":"2_CR37","unstructured":"World Wide\u00a0Web Consortium. XML Path Language (XPath), Version 2.0. W3C Recommendation, http:\/\/www.w3.org\/TR\/xpath20"},{"key":"2_CR38","unstructured":"World Wide\u00a0Web Consortium. XML schema, http:\/\/www.w3.org\/XML\/Schema"},{"key":"2_CR39","doi-asserted-by":"crossref","unstructured":"Demri, S., Lazic, R.: LTL with the freeze quantifier and register automata. ACM Trans. Comput. Log.\u00a010(3) (2009)","DOI":"10.1145\/1507244.1507246"},{"key":"2_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-642-12032-9_13","volume-title":"Foundations of Software Science and Computational Structures","author":"S. Demri","year":"2010","unstructured":"Demri, S., Sangnier, A.: When Model-Checking Freeze ltl Over Counter Machines Becomes Decidable. In: Ong, L. (ed.) FOSSACS 2010. LNCS, vol.\u00a06014, pp. 176\u2013190. Springer, Heidelberg (2010)"},{"issue":"5","key":"2_CR41","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/S0022-0000(70)80041-1","volume":"4","author":"J. Doner","year":"1970","unstructured":"Doner, J.: Tree acceptors and some of their applications. J. Comput. Syst. Sci.\u00a04(5), 406\u2013451 (1970)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR42","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1090\/S0002-9947-1961-0139530-9","volume":"98","author":"C.C. Elgot","year":"1961","unstructured":"Elgot, C.C.: Decision problems of finite automata design and related arithmetics. Transactions of The American Mathematical Society\u00a098, 21\u201321 (1961)","journal-title":"Transactions of The American Mathematical Society"},{"key":"2_CR43","doi-asserted-by":"crossref","unstructured":"Engelfriet, J., Hoogeboom, H.J.: Automata with nested pebbles capture first-order logic with transitive closure. Logical Methods in Computer Science\u00a03(2) (2007)","DOI":"10.2168\/LMCS-3(2:3)2007"},{"key":"2_CR44","doi-asserted-by":"crossref","unstructured":"Engelfriet, J., Hoogeboom, H.J., Samwel, B.: Xml transformation by tree-walking transducers with invisible pebbles. In: Libkin, L. (ed.) PODS, pp. 63\u201372. ACM (2007)","DOI":"10.1145\/1265530.1265540"},{"issue":"1","key":"2_CR45","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1006\/inco.1999.2807","volume":"154","author":"J. Engelfriet","year":"1999","unstructured":"Engelfriet, J., Maneth, S.: Macro tree transducers, attribute grammars, and mso definable tree translations. Inf. Comput.\u00a0154(1), 34\u201391 (1999)","journal-title":"Inf. Comput."},{"key":"2_CR46","doi-asserted-by":"crossref","unstructured":"Figueira, D.: Satisfiability of downward XPath with data equality tests. In: PODS, pp. 197\u2013206 (2009)","DOI":"10.1145\/1559795.1559827"},{"key":"2_CR47","doi-asserted-by":"crossref","unstructured":"Figueira, D.: Forward-XPath and extended register automata on data-trees. In: ICDT, pp. 231\u2013241 (2010)","DOI":"10.1145\/1804669.1804699"},{"key":"2_CR48","unstructured":"Figueira, D., Segoufin, L.: Bottom-up automata on data trees and vertical xpath. In: Schwentick, D\u00fcrr [82], pp. 93\u2013104"},{"issue":"1","key":"2_CR49","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1023\/A:1021560618289","volume":"7","author":"M.N. Garofalakis","year":"2003","unstructured":"Garofalakis, M.N., Gionis, A., Rastogi, R., Seshadri, S., Shim, K.: Xtract: Learning document type descriptors from xml document collections. Data Min. Knowl. Discov.\u00a07(1), 23\u201356 (2003)","journal-title":"Data Min. Knowl. Discov."},{"key":"2_CR50","doi-asserted-by":"crossref","unstructured":"Van den Bussche, J., Bex, G.J., Neven, F.: DTDs versus XML schema: A practical study. In: International Workshop on the World Wide Web and Databases, pp. 79\u201384 (2004)","DOI":"10.1145\/1017074.1017095"},{"key":"2_CR51","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-642-03816-7_32","volume-title":"Mathematical Foundations of Computer Science 2009","author":"W. Gelade","year":"2009","unstructured":"Gelade, W., Gyssens, M., Martens, W.: Regular Expressions with Counting: Weak versus Strong Determinism. In: Kr\u00e1lovi\u010d, R., Niwi\u0144ski, D. (eds.) MFCS 2009. LNCS, vol.\u00a05734, pp. 369\u2013381. Springer, Heidelberg (2009)"},{"key":"2_CR52","series-title":"LIPIcs","first-page":"325","volume-title":"STACS","author":"W. Gelade","year":"2008","unstructured":"Gelade, W., Neven, F.: Succinctness of the complement and intersection of regular expressions. In: Albers, S., Weil, P. (eds.) STACS. LIPIcs, vol.\u00a01, pp. 325\u2013336. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany (2008)"},{"key":"2_CR53","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1070\/RM1961v016n05ABEH004112","volume":"16","author":"V.M. Glushkov","year":"1961","unstructured":"Glushkov, V.M.: The abstract theory of automata. Russian Math. Surveys\u00a016, 1\u201353 (1961)","journal-title":"Russian Math. Surveys"},{"key":"2_CR54","unstructured":"Goris, E., Marx, M.: Looping caterpillars. In: LICS 2005 (2005)"},{"issue":"2","key":"2_CR55","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1145\/1071610.1071614","volume":"30","author":"G. Gottlob","year":"2005","unstructured":"Gottlob, G., Koch, C., Pichler, R.: Efficient algorithms for processing xpath queries. ACM Trans. Database Syst.\u00a030(2), 444\u2013491 (2005)","journal-title":"ACM Trans. Database Syst."},{"key":"2_CR56","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/3-540-36285-1_12","volume-title":"Database Theory - ICDT 2003","author":"T.J. Green","year":"2002","unstructured":"Green, T.J., Miklau, G., Onizuka, M., Suciu, D.: Processing XML Streams with Deterministic Automata. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol.\u00a02572, pp. 173\u2013189. Springer, Heidelberg (2002)"},{"issue":"2","key":"2_CR57","doi-asserted-by":"publisher","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.\u00a0134(2), 329\u2013363 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR58","doi-asserted-by":"crossref","unstructured":"Koch, C., Scherzinger, S., Schweikardt, N., Stegmaier, B.: FluXQuery: An optimizing XQuery processor for streaming XML data. In: Proc. 30th International Conference on Very Large Data Bases (VLDB), Toronto, pp. 1309\u20131312 (2004)","DOI":"10.1016\/B978-012088469-8\/50134-0"},{"key":"2_CR59","doi-asserted-by":"crossref","unstructured":"Libkin, L.: Logics for unranked trees: An overview. Logical Methods in Computer Science 2(3) (2006)","DOI":"10.2168\/LMCS-2(3:2)2006"},{"key":"2_CR60","doi-asserted-by":"crossref","unstructured":"Maneth, S., Berlea, A., Perst, T., Seidl, H.: XML type checking with macro tree transducers. In: PODS, pp. 283\u2013294 (2005)","DOI":"10.1145\/1065167.1065203"},{"key":"2_CR61","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/11965893_18","volume-title":"Database Theory \u2013 ICDT 2007","author":"S. Maneth","year":"2006","unstructured":"Maneth, S., Perst, T., Seidl, H.: Exact XML Type Checking in Polynomial Time. In: Schwentick, T., Suciu, D. (eds.) ICDT 2007. LNCS, vol.\u00a04353, pp. 254\u2013268. Springer, Heidelberg (2006)"},{"issue":"3","key":"2_CR62","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/j.jcss.2006.10.005","volume":"73","author":"W. Martens","year":"2007","unstructured":"Martens, W., Neven, F.: Frontiers of tractability for typechecking simple xml transformations. J. Comput. Syst. Sci.\u00a073(3), 362\u2013390 (2007)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"2_CR63","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/1324185.1324188","volume":"36","author":"W. Martens","year":"2007","unstructured":"Martens, W., Neven, F., Schwentick, T.: Simple off the shelf abstractions for XML schema. SIGMOD Record\u00a036(3), 15\u201322 (2007)","journal-title":"SIGMOD Record"},{"issue":"4","key":"2_CR64","doi-asserted-by":"publisher","first-page":"1486","DOI":"10.1137\/080743457","volume":"39","author":"W. Martens","year":"2009","unstructured":"Martens, W., Neven, F., Schwentick, T.: Complexity of decision problems for XML schemas and chain regular expressions. SIAM J. Comput.\u00a039(4), 1486\u20131530 (2009)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"2_CR65","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1145\/1166074.1166076","volume":"31","author":"W. Martens","year":"2006","unstructured":"Martens, W., Neven, F., Schwentick, T., Bex, G.J.: Expressiveness and complexity of XML schema. ACM Trans. Database Syst.\u00a031(3), 770\u2013813 (2006)","journal-title":"ACM Trans. Database Syst."},{"key":"2_CR66","unstructured":"Marx, M., de Rijke, M.: Semantic characterizations of XPath. In: TDM 2004 Workshop on XML Databases and Information Retrieval, Twente, The Netherlands, June 21 (2004)"},{"issue":"4","key":"2_CR67","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1145\/1114244.1114247","volume":"30","author":"M. Marx","year":"2005","unstructured":"Marx, M.: Conditional xpath. ACM Trans. Database Syst.\u00a030(4), 929\u2013959 (2005)","journal-title":"ACM Trans. Database Syst."},{"key":"2_CR68","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-642-03754-2_3","volume-title":"Reasoning Web. Semantic Technologies for Information Systems","author":"M. Marx","year":"2009","unstructured":"Marx, M.: Logical Foundations of XML and XQuery. In: Tessaris, S., Franconi, E., Eiter, T., Gutierrez, C., Handschuh, S., Rousset, M.-C., Schmidt, R.A. (eds.) Reasoning Web 2009. LNCS, vol.\u00a05689, pp. 111\u2013157. Springer, Heidelberg (2009)"},{"issue":"2","key":"2_CR69","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/1083784.1083792","volume":"34","author":"M. Marx","year":"2005","unstructured":"Marx, M., de Rijke, M.: Semantic characterizations of navigational xpath. SIGMOD Record\u00a034(2), 41\u201346 (2005)","journal-title":"SIGMOD Record"},{"issue":"1","key":"2_CR70","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/S0022-0000(02)00030-2","volume":"66","author":"T. Milo","year":"2003","unstructured":"Milo, T., Suciu, D., Vianu, V.: Typechecking for xml transformers. J. Comput. Syst. Sci.\u00a066(1), 66\u201397 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR71","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-540-30570-5_2","volume-title":"Database Theory - ICDT 2005","author":"A. M\u00f8ller","year":"2005","unstructured":"M\u00f8ller, A., Schwartzbach, M.I.: The Design Space of Type Checkers for XML Transformation Languages. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol.\u00a03363, pp. 17\u201336. Springer, Heidelberg (2005)"},{"key":"2_CR72","unstructured":"Murata, M.: Forest-regular languages and tree-regular languages. Technical report, Fuji Xerox, Japan. Technical Report (1995)"},{"issue":"4","key":"2_CR73","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1145\/1111627.1111631","volume":"5","author":"M. Murata","year":"2005","unstructured":"Murata, M., Lee, D., Mani, M., Kawaguchi, K.: Taxonomy of XML schema languages using formal language theory. ACM Trans. Internet Techn.\u00a05(4), 660\u2013704 (2005)","journal-title":"ACM Trans. Internet Techn."},{"key":"2_CR74","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1016\/S0304-3975(01)00301-2","volume":"275","author":"F. Neven","year":"2002","unstructured":"Neven, F., Schwentick, T.: Query automata over finite trees. Theoretical Computer Science\u00a0275, 633\u2013674 (2002)","journal-title":"Theoretical Computer Science"},{"key":"2_CR75","doi-asserted-by":"crossref","unstructured":"Neven, F.: Automata, logic, and XML. In: CSL, pp. 2\u201326 (2002)","DOI":"10.1007\/3-540-45793-3_2"},{"issue":"3","key":"2_CR76","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1145\/601858.601869","volume":"31","author":"F. Neven","year":"2002","unstructured":"Neven, F.: Automata theory for XML researchers. SIGMOD Record\u00a031(3), 39\u201346 (2002)","journal-title":"SIGMOD Record"},{"issue":"1-2","key":"2_CR77","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1016\/S0304-3975(01)00301-2","volume":"275","author":"F. Neven","year":"2002","unstructured":"Neven, F., Schwentick, T.: Query automata over finite trees. Theoretical Computer Science\u00a0275(1-2), 633\u2013674 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"2_CR78","first-page":"86","volume":"183","author":"F. Neven","year":"2003","unstructured":"Neven, F., Schwentick, T.: On the power of tree-walking automata. Information and Control\u00a0183(1), 86\u2013103 (2003)","journal-title":"Information and Control"},{"key":"2_CR79","doi-asserted-by":"crossref","unstructured":"Neven, F., Schwentick, T.: On the complexity of XPath containment in the presence of disjunction, DTDs, and variables. Logical Methods in Computer Science\u00a02(3) (2006)","DOI":"10.2168\/LMCS-2(3:1)2006"},{"key":"2_CR80","unstructured":"Potthoff, A.: Logische Klassifizierung regul\u00e4rer Baumsprachen. Doctor\u2019s thesis, Institut f\u00fcr Informatik u. Prakt. Math., Universit\u00e4t Kiel (1994)"},{"issue":"3","key":"2_CR81","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/j.jcss.2006.10.003","volume":"73","author":"T. Schwentick","year":"2007","unstructured":"Schwentick, T.: Automata for XML - a survey. J. Comput. Syst. Sci.\u00a073(3), 289\u2013315 (2007)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR82","unstructured":"Schwentick, T., D\u00fcrr, C. (eds.): 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, Dortmund, Germany, March 10-12. LIPIcs, vol.\u00a09. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2011)"},{"key":"2_CR83","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/11874683_3","volume-title":"Computer Science Logic","author":"L. Segoufin","year":"2006","unstructured":"Segoufin, L.: Automata and Logics for Words and Trees over an Infinite Alphabet. In: \u00c9sik, Z. (ed.) CSL 2006. LNCS, vol.\u00a04207, pp. 41\u201357. Springer, Heidelberg (2006)"},{"issue":"1","key":"2_CR84","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1276301.1276308","volume":"36","author":"L. Segoufin","year":"2007","unstructured":"Segoufin, L.: Static analysis of xml processing with data values. SIGMOD Record\u00a036(1), 31\u201338 (2007)","journal-title":"SIGMOD Record"},{"key":"2_CR85","doi-asserted-by":"crossref","unstructured":"Segoufin, L., Vianu, V.: Validating streaming XML documents. In: PODS 2002, pp. 53\u201364 (2002)","DOI":"10.1145\/543613.543622"},{"key":"2_CR86","doi-asserted-by":"crossref","unstructured":"ten Cate, B., Lutz, C.: The complexity of query containment in expressive fragments of xpath 2.0. J. ACM\u00a056(6) (2009)","DOI":"10.1145\/1568318.1568321"},{"issue":"4","key":"2_CR87","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/s00224-008-9151-9","volume":"44","author":"B. Cate ten","year":"2009","unstructured":"ten Cate, B., Marx, M.: Axiomatizing the logical core of xpath 2.0. Theory Comput. Syst.\u00a044(4), 561\u2013589 (2009)","journal-title":"Theory Comput. Syst."},{"key":"2_CR88","doi-asserted-by":"crossref","unstructured":"ten Cate, B., Segoufin, L.: Transitive closure logic, nested tree walking automata, and xpath. J. ACM\u00a057(3) (2010)","DOI":"10.1145\/1706591.1706598"},{"issue":"1","key":"2_CR89","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J.W. Thatcher","year":"1968","unstructured":"Thatcher, J.W., Wright, J.B.: Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical Systems Theory\u00a02(1), 57\u201381 (1968)","journal-title":"Mathematical Systems Theory"},{"key":"2_CR90","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/978-3-642-59126-6_7","volume-title":"Handbook of Formal Languages","author":"W. Thomas","year":"1997","unstructured":"Thomas, W.: Languages, Automata, and Logic. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.\u00a0III, pp. 389\u2013455. Springer, Heidelberg (1997)"},{"key":"2_CR91","first-page":"326","volume":"140","author":"B.A. Trakhtenbrot","year":"1961","unstructured":"Trakhtenbrot, B.A.: Finite automata and logic of monadic predicates. Doklady Akademii Nauk SSSR\u00a0140, 326\u2013329 (1961)","journal-title":"Doklady Akademii Nauk SSSR"}],"container-title":["Lecture Notes in Computer Science","Foundations of Information and Knowledge Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-28472-4_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T06:03:31Z","timestamp":1742623411000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28472-4_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642284717","9783642284724"],"references-count":91,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28472-4_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}