CAYLEY LINEAR–TIME COMPUTABLE GROUPS

Abstract

This paper looks at the class of groups admitting normal forms for which the right multiplication by a group element is computed in linear time on a multi–tape Turing machine. We show that the groups Z2 ≀ Z2, Z2 ≀ F2 and Thompson’s group F have normal forms for which the right multiplication by a group element is computed in linear time on a 2–tape Turing machine. This refines the results previously established by Elder and the authors that these groups are Cayley polynomial–time computable.