## Abstract

Ordered labeled trees are trees in which the left-to-right order among siblings is significant. The distance between two ordered trees is considered to be the weighted number of edit operations (insert, delete, and modify) to transform one tree to another. The problem of approximate tree matching is also considered. Specifically, algorithms are designed to answer the following kinds of questions: (1) What is the distance between two trees? (2) What is the minimum distance between T_{1} and T_{2} when zero or more subtrees can be removed from T_{2}? (3) Let the pruning of a tree at node n mean removing all the descendants of node n. The analogous question for prunings as for subtrees is answered. A dynamic programming algorithm is presented to solve the three questions.

Original language | English (US) |
---|---|

Pages (from-to) | 1245-1262 |

Number of pages | 18 |

Journal | SIAM Journal on Computing |

Volume | 18 |

Issue number | 6 |

DOIs | |

State | Published - 1989 |

## ASJC Scopus subject areas

- General Computer Science
- General Mathematics