zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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. EUR 89.95/net; £ 81.00; SFR 140.00 (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 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-02Research exposition (Dynamical systems and ergodic theory)
37B15Cellular automata
68Q80Cellular automata (theory of computing)
20F65Geometric group theory
20M35Semigroups in automata theory, linguistics, etc.
68Q70Algebraic theory of languages and automata
20-02Research monographs (group theory)
68-02Research monographs (computer science)