| 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.
|
|
アブストラクト