Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0920.43001
Ceccherini-Silberstein, Tullio G.; Machì, Antonio; Scarabotti, Fabio
Amenable groups and cellular automata. (English)
[J] Ann. Inst. Fourier 49, No.2, 673-685 (1999). ISSN 0373-0956; ISSN 1777-5310/e

The authors study the connection between cellular automata and amenable groups. Using the notions of Garden of Eden (GOE) and mutually erasable (ME) configurations [see {\it A. Machì} and {\it F. Mignosi}, SIAM J. Discr. Math. 6, 44-56 (1993; Zbl 0768.68103)], the following main result is proved: For any cellular automaton $(S,{\cal G}_A (G),f)$, where $S$ is the alphabet (set of states), ${\cal G}_A(G)$ the Cayley graph of a finitely generated amenable group $G$ with respect to a finite and symmetric generated system $A$ and $f$ the local map, there exist GOE patterns if and only if there exist ME patterns. This extends the theorems of E. F. Moore and J. Myhill to universes which are the Cayley graphs of amenable groups. Some counterexamples of universes are given that show the limits of applicability of the mentioned result.
[I.Strazdins (Riga)]

MSC 2000:: *43A07 Means on groups, etc.
68Q80 Cellular and array automata
05C25 Graphs and groups
20F65 Geometric group theory

Keywords: amenable groups; Cayley graph; cellular automaton; garden of Eden

Citations: Zbl 0768.68103

Cited in: Zbl 1168.43300

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

	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]