Kruengthomya P.Berdinsky D.Mahidol University2024-04-272024-04-272024-01-01Groups, Complexity, Cryptology Vol.15 No.2 (2024) , 1:1-1:22https://repository.li.mahidol.ac.th/handle/20.500.14594/98127This 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.MathematicsComputer ScienceArticleSCOPUS10.46298/jgcc.2024.15.2.125032-s2.0-8519076990318696104