| Issue |
RAIRO-Theor. Inf. Appl.
Volume 47, Number 1, January-March 2013
6th Workshop on Fixed Points in Computer Science (FICS'09)
|
|
|---|---|---|
| Page(s) | 3 - 23 | |
| DOI | https://doi.org/10.1051/ita/2012027 | |
| Published online | 19 December 2012 | |
On Core XPath with Inflationary Fixed Points∗
1
Google Inc., 1600 Amphitheatre Parkway, Mountain View, CA
94043,
USA
loredana.afanasiev@gmail.com
2
Department of Computer Science, University of California at Santa
Cruz, 1156 High
Street, Santa Cruz,
CA
95064,
USA.
btencate@ucsc.edu
Received:
28
September
2012
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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.