A Sequent Calculus for a Modal Logic on Finite Data Trees - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2015

A Sequent Calculus for a Modal Logic on Finite Data Trees

Résumé

We investigate the proof theory of a modal fragment of XPath equipped with data (in)equality tests over finite data trees, i.e. over finite unranked trees where nodes are labelled with both a symbol from a finite alphabet and a single data value from an infinite domain. We present a sound and complete sequent calculus for this logic, which yields the optimal PSPACE complexity bound for its validity problem.
Fichier principal
Vignette du fichier
main.pdf (631.33 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01191172 , version 1 (01-09-2015)
hal-01191172 , version 2 (07-09-2015)

Licence

Paternité - Partage selon les Conditions Initiales

Identifiants

  • HAL Id : hal-01191172 , version 1

Citer

David Baelde, Simon Lunel, Sylvain Schmitz. A Sequent Calculus for a Modal Logic on Finite Data Trees. 2015. ⟨hal-01191172v1⟩
512 Consultations
345 Téléchargements

Partager

Gmail Facebook X LinkedIn More