Bounded Repairability for Regular Tree Languages
Type de document :
Compte-rendu et recension critique d'ouvrage
DOI :
Titre :
Bounded Repairability for Regular Tree Languages
Auteur(s) :
Bourhis, Pierre [Auteur]
Linking Dynamic Data [LINKS]
Riveros, Cristian [Auteur]
Pontificia Universidad Católica de Chile [UC]
Staworko, Slawomir [Auteur]
Linking Dynamic Data [LINKS]
Puppis, Gabriele [Auteur]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Linking Dynamic Data [LINKS]
Riveros, Cristian [Auteur]
Pontificia Universidad Católica de Chile [UC]
Staworko, Slawomir [Auteur]
Linking Dynamic Data [LINKS]
Puppis, Gabriele [Auteur]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Titre de la revue :
ACM Transactions on Database Systems
Pagination :
1-45
Éditeur :
Association for Computing Machinery
Date de publication :
2016-06
ISSN :
0362-5915
Discipline(s) HAL :
Informatique [cs]/Base de données [cs.DB]
Informatique [cs]/Théorie et langage formel [cs.FL]
Informatique [cs]/Théorie et langage formel [cs.FL]
Résumé en anglais : [en]
We study the problem of bounded repairability of a given restriction tree language R into a target tree language T. More precisely, we say that R is bounded repairable w.r.t. T if there exists a bound on the number of ...
Lire la suite >We study the problem of bounded repairability of a given restriction tree language R into a target tree language T. More precisely, we say that R is bounded repairable w.r.t. T if there exists a bound on the number of standard tree editing operations necessary to apply to any tree in R in order to obtain a tree in T. We consider a number of possible specifications for tree languages: bottom-up tree automata (on curry encoding of unranked trees) that capture the class of XML Schemas and DTDs. We also consider a special case when the restriction language R is universal, i.e., contains all trees over a given alphabet. We give an effective characterization of bounded repairability between pairs of tree languages represented with automata. This characterization introduces two tools, synopsis trees and a coverage relation between them, allowing one to reason about tree languages that undergo a bounded number of editing operations. We then employ this characterization to provide upper bounds to the complexity of deciding bounded repairability and we show that these bounds are tight. In particular, when the input tree languages are specified with arbitrary bottom-up automata, the problem is coNEXPTIME-complete. The problem remains coNEXPTIME-complete even if we use deterministic non-recursive DTDs to specify the input languages. The complexity of the problem can be reduced if we assume that the alphabet, the set of node labels, is fixed: the problem becomes PSPACE-complete for non-recursive DTDs and coNP-complete for deterministic non-recursive DTDs. Finally, when the restriction tree language R is universal, we show that the bounded repairability problem becomes EXPTIME-complete if the target language is specified by an arbitrary bottom-up tree automaton and becomes tractable (PTIME-complete, in fact) when a deterministic bottom-up automaton is used.Lire moins >
Lire la suite >We study the problem of bounded repairability of a given restriction tree language R into a target tree language T. More precisely, we say that R is bounded repairable w.r.t. T if there exists a bound on the number of standard tree editing operations necessary to apply to any tree in R in order to obtain a tree in T. We consider a number of possible specifications for tree languages: bottom-up tree automata (on curry encoding of unranked trees) that capture the class of XML Schemas and DTDs. We also consider a special case when the restriction language R is universal, i.e., contains all trees over a given alphabet. We give an effective characterization of bounded repairability between pairs of tree languages represented with automata. This characterization introduces two tools, synopsis trees and a coverage relation between them, allowing one to reason about tree languages that undergo a bounded number of editing operations. We then employ this characterization to provide upper bounds to the complexity of deciding bounded repairability and we show that these bounds are tight. In particular, when the input tree languages are specified with arbitrary bottom-up automata, the problem is coNEXPTIME-complete. The problem remains coNEXPTIME-complete even if we use deterministic non-recursive DTDs to specify the input languages. The complexity of the problem can be reduced if we assume that the alphabet, the set of node labels, is fixed: the problem becomes PSPACE-complete for non-recursive DTDs and coNP-complete for deterministic non-recursive DTDs. Finally, when the restriction tree language R is universal, we show that the bounded repairability problem becomes EXPTIME-complete if the target language is specified by an arbitrary bottom-up tree automaton and becomes tractable (PTIME-complete, in fact) when a deterministic bottom-up automaton is used.Lire moins >
Langue :
Anglais
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-01411116/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-01411116/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-01411116/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- TODS%202016.pdf
- Accès libre
- Accéder au document