A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
No Tits alternative for cellular automata
Tekijät: Ville Salo
Kustantaja: European Mathematical Society Publishing House
Kustannuspaikka: Zürich
Julkaisuvuosi: 2019
Journal: Groups, Geometry, and Dynamics
Lehden akronyymi: GGD
Artikkelin numero: 13
Vuosikerta: 13
Numero: 4
Aloitussivu: 1437
Lopetussivu: 1455
Sivujen määrä: 19
ISSN: 1661-7207
eISSN: 1661-7215
DOI: https://doi.org/10.4171/GGD/529
Verkko-osoite: https://www.ems-ph.org/journals/show_pdf.php?issn=1661-7207&vol=13&iss=4&rank=13
Rinnakkaistallenteen osoite: https://arxiv.org/abs/1709.00858
We show that the automorphism group of a one-dimensional full shift (the
group of reversible cellular automata) does not satisfy the Tits alternative.
That is, we construct a finitely-generated subgroup which is not virtually
solvable yet does not contain a free group on two generators. We give
constructions both in the two-sided case (spatially acting group Z) and the
one-sided case (spatially acting monoid N, alphabet size at least eight).
Lack of Tits alternative follows for several groups of symbolic (dynamical)
origin: automorphism groups of two-sided one-dimensional uncountable sofic
shifts, automorphism groups of multidimensional subshifts of finite type with
positive entropy and dense minimal points, automorphism groups of full shifts
over non-periodic groups, and the mapping class groups of two-sided
one-dimensional transitive SFTs. We also show that the classical Tits
alternative applies to one-dimensional (multi-track) reversible linear cellular
automata over a finite field.
Ladattava julkaisu This is an electronic reprint of the original article. |