Bounded repairability for regular tree languages
Cristian Riveros
Info
|
Date |
14th February 2012 (week , Hilary Term 2012) |
|
Time |
11:30 |
|
Place |
147 |
Abstract
In this talk, I will present our recent results about repairing XML documents satisfying a given restriction schema into XML documents satisfying a given target schema. Specifically, I will focus on the more general 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). I will present an effective characterization of the pairs of specifications R and T for which such a uniform bound exists and show the complexity of the problem under different representations of the regular tree languages (e.g., DTDs, tree automata). Finally, I will point out some connections with the analogous problem for regular languages of words, which was previously studied.
Further info
|
Related series |
|
