Lamplighter groups and automata

Jain, Sanjay; Moldagaliyev, Birzhan; Stephan, Frank; Tien Dat Tran, Tien

doi:10.1007/s00236-022-00423-3

Lamplighter groups and automata

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

ACTA INFORMATICA, cilt.59, sa.4, ss.451-478, 2022 (SCI-Expanded, Scopus)

Yayın Türü: Makale / Tam Makale
Cilt numarası: 59 Sayı: 4
Basım Tarihi: 2022
Doi Numarası: 10.1007/s00236-022-00423-3
Dergi Adı: ACTA INFORMATICA
Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, PASCAL, ABI/INFORM, Applied Science & Technology Source, Compendex, Computer & Applied Sciences, INSPEC
Sayfa Sayıları: ss.451-478
Süleyman Demirel Üniversitesi Adresli: Hayır

Özet

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.