Measuring closeness between Cayley automatic groups and automatic groups

DOI10.1007/978-3-319-77313-1_19MaRDI QIDQ1647707zbMATH OpenOpenAlexFDO

Authors D. A. Berdinskij, Phongpitak Trakuldit

Publication date 26 June 2018

Full work available at URL https://arxiv.org/abs/1804.02548

zbMATH Keywords

Heisenberg groupautomatic structureslamplighter groupBaumslag-Solitar groupsautomatic groupsCayley automatic groupsnumerical characteristics of groups

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Abstract: In this paper we introduce a way to estimate a level of closeness of Cayley automatic groups to the class of automatic groups using a certain numerical characteristic. We characterize Cayley automatic groups which are not automatic in terms of this numerical characteristic and then study it for the lamplighter group, the Baumslag--Solitar groups and the Heisenberg group.

Recommendations

• Towards quantitative classification of Cayley automatic groups
• From automatic structures to automatic groups.
• Finitely generated semiautomatic groups
• Cayley automatic groups and numerical characteristics of Turing transducers
• Cayley graph automatic groups are not necessarily Cayley graph biautomatic

Cited in

(5)

• On the geometry of Cayley automatic groups
• Towards quantitative classification of Cayley automatic groups
• String compression in FA-presentable structures
• Extending the synchronous fellow traveler property
• Cayley polynomial-time computable groups

This page was built for publication: Measuring closeness between Cayley automatic groups and automatic groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1647707)