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 - http://www.scopus.com/inward/record.url?scp=84898067722&partnerID=8YFLogxK

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 -