Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1218.37004
Ceccherini-Silberstein, Tullio; Coornaert, Michel
Cellular automata and groups. (English)
[B] Springer Monographs in Mathematics. Berlin: Springer. xix, 439~p. EUR~89.95/net; \sterling~81.00; SFR~140.00 (2010). ISBN 978-3-642-14033-4/hbk; ISBN 978-3-642-14034-1/ebook

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.
[Boris S. Kruglikov (Troms\o)]

MSC 2000:: *37-02 Research exposition (Dynamical systems and ergodic theory)
37B15 Cellular automata
68Q80 Cellular and array automata
20F65 Geometric group theory
20M35 Semigroups in automata theory, linguistics, etc.
68Q70 Algebraic theory of automata
20-02 Research monographs (group theory)
68-02 Research monographs (computer science)

Keywords: cellular automata; amenable groups; Garden of Eden theorem; surjunctivity; symbolic dynamics; word growth; entropy; sofic groups; linear cellular automata

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]