RAIRO-Theor. Inf. Appl.
Volume 40, Number 4, October-December 2006
|Page(s)||593 - 609|
|Published online||08 November 2006|
Edit distance between unlabeled ordered trees
CNRS, LIAFA, Université Paris 7, 2 Place
Jussieu, 75251 Paris Cedex 05, France; firstname.lastname@example.org; email@example.com
Accepted: 15 February 2006
There exists a bijection between one-stack sortable permutations (permutations which avoid the pattern (231)) and rooted plane trees. We define an edit distance between permutations which is consistent with the standard edit distance between trees. This one-to-one correspondence yields a polynomial algorithm for the subpermutation problem for (231) pattern-avoiding permutations. Moreover, we obtain the generating function of the edit distance between ordered unlabeled trees and some special ones. For the general case we show that the mean edit distance between a rooted plane tree and all other rooted plane trees is at least n/ln(n). Some results can be extended to labeled trees considering colored Dyck paths or, equivalently, colored one-stack sortable permutations.
Mathematics Subject Classification: 05C12 / 05C05 / 05A05 / 05A15
Key words: Edit distance / trees.
© EDP Sciences, 2006
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.