Lamplighter groups and automata

Jain S., Moldagaliyev B., Stephan F., Tien Dat Tran T. D. T.

ACTA INFORMATICA, vol.59, no.4, pp.451-478, 2022 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 59 Issue: 4
  • Publication Date: 2022
  • Doi Number: 10.1007/s00236-022-00423-3
  • Journal Name: ACTA INFORMATICA
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, PASCAL, ABI/INFORM, Applied Science & Technology Source, Compendex, Computer & Applied Sciences, INSPEC
  • Page Numbers: pp.451-478
  • Süleyman Demirel University Affiliated: No

Abstract

This paper investigates presentations of lamplighter groups using computationalmodels from automata theory. The present work shows that if G can be presented such that the full group operation is recognised by a transducer, then the same is true for the lamplighter group G (sic) Z of G. Furthermore, Cayley presentations, where only multiplications with constants are recognised by transducers, are used to study generalised lamplighter groups of the form G (sic) Zd and G (sic) Fd, where Fd is the free group over d generators. Additionally, Zk (sic) Z2 and Zk (sic) Fd are shown to be Cayley tree automatic.