Displaying similar documents to “Completion of the Wilf-classification of 3-5 pairs using generating trees.”

Edit distance between unlabeled ordered trees

Anne Micheli, Dominique Rossin (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

There exists a bijection between one-stack sortable permutations (permutations which avoid the pattern ) 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 pattern-avoiding permutations. Moreover, we obtain the generating function of the edit distance between ordered unlabeled trees and some special ones. For...