Bounded Repairability for Regular Tree Languages
Document type :
Compte-rendu et recension critique d'ouvrage
DOI :
Title :
Bounded Repairability for Regular Tree Languages
Author(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]
Journal title :
ACM Transactions on Database Systems
Pages :
1-45
Publisher :
Association for Computing Machinery
Publication date :
2016-06
ISSN :
0362-5915
HAL domain(s) :
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]
English abstract : [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 ...
Show more >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.Show less >
Show more >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.Show less >
Language :
Anglais
Popular science :
Non
Collections :
Source :
Files
- https://hal.archives-ouvertes.fr/hal-01411116/document
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-01411116/document
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-01411116/document
- Open access
- Access the document
- document
- Open access
- Access the document
- TODS%202016.pdf
- Open access
- Access the document