On Core XPath with Inflationary Fixed Points∗
Google Inc., 1600 Amphitheatre Parkway, Mountain View, CA
2 Department of Computer Science, University of California at Santa Cruz, 1156 High Street, Santa Cruz, CA 95064, USA.
Accepted: 28 September 2012
We prove the undecidability of Core XPath 1.0 (CXP) [G. Gottlob and C. Koch, in Proc. of 17th Ann. IEEE Symp. on Logic in Computer Science, LICS ’02 (Copenhagen, July 2002). IEEE CS Press (2002) 189–202.] extended with an Inflationary Fixed Point (IFP) operator. More specifically, we prove that the satisfiability problem of this language is undecidable. In fact, the fragment of CXP+IFP containing only the self and descendant axes is already undecidable.
Mathematics Subject Classification: 68P15 / 03B45 / 03B70
Key words: Modal Logic / fixed points / XML Databases / XPath
© EDP Sciences 2012