New algorithm for ordered tree-to-tree correction problem

The ordered tree-to-tree correction problem is to compute the minimum edit cost of transforming one ordered tree to another one. This paper presents a new algorithm for this problem. Given two ordered trees S and T, our algorithm runs in O(\S \ \T \ + min (L-S(2)\T \ + L-S(2.5) L-T, L-T(2)\S \ +(LTLS)-L-2.5) time, where L-S denotes the number of leaves of S and D-S denotes the depth of S. The previous best algorithms for this problem run in O(\S \ \T \ min (L-S, D-S} min {L-T, D-T}) time (K. Zhang and D. Shasha, SIAM J. Comput. 18, No. 6 (1989), 1245-1262) and in O(min (\S \ (2) \T \ log(2) \T \, \T \ (2)\S \ log(2) \S \}) time (P. N. Klein, in "Algorithms-ESA'98, 6th Annual European Symposium" (G. Bilardi, G. F. ltaliano, A. Pietracaprina, and G. Pucci, Eds.), Lecture Notes in Computer Science, Vol. 1461, pp. 91-102, Springer-Verlag, Berlin/New York, 1998). As a comparison, our algorithm is asymptotically faster for certain kind of trees. (C) 2001 Academic Press.