No Access

BOUNDING RIGHT-ARM ROTATION DISTANCES

SEAN CLEARY

Department of Mathematics, The City College of New York & The CUNY Graduate Center, New York, NY 10031, USA

Search for more papers by this author

and

JENNIFER TABACK

Department of Mathematics, Bowdoin College, Brunswick, ME 04011, USA

Search for more papers by this author

https://doi.org/10.1142/S0218196707003664Cited by:3 (Source: Crossref)

Abstract

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.

Keywords:

AMSC: 20F65, 68R99

References

K. S. Brown, Algorithms and Classification in Combinatorial Group Theory (Springer, New York, 1992) pp. 137–163. Crossref, Google Scholar
K. S. Brown and R. Geoghegan, Invent. Math. 77, 367 (1984). Crossref, Web of Science, Google Scholar
J. W. Cannon, W. J. Floyd and W. R. Parry, Enseign. Math. 42(3–4), 215 (1996). Web of Science, Google Scholar
S. Cleary, Inform. Process. Lett. 84(3), 333 (2002). Crossref, Web of Science, Google Scholar
S. Cleary and J. Taback, Inform. Process. Lett. 88(5), 251 (2003). Crossref, Web of Science, Google Scholar
S. Cleary and J. Taback, J. Algebra 270(1), 133 (2003). Crossref, Web of Science, Google Scholar
S. Cleary and J. Taback, Trans. Amer. Math. Soc. 356(7), 2825 (2004). Crossref, Web of Science, Google Scholar
K. Culik II and D. Wood, Inform. Process. Lett. 15(1), 39 (1982). Crossref, Web of Science, Google Scholar
S. B. Fordham, Geom. Dedicata 99, 179 (2003). Crossref, Web of Science, Google Scholar
D. E. Knuth , The Art of Computer Programming 3 ( Addison-Wesley , Reading, MA , 1973 ) . Google Scholar
J. Pallo, Inform. Process. Lett. 73(3–4), 87 (2000). Crossref, Web of Science, Google Scholar
J. M. Pallo, Inform. Process. Lett. 87(4), 173 (2003). Crossref, Web of Science, Google Scholar
R. Rogers, On finding shortest paths in the rotation graph of binary trees, Proc. Southeastern Int. Conf. Combinatorics, Graph Theory, and Computing137 (1999) pp. 77–95. Google Scholar
D. D. Sleator, R. E. Tarjan and W. P. Thurston, J. Amer. Math. Soc. 1(3), 647 (1988). Crossref, Google Scholar