Voir la notice de l'article provenant de la source Numdam
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.
@article{ITA_2013__47_1_3_0,
author = {Afanasiev, Loredana and Cate, Balder Ten},
title = {On {Core} {XPath} with {Inflationary} {Fixed} {Points}},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {3--23},
publisher = {EDP-Sciences},
volume = {47},
number = {1},
year = {2013},
doi = {10.1051/ita/2012027},
mrnumber = {3072309},
zbl = {1270.68100},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2012027/}
}
TY - JOUR AU - Afanasiev, Loredana AU - Cate, Balder Ten TI - On Core XPath with Inflationary Fixed Points JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2013 SP - 3 EP - 23 VL - 47 IS - 1 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2012027/ DO - 10.1051/ita/2012027 LA - en ID - ITA_2013__47_1_3_0 ER -
%0 Journal Article %A Afanasiev, Loredana %A Cate, Balder Ten %T On Core XPath with Inflationary Fixed Points %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2013 %P 3-23 %V 47 %N 1 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2012027/ %R 10.1051/ita/2012027 %G en %F ITA_2013__47_1_3_0
Afanasiev, Loredana; Cate, Balder Ten. On Core XPath with Inflationary Fixed Points. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) no. 1, pp. 3-23. doi: 10.1051/ita/2012027
Cité par Sources :