Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
429252 | Information Processing Letters | 2006 | 5 Pages |
Abstract
We consider a relationship between the unit cost edit distance for two rooted ordered trees and the unit cost edit distance for the corresponding Euler strings. We show that the edit distance between trees is at least half of the edit distance between the Euler strings and is at most 2h+1 times the edit distance between the Euler strings, where h is the minimum height of two trees. The result can be extended for more general cost functions.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics