Expressiveness of a spatial logic for trees - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2005

Expressiveness of a spatial logic for trees

Résumé

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.
Fichier principal
Vignette du fichier
lics2005.pdf (188.47 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00536696 , version 1 (16-11-2010)

Identifiants

  • HAL Id : inria-00536696 , version 1

Citer

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. pp.280--289. ⟨inria-00536696⟩
88 Consultations
179 Téléchargements

Partager

Gmail Facebook X LinkedIn More