Top-down tree edit-distance of regular tree languages

Sang Ki Ko, Yo Sub Han, Kai Salomaa

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


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.

Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications - 8th International Conference, LATA 2014, Proceedings
Number of pages12
StatePublished - 2014
Event8th International Conference on Language and Automata Theory and Applications, LATA 2014 - Madrid, Spain
Duration: 10 Mar 201414 Mar 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8370 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference8th International Conference on Language and Automata Theory and Applications, LATA 2014


  • dynamic programming
  • regular tree languages
  • tree automata
  • tree edit-distance


Dive into the research topics of 'Top-down tree edit-distance of regular tree languages'. Together they form a unique fingerprint.

Cite this