A relation between edit distance for ordered trees and edit distance for Euler strings

摘要

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.