Paper Abstract and Keywords |
Presentation |
2004-09-17 13:15
Mapping Conditions for Alignment of Trees Tetsuji Kuboyama (Univ. of Tokyo), Akira Yasuhara (Tokyo Gakugei Univ.), Tetsuhiro Miyahara (Hiroshima City Univ.) |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
A number of edit-based distance measures have been proposed to find a structural similarity between trees. Alignment of trees is one of these measures, which gives a common supertree of two trees under minor containment. It is well-known that finding an alignment is equivalent to computing an edit distance for sequences. This equivalence, however, does not hold for trees. In this paper, we establish the relationship between tree edit distance and alignment of trees by showing that the mapping condition for alignment of trees is identical to the condition for a variant of edit distance, called less-constrained edit distance. Moreover, we show a mapping condition for yielding a unique supertree of two trees. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
alignment of trees / tree edit distance / / / / / / |
Reference Info. |
IEICE Tech. Rep., vol. 104, no. 317, COMP2004-29, pp. 25-32, Sept. 2004. |
Paper # |
COMP2004-29 |
Date of Issue |
2004-09-10 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 |
Download PDF |
|
Conference Information |
Committee |
COMP |
Conference Date |
2004-09-17 - 2004-09-17 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
Hokkaido University |
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
|
Paper Information |
Registration To |
COMP |
Conference Code |
2004-09-COMP |
Language |
English |
Title (in Japanese) |
(See Japanese page) |
Sub Title (in Japanese) |
(See Japanese page) |
Title (in English) |
Mapping Conditions for Alignment of Trees |
Sub Title (in English) |
|
Keyword(1) |
alignment of trees |
Keyword(2) |
tree edit distance |
Keyword(3) |
|
Keyword(4) |
|
Keyword(5) |
|
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
Tetsuji Kuboyama |
1st Author's Affiliation |
The University of Tokyo (Univ. of Tokyo) |
2nd Author's Name |
Akira Yasuhara |
2nd Author's Affiliation |
Tokyo Gakugei University (Tokyo Gakugei Univ.) |
3rd Author's Name |
Tetsuhiro Miyahara |
3rd Author's Affiliation |
Hiroshima City University (Hiroshima City Univ.) |
4th Author's Name |
|
4th Author's Affiliation |
() |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-1 |
Date Time |
2004-09-17 13:15:00 |
Presentation Time |
30 minutes |
Registration for |
COMP |
Paper # |
COMP2004-29 |
Volume (vol) |
vol.104 |
Number (no) |
no.317 |
Page |
pp.25-32 |
#Pages |
8 |
Date of Issue |
2004-09-10 (COMP) |
|