Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
435367 | Theoretical Computer Science | 2016 | 27 Pages |
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.