Skip to Main content Skip to Navigation
New interface
Conference papers

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 metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Slawomir Staworko Connect in order to contact the contributor
Submitted on : Thursday, April 5, 2012 - 10:47:04 PM
Last modification on : Friday, February 4, 2022 - 3:18:24 AM
Long-term archiving on: : Monday, November 26, 2012 - 12:51:32 PM


Files produced by the author(s)




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⟩



Record views


Files downloads