| Presentation | 2004-09-17 Mapping Conditions for Alignment of Trees Tetsuji KUBOYAMA, Akira YASUHARA, Tetsuhiro MIYAHRA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(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) |
| Keyword(in English) | tree edit distance / alignment of trees / tree minor containment |
| Paper # | COMP2004-29 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2004/9/10(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| 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) | tree edit distance |
| Keyword(2) | alignment of trees |
| Keyword(3) | tree minor containment |
| 1st Author's Name | Tetsuji KUBOYAMA |
| 1st Author's Affiliation | Center for Collaborative Research, The University of Tokyo() |
| 2nd Author's Name | Akira YASUHARA |
| 2nd Author's Affiliation | Department of Mathematics, Tokyo Gakugei University |
| 3rd Author's Name | Tetsuhiro MIYAHRA |
| 3rd Author's Affiliation | Faculty of Information Sciences, Hiroshima City University |
| Date | 2004-09-17 |
| Paper # | COMP2004-29 |
| Volume (vol) | vol.104 |
| Number (no) | 317 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |