Edit Distance between Unlabeled Ordered Trees

Details Edit Distance between Unlabeled Ordered Trees Edit Distance between Unlabeled Ordered Trees

2005-06-27

arxiv.org/abs/math/0506538v1

Mathematics

Combinatorics

Algorithmique et Combinatoire

Scientific paper

There exists a bijection between one stack sortable permutations --permutations which avoid the pattern 231-- and planar trees. We define an edit distance between permutations which is coherent with the standard edit distance between trees. This one-to-one correspondence yields a polynomial algorithm for the subpermutation problem for $(231)$ avoiding permutations. Moreover, we obtain the generating function of the edit distance between ordered trees and some special ones. For the general case we show that the mean edit distance between a planar tree and all other planar 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.

Affiliated with

Also associated with

No associations

Rating

Edit Distance between Unlabeled Ordered Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Edit Distance between Unlabeled Ordered Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Edit Distance between Unlabeled Ordered Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-646417