Paper Info
Title
Property Testing of Regular Tree Languages
Abstract
We consider the edit distance with moves on the class of wordsand the class of ordered trees. We first exhibit a simple testerfor the class of regular languages on words and generalize it tothe class of ranked and unranked regular trees. We also show thatthis distance problem is NP-complete on orderedtrees.
Year
DOI
Venue
2007
10.1007/s00453-007-9028-3
ICALP
Keywords
Field
DocType
Property testing,Edit distance with moves,Regular trees languages
Edit distance,String searching algorithm,Discrete mathematics,Combinatorics,NP-complete,Property testing,Regular tree grammar,Ranking,Regular language,Tree automaton,Mathematics
Journal
Volume
Issue
ISSN
49
2
0178-4617
Citations 
PageRank 
References 
10
0.64
13
Authors
2
Name
Order
Citations
PageRank
Frédéric Magniez157044.33
Michel De Rougemont2138143.69