Approximate consistency for transformations on words and trees

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 TT 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(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.