@article{deRougemont201613,
title = "Approximate consistency for transformations on words and trees ",
journal = "Theoretical Computer Science ",
volume = "626",
number = "",
pages = "13 - 39",
year = "2016",
note = "",
issn = "0304-3975",
doi = "http://dx.doi.org/10.1016/j.tcs.2016.01.032",
url = "http://www.sciencedirect.com/science/article/pii/S0304397516000566",
author = "Michel de Rougemont and Adrien Vieilleribière",
keywords = "Database theory",
keywords = "Approximation",
keywords = "Complexity ",
abstract = "Abstract We introduce approximate Source-consistency, for transformations of words and trees, the relaxed version of the Source-consistency problem. A setting consists in an input schema, an output schema and a relation T between input and output structures. Given an input structure I, we want to decide if there is an output structure J in the output schema such that ( I , J ) ∈ T . We consider transducers of words and trees and prove the testability of this property for some edit distance on words and trees. We exhibit randomized algorithms which distinguish between a consistent and an ε-far from consistent I, by looking at a constant fraction of the large input I. The main result on trees is based on a statistical representation of ordered unranked trees, which may be used in other contexts. "
}