Bounded repairability for regular tree languages

Gabriele Puppis, Cristian Riveros, Slawek Staworko

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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, which was previously studied in [6].
Original languageEnglish
Title of host publication15th International Conference on Database Theory, ICDT '12, Berlin, Germany, March 26-29, 2012
PublisherACM
Pages155-168
Number of pages14
DOIs
Publication statusPublished - 2012

Fingerprint Dive into the research topics of 'Bounded repairability for regular tree languages'. Together they form a unique fingerprint.

Cite this