Logics for Unordered Trees with Data Constraints on Siblings

Adrien Boiret 1 Vincent Hugot 1 Joachim Niehren 1 Ralf Treinen 2
1 LINKS - Linking Dynamic Data
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
2 PPS - Preuves, Programmes et Systèmes
Abstract : We study counting monadic second-order logics (CMso) for unordered data trees. Our objective is to enhance this logic with data constraints for comparing string data values attached to sibling edges of a data tree. We show that CMso satisfiability becomes undecidable when adding data constraints between siblings that can check the equality of factors of data values. For more restricted data constraints that can only check the equality of prefixes, we show that it becomes decidable, and propose a related automaton model with good complexities. This restricted logic is relevant to applications such as checking well-formedness properties of semi-structured databases and file trees. Our decidability results are obtained by compilation of CMso to automata for unordered trees, where both are enhanced with data constraints in a novel manner.
Keywords : logics unordered trees
Type de document :
Communication dans un congrès
LATA : 9th International Conference on Language and Automata Theory and Applications, Mar 2015, Nice, France. pp.175-187, 〈http://grammars.grlmc.com/lata2015/〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01088761
Contributeur : Inria Links <>
Soumis le : vendredi 28 novembre 2014 - 15:56:47
Dernière modification le : vendredi 22 mars 2019 - 01:34:02
Document(s) archivé(s) le : vendredi 14 avril 2017 - 23:09:12

Fichier

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

Identifiants

  • HAL Id : hal-01088761, version 1

Collections

UNIV-PARIS7 | INRIA | PPS | CRISTAL-LINKS | USPC | CRISTAL | UNIV-LILLE

Citation

Adrien Boiret, Vincent Hugot, Joachim Niehren, Ralf Treinen. Logics for Unordered Trees with Data Constraints on Siblings. LATA : 9th International Conference on Language and Automata Theory and Applications, Mar 2015, Nice, France. pp.175-187, 〈http://grammars.grlmc.com/lata2015/〉. 〈hal-01088761〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

334

Téléchargements de fichiers

206

Contact


archive-ouverte@inria.fr