期刊
THEORY OF COMPUTING SYSTEMS
卷 60, 期 4, 页码 759-783出版社
SPRINGER
DOI: 10.1007/s00224-016-9705-1
关键词
Tai mapping; Tai mapping hierarchy; Common subforest; Tree edit distance
资金
- Ministry of Education, Culture, Sports, Science and Technology, Japan [16H02870, 16H01743, 15K12102, 26280085, 24300060]
- Grants-in-Aid for Scientific Research [15K12102, 16H01743, 26280085, 16H02870] Funding Source: KAKEN
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据