Deciding Conjugacy in Thompson's Group F in Linear Time

Proceedings of the 15th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2013), (2013), 89 - 96
http://dx.doi.org/10.1109/SYNASC.2013.19

We present an efficient implementation of the solution
to the conjugacy problem in Thompson’s group F, a
certain infinite group whose elements are piecewise-linear homeomorphisms of the unit interval [0; 1]. This algorithm checks for conjugacy by constructing and comparing directed graphs called strand diagrams. We provide a comprehensive description of our solution algorithm, including the data structure that stores strand diagrams and methods to simplify them. We prove that our algorithm theoretically achieves an O(n) bound in the size of the input, and we present a O(n2) working solution.