Geodesic
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

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.

DOI : 10.1051/ita/2012027
Classification : 68P15, 03B45, 03B70
Keywords: modal logic, fixed points, XML databases, XPath 
@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 :