Expressiveness of a spatial logic for trees

Abstract : In this paper we investigate the quantifier-free fragment of the TQL logic proposed by Cardelli and Ghelli. The TQL logic, inspired from the ambient logic, is the core of a query language for semistructured data represented as unranked and unordered trees. The fragment we consider here, named STL, contains as main features spatial composition and location as well as a fixed point construct. We prove that satisfiability for STL is undecidable.We show also that STL is strictly more expressive that the Presburger monadic second-order logic (PMSO) of Seidl, Schwentick and Muscholl when interpreted over unranked and unordered edge-labeled trees. We define a class of tree automata whose transitions are conditioned by arithmetical constraints; we show then how to compute from a closed STL formula a tree automaton accepting precisely the models of the formula. Finally, still using our tree automata framework, we exhibit some syntactic restrictions over STL formulae that allow us to capture precisely the logics MSO and PMSO.
Type de document :
Communication dans un congrès
20th Annual IEEE Symposium on Logic in Computer Science, 2005, Chicago, United States. IEEE Computer Science Press, pp.280--289, 2005
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00536696
Contributeur : Iovka Boneva <>
Soumis le : mardi 16 novembre 2010 - 17:32:11
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : jeudi 17 février 2011 - 03:07:21

Fichier

lics2005.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00536696, version 1

Collections

Citation

Iovka Boneva, Jean-Marc Talbot, Sophie Tison. Expressiveness of a spatial logic for trees. 20th Annual IEEE Symposium on Logic in Computer Science, 2005, Chicago, United States. IEEE Computer Science Press, pp.280--289, 2005. 〈inria-00536696〉

Partager

Métriques

Consultations de la notice

168

Téléchargements de fichiers

117