Logics for Unordered Trees with Data Constraints - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Journal of Computer and System Sciences Année : 2019

Logics for Unordered Trees with Data Constraints

Adrien Boiret
  • Fonction : Auteur
  • PersonId : 958173
Vincent Hugot
  • Fonction : Auteur
  • PersonId : 881395
Joachim Niehren
Ralf Treinen
  • Fonction : Auteur
  • PersonId : 845934

Résumé

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. Comparisons between data values at arbitrary positions of a data tree quickly lead to undecidability. Therefore, we restrict ourselves to comparing sibling data values of unordered trees. But even in this case CMso remains undecidable when allowing data comparisons that can check the equality of string factors. However, for more restricted data constraints that can only check the equality of string prefixes, it becomes decidable. This decidability result is obtained by reduction to WSkS. Furthermore, we exhibit a restricted class of constraints which can be used in transitions of tree automata, resulting in a model with tractable complexity, which can be extended with structural equality tests between siblings. This practical restriction is relevant to applications such as checking well-formedness properties of file system trees.
Fichier principal
Vignette du fichier
0.pdf (566.76 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01176763 , version 1 (13-11-2018)
hal-01176763 , version 2 (19-12-2018)

Identifiants

Citer

Adrien Boiret, Vincent Hugot, Joachim Niehren, Ralf Treinen. Logics for Unordered Trees with Data Constraints. Journal of Computer and System Sciences, 2019, pp.40. ⟨10.1016/j.jcss.2018.11.004⟩. ⟨hal-01176763v2⟩
438 Consultations
265 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More