zbMATH — the first resource for mathematics

New algorithm for ordered tree-to-tree correction problem. (English) Zbl 0980.68142
Summary: 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\{{\mathcal L}^2_S|T|+{\mathcal L}^{2.5}_S{\mathcal L}_T, {\mathcal L}^2_T|S|+{\mathcal L}^{2.5}_T{\mathcal L}_S\})\) time, where \({\mathcal L}_S\) denotes the number of leaves of \(S\) and \({\mathcal D}_S\) denotes the depth of \(S\). The previous best algorithms for this problem run in \[ O(|S||T|\min\{{\mathcal L}_S,{\mathcal D}_S\}\min\{{\mathcal L}_T,{\mathcal D}_T\}) \] time [K. Zhang and D. Shasha, SIAM J. Comput. 18, No. 6, 1245-1262 (1989; Zbl 0092.68047)] and in \(O(\min\{|S|^2|T|\log_2|T|,|T|^2|S|\log_2|S|\}\)) time [P. N. Klein, Lect. Notes Comput. Sci. 1461, 91-102 (1998; Zbl 0932.68066)]. As a comparison, our algorithm is asymptotically faster for certain kind of trees.

68W05 Nonnumerical algorithms
Full Text: DOI