Property testing of regular tree languages
We consider the edit distance with moves on the class of words and the class of ordered trees. We first exhibit a simple tester for the class of regular languages on words and generalize it to the class of ranked and unranked regular trees. We also show that this distance problem is NP-complete on ordered trees.
property testing regular trees languages edit distance with moves