Algorithms for the constrained editing distance between ordered labeled trees and related problems

摘要

This paper considers the problem of computing a constrained editing distance between ordered labeled trees. This distance metric can be applied to pattern recognition, syntactic tree comparison, classification tree comparison and other applications. The problem of approximate ordered tree matching is also considered. We present optimal algorithms for solving these problems in sequential time O(|T1| × |T2|