Cayley linear-time computable groups (Q6601468)

The concept of a Cayley automatic group was introduced by \textit{O. Kharlampovich} et al. in [Groups Geom. Dyn. 8, No. 1, 157-198 (2014; Zbl 1322.20025)]. In that approach a normal form is defined by a bijection between a regular language and a group such that the right multiplication by a group element is recognized by a two-tape synchronous automaton. A further extension, introduced in this paper, is that of Cayley linear-time computable, that is groups admitting normal forms for which the right multiplication by a group element is computed in linear time on a multi-tape Turing machine.\N\NIn the paper under review, the authors show that the groups \(\mathbb{Z}_{2}\wr \mathbb{Z}^{2}\), \(\mathbb{Z}_{2} \wr \mathbb{F}_{2}\) and Thompson's group \(F\) are Cayley linear-time computable. This refines some results previously established by \textit{M. Elder} and the authors in [Inf. Comput. 288, Article ID 104768, 15 p. (2022; Zbl 07601279)].