کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435367 | 689899 | 2016 | 27 صفحه PDF | دانلود رایگان |
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.
Journal: Theoretical Computer Science - Volume 626, 2 May 2016, Pages 13–39