Cayley linear-time computable groups
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)].
- C-graph automatic groups.
- Algorithms and topology of Cayley graphs for groups.
- An infinite-dimensional torsion-free \(\text{FP}_{\infty}\) group
- Automatic functions, linear time and learning
- Cayley automatic representations of wreath products
- Cayley polynomial-time computable groups
- Finitely generated semiautomatic groups
- Formal language theory and the geometry of 3-manifolds
- From automatic structures to automatic groups.
- scientific article; zbMATH DE number 53661 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- Introductory notes on Richard Thompson's groups
- Lamplighter groups and automata
- Parallel poly-pushdown groups
- Thompson's group F is 1-counter graph automatic.
This page was built for publication: Cayley linear-time computable groups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6601468)
