An Efficient Bottom-Up Distance between Trees

A new bottom-updistancemeasur e for labeled trees, which is basedon the largest commonforest of the trees andhasthethreefoldadvantageof independenceof particular editcosts,low complexity, andcoverageof orderedand unorderedtrees,is introducedandrelatedin thispaperwith other distancemeasur espublishedin the literature. Algorithmsfor computingthebottom-updistancein timelinear in thenumberof nodesare givenin full detail.