Date 
Apr. 9, 2013 
Speaker 
Dr. Koichi Hirata, Kyushu Institute of Technology

Title 
Tai mapping hierarchy and variations of tree edit distance

Abstract 
The most famous distance measure comparing rooted labeled trees (trees,
for short)
is a tree edit distance between them.
It is known that the tree edit distance is closely related to a Tai mapping,
and the minimum cost of possible Tai mappings coincides with the tree
edit distance.
In this talk, we introduce the several variations of the Tai mapping,
including a segmental mapping which we have introduced at ISAAC 2012.
The variations of the Tai mapping provide a hierarchy
and imply the variations of the tree edit distance.
Then, we present the time complexity for computing
the variations of the tree edit distance
induced from the hierarchy for ordered and unordered trees.
In particular, we present the algorithm for computing the segmental
distance.

