Property and Equivalence Testing on Strings
Eldar Fischer, Frédéric Magniez, Michel de Rougemont · 2004
Using a new statistical embedding of words which has similarities with the Parikh mapping, we first construct atolerant tester for the equality of two words, whose complexity is independent of the string size, where the distance between inputs is measured by the normalized edit distance with moves. As a consequence we get an approximationalgorithm for the normalized distance, the first such algorithm whose complexity does not depend on the string size. Then we extend our embedding to languages, and get a geometrical approximate description of regular languagesby finite unions of polytopes. As an application, we have a new tester for regular languages whose complexity does not depend on the automaton. The automaton is only required in a preprocessing step, whose time is polynomial inthe automaton size for a fixed threshold distance. The remaining complexity is a constant depending on the threshhold distance but not on the automaton.Last, we introduce the notion of equivalence testing. Using the above geometrical description, we exhibit an equivalence tester for regular languages. The tester is deterministic and of polynomial time, for a fixed thresholddistance. In contrast, the problem of deciding the exact equivalence of finite automata requires exponential space.