Bounded repairability for regular tree languages

Abstract : We consider the problem of repairing unranked trees (e.g., XML documents) satisfying a given restriction specification R (e.g., a DTD) into unranked trees satisfying a given target specification T. Specifically, we focus on the question of whether one can get from any tree in a regular language R to some tree in another regular language T with a finite, uniformly bounded, number of edit operations (i.e., deletions and insertions of nodes). We give effective characterizations of the pairs of specifications R and T for which such a uniform bound exists, and we study the complexity of the problem under different representations of the regular tree languages (e.g., non-deterministic stepwise automata, deterministic stepwise automata, DTDs). Finally, we point out some connections with the analogous problem for regular languages of words.
Type de document :
Communication dans un congrès
15th International Conference on Database Theory, ICDT, Mar 2012, Berlin, Germany. ACM, pp.155-168, 2012, 〈10.1145/2274576.2274593〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00643100
Contributeur : Slawomir Staworko <>
Soumis le : jeudi 5 avril 2012 - 22:47:04
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : lundi 26 novembre 2012 - 12:51:32

Fichier

staworko-icdt12b.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Gabriele Puppis, Cristian Riveros, Slawomir Staworko. Bounded repairability for regular tree languages. 15th International Conference on Database Theory, ICDT, Mar 2012, Berlin, Germany. ACM, pp.155-168, 2012, 〈10.1145/2274576.2274593〉. 〈hal-00643100〉

Partager

Métriques

Consultations de la notice

524

Téléchargements de fichiers

115