{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T04:48:47Z","timestamp":1745470127686,"version":"3.40.4"},"reference-count":21,"publisher":"EDP Sciences","issue":"1","license":[{"start":{"date-parts":[[2012,12,19]],"date-time":"2012-12-19T00:00:00Z","timestamp":1355875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"accepted":{"date-parts":[[2012,9,28]]},"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>We prove the undecidability of Core XPath 1.0 (CXP) [G. Gottlob and C. Koch, in<jats:italic>Proc. of 17th Ann. IEEE Symp. on Logic in Computer Science, LICS \u201902 (Copenhagen, July 2002).<\/jats:italic>IEEE CS Press (2002) 189\u2013202.] extended with an<jats:italic>Inflationary Fixed Point (IFP)<\/jats:italic>operator. More specifically, we prove that the satisfiability problem of this language is undecidable. In fact, the fragment of CXP+IFP containing only the<jats:italic>self<\/jats:italic>and<jats:italic>descendant<\/jats:italic>axes is already undecidable.<\/jats:p>","DOI":"10.1051\/ita\/2012027","type":"journal-article","created":{"date-parts":[[2012,12,19]],"date-time":"2012-12-19T14:23:23Z","timestamp":1355927003000},"page":"3-23","source":"Crossref","is-referenced-by-count":1,"title":["On Core XPath with Inflationary Fixed Points"],"prefix":"10.1051","volume":"47","author":[{"given":"Loredana","family":"Afanasiev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Balder ten","family":"Cate","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2012,12,19]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"L. Afanasiev, T. Grust, M.J. Marx, J. Rittinger and J. Teubner, An inflationary fixed point operator in XQuery, in Proc. of 24th Int. Conf. on Data Engineering, ICDE \u201908 (Cancun, Apr. 2008). IEEE CS Press (2008) 1504\u20131506.","DOI":"10.1109\/ICDE.2008.4497604"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"L. Afanasiev, T. Grust, M.J. Marx, J. Rittinger and J. Teubner, Recursion in XQuery: Put your distributivity safety belt on, in Proc. of 12th Int. Conf. on Extending Database Technology, EDBT \u201909 (St. Petersburg, March 2009). ACM Press (2009) 345\u2013356.","DOI":"10.1145\/1516360.1516401"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"P. Blackburn, M. de Rijke and Y. Venema, Modal Logic, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press 53 (2002).","DOI":"10.1017\/CBO9781107050884"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"P. Boncz, T. Grust, M. van Keulen, S. Manegold, J. Rittinger and J. Teuber, MonetDB\/XQuery: a fast XQuery processor powered by a relational engine, in Proc. of 25th ACM SIGMOD Int. Conf. on Management of Data, SIGMOD \u201906 (Chicago, IL, June 2006). ACM Press (2006) 479\u2013490.","DOI":"10.1145\/1142473.1142527"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"E. B\u00f6rger, E. Gr\u00e4del and Y. Gurevich, The Classical Decision Problem. Springer (1997).","DOI":"10.1007\/978-3-642-59207-2"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"J. Bradfield and C. Stirling, Modal \u03bc-calculi, in Handbook of Modal Logic, edited by P. Blackburn, J. van Benthem and F. Wolter. Elsevier (2007) 721\u2013756.","DOI":"10.1016\/S1570-2464(07)80015-2"},{"key":"R7","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1145\/976706.976710","volume":"5","author":"Dawar","year":"2004","journal-title":"ACM Trans. Comput. Log."},{"key":"R8","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1007\/s00778-002-0080-y","volume":"11","author":"Fiebig","year":"2002","journal-title":"VLDB J."},{"key":"R9","unstructured":"Georgetown Protein Information Resource, Protein sequence database (2001). Available on http:\/\/www.cs.washington.edu\/research\/xmldatasets\/"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"G. Gottlob and C. Koch, Monadic queries over tree-structured data, in Proc. of 17th Ann. IEEE Symp. on Logic in Computer Science, LICS \u201902 (Copenhagen, July 2002). IEEE CS Press (2002) 189\u2013202.","DOI":"10.1109\/LICS.2002.1029828"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"E. Gr\u00e4del, M. Otto and E. Rosen, Undecidability results on two-variable logics, in Proc. of 14th Ann. Symp. on Theoretical Aspects of Computer Science, STACS \u201997 (L\u00fcbeck, Feb.\/March 1997), Lect. Notes Comput. Sci. vol. 1200, edited by R. Reischuk and M. Morvan, Springer (1997) 249\u2013260.","DOI":"10.1007\/BFb0023464"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"N. Immerman, Descriptive Complexity. Springer (1999).","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"H.V. Jagadish, L.V.S. Lakshmanan, D. Srivastava and K. Thompson, TAX: A tree algebra for XML, in Revised Papers from 8th Int. Workshop on Database Programming Languages, DBPL 2001 (Frascati, Sept. 2001), Lect. Notes Comput. Sci. vol. 2397, edited by G. Ghelli and G. Grahne, Springer (2002) 149\u2013164.","DOI":"10.1007\/3-540-46093-4_9"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"D. Janin and I. Walukiewicz, On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic, in Proc. of 7th Int. Conf. on Concurrency Theory, CONCUR 1996 (Pisa, Aug. 1996), Lect. Notes Comput. Sci. vol. 1119, edited by U. Montanari and V. Sassone, Springer (1996) 263\u2013277.","DOI":"10.1007\/3-540-61604-7_60"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"M. Marx, XPath with conditional axis relations, in Proc. of 9th Int. Conf. on Extending Database Technology, EDBT 2004 (Heraclion, March 2004), Lect. Notes Comput. Sci. vol. 2992, edited by E. Bertino et al., Springer (2004) 477\u2013494.","DOI":"10.1007\/978-3-540-24741-8_28"},{"key":"R16","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1145\/1083784.1083792","volume":"34","author":"Marx","year":"2005","journal-title":"ACM SIGMOD Record"},{"key":"R17","unstructured":"B. ten Cate, Regular XPath: algebra, logic and automata, unpublished note presented at AUTOMATHA Workshop on Algebraic Theory of Automata and Logic (2006)."},{"key":"R18","doi-asserted-by":"crossref","unstructured":"Thomas W., Languages, automata, and logic, Handbook of Formal Languages, Beyond Words vol. 3, edited by G. Rozenberg and A. Salomaa, Springer (1997) 389\u2013455.","DOI":"10.1007\/978-3-642-59126-6_7"},{"key":"R19","unstructured":"XML path language (XPath) version 1.0, edited by J. Clark and S. DeRose. World Wide Web Consortium (1999). http:\/\/www.w3.org\/TR\/xpath\/."},{"key":"R20","unstructured":"XML path language (XPath) 2.0, edited by A. Berglund et al. World Wide Web Consortium (2007). Available on http:\/\/www.w3.org\/TR\/xpath20\/."},{"key":"R21","unstructured":"XQuery 1.0 : An XML query language, edited by S. Boag et al. World Wide Web Consortium (2007). Available on http:\/\/www.w3.org\/TR\/xquery\/."}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2012027\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T23:22:58Z","timestamp":1745450578000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2012027"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12,19]]},"references-count":21,"journal-issue":{"issue":"1"},"alternative-id":["ita120041"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2012027","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"type":"print","value":"0988-3754"},{"type":"electronic","value":"1290-385X"}],"subject":[],"published":{"date-parts":[[2012,12,19]]}}}