×

zbMATH — the first resource for mathematics

Cellular automata and groups. (English) Zbl 1218.37004
Springer Monographs in Mathematics. Berlin: Springer (ISBN 978-3-642-14033-4/hbk; 978-3-642-14034-1/ebook). xix, 439 p. (2010).
Cellular automata were introduced by John von Neumann as theoretical models for self reproducing machines. He also introduced the class of groups called amenable, which include all solvable and all finitely generated groups of sub-exponential growth. A relation between these distinct notions is given by the Garden of Eden theorem proved in 1997 by A. Machi, F. Scarabotti and T. Ceccherini-Silberstein. For cellular automata with finite alphabets over amenable groups, surjectivity (transitivity on configurations from dynamical viewpoint) is equivalent to pre-injectivity (two configurations equal in a complement to a finite subset of the group and with equal images must be the same). Simultaneously and independently, M. Gromov proved a more general version for amenable graphs with a dense holonomy and cellular automata based on maps of bounded variations. Later, the Garden of Eden theorem was shown to be wrong for non-amenable groups.
The book discusses these and related topics from the theory of cellular automata on groups and explores its deep connections with recent developments in geometric group theory, symbolic dynamics and theoretical computer science. It contains concise introduction to cellular automata from both theoretic computer and symbolic dynamic viewpoint. Various classes of groups are studied in details: residually finite, surjunctive, amenable and later sofic groups. The central results discussed and proved in the book are: the Gromov theorem that a limit of surjunctive marked groups is surjunctive, Følner and Tarski theorems on characterizations of amenable groups, the Garden of Eden theorem for amenable groups demonstrated by establishing that both surjectivity and pre-injectivity are equivalent to maximal entropy for the image of the configuration space, a theorem that every finitely generated group of sub-exponential growth is amenable, the Kesten-Day theorem that amenability is equivalent to the fact that the \(\ell^2\)-spectrum of the Laplacian contains 0, the Gromov-Weiss theorem that every sofic group is surjunctive, and its analog for linear cellular automata that every sofic group is \(L\)-surjunctive, the linear version of the Garden of Eden theorem, and the resolution of the Kaplansky conjecture on the stable finiteness of group rings for sofic groups.
The book has 8 chapters, 10 appendices and more than 300 exercises. It is oriented towards a broad audience, and shall be useful for experts as a detailed comprehensive account of the recent progress in the field.

MSC:
37-02 Research exposition (monographs, survey articles) pertaining to dynamical systems and ergodic theory
37B15 Dynamical aspects of cellular automata
68Q80 Cellular automata (computational aspects)
20F65 Geometric group theory
20M35 Semigroups in automata theory, linguistics, etc.
68Q70 Algebraic theory of languages and automata
20-02 Research exposition (monographs, survey articles) pertaining to group theory
68-02 Research exposition (monographs, survey articles) pertaining to computer science
PDF BibTeX XML Cite
Full Text: DOI