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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-00643100
Contributor : Slawomir Staworko <>
Submitted on : Thursday, April 5, 2012 - 10:47:04 PM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on : Monday, November 26, 2012 - 12:51:32 PM

File

staworko-icdt12b.pdf
Files produced by the author(s)

Identifiers

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. pp.155-168, ⟨10.1145/2274576.2274593⟩. ⟨hal-00643100⟩

Share

Metrics

Record views

624

Files downloads

249