Bounding right-arm rotation distances

Details Bounding right-arm rotation distances Bounding right-arm rotation distances

2005-06-20

arxiv.org/abs/math/0506413v2

Mathematics

Group Theory

30 pages, 11 figures. This revised version corrects some typos and has some clearer proofs of the results for the lower bounds

Scientific paper

Rotation distance measures the difference in shape between binary trees of the same size by counting the minimum number of rotations needed to transform one tree to the other. We describe several types of rotation distance where restrictions are put on the locations where rotations are permitted, and provide upper bounds on distances between trees with a fixed number of nodes with respect to several families of these restrictions. These bounds are sharp in a certain asymptotic sense and are obtained by relating each restricted rotation distance to the word length of elements of Thompson's group F with respect to different generating sets, including both finite and infinite generating sets.

Affiliated with

Also associated with

No associations

Rating

Bounding right-arm rotation distances 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 Bounding right-arm rotation distances, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounding right-arm rotation distances will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-293353