Name
Abstract | ||
|---|---|---|
A Tai mapping between two rooted labeled trees (trees, for short) is a one-to-one node correspondence preserving ancestors and siblings (if trees are ordered). The variations of the Tai mapping are known to provide a hierarchy, called a Tai mapping hierarchy. In this paper, we characterize the Tai mapping hierarchy as a common subforest by focusing on the connections of nodes and the arrangements of subtrees in a common subforest. Then, we fill a gap in the Tai mapping hierarchy by introducing several new variations. Furthermore, we summarize and investigate the time complexity of computing the variations of the edit distance as the minimum cost of the variations of the Tai mapping. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s00224-016-9705-1 | Theory Comput. Syst. |
Keywords | Field | DocType |
Tai mapping,Tai mapping hierarchy,Common subforest,Tree edit distance | Edit distance,Artificial intelligence,Tree edit distance,Hierarchy,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
60 | 4 | 1432-4350 |
Citations | PageRank | References |
3 | 0.44 | 14 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Takuya Yoshino | 1 | 4 | 4.54 |
| Kouichi Hirata | 2 | 130 | 32.04 |