TY - GEN
T1 - Top-down tree edit-distance of regular tree languages
AU - Ko, Sang Ki
AU - Han, Yo Sub
AU - Salomaa, Kai
PY - 2014
Y1 - 2014
N2 - We study the edit-distance of regular tree languages. The edit-distance is a metric for measuring the similarity or dissimilarity between two objects, and a regular tree language is a set of trees accepted by a finite-state tree automaton or described by a regular tree grammar. Given two regular tree languages L and R, we define the edit-distance d(L,R) between L and R to be the minimum edit-distance between a tree t1 ∈ L and t2 ∈ R, respectively. Based on tree automata for L and R, we present a polynomial algorithm that computes d(L,R). We also suggest how to use the edit-distance between two tree languages for identifying a special common string between two context-free grammars.
AB - We study the edit-distance of regular tree languages. The edit-distance is a metric for measuring the similarity or dissimilarity between two objects, and a regular tree language is a set of trees accepted by a finite-state tree automaton or described by a regular tree grammar. Given two regular tree languages L and R, we define the edit-distance d(L,R) between L and R to be the minimum edit-distance between a tree t1 ∈ L and t2 ∈ R, respectively. Based on tree automata for L and R, we present a polynomial algorithm that computes d(L,R). We also suggest how to use the edit-distance between two tree languages for identifying a special common string between two context-free grammars.
KW - dynamic programming
KW - regular tree languages
KW - tree automata
KW - tree edit-distance
UR - https://www.scopus.com/pages/publications/84898067722
U2 - 10.1007/978-3-319-04921-2_38
DO - 10.1007/978-3-319-04921-2_38
M3 - Conference contribution
AN - SCOPUS:84898067722
SN - 9783319049205
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 466
EP - 477
BT - Language and Automata Theory and Applications - 8th International Conference, LATA 2014, Proceedings
T2 - 8th International Conference on Language and Automata Theory and Applications, LATA 2014
Y2 - 10 March 2014 through 14 March 2014
ER -