The Myhill property for strongly irreducible subshifts over amenable groups (Q662409)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The Myhill property for strongly irreducible subshifts over amenable groups |
scientific article |
Statements
The Myhill property for strongly irreducible subshifts over amenable groups (English)
0 references
22 February 2012
0 references
This article generalizes the Myhill theorem to cellular automata over strongly irreducible subshifts in (possibly uncountable) amenable groups: if \(G\) is an amenable group, \(A\) a finite alphabet, \(X\subset A^G\) an irreducible subshift, and \(\tau:X\to X\) a CA (continuous shift-commuting) that is pre-injective (two preimages of the same configuration have finite differences), then it is surjective. This fact was well-known for classical CA over \(X=A^{\mathbb Z}\) since [\textit{J. Myhill}, Proc. Am. Math. Soc. 14, 685--686 (1963; Zbl 0126.32501)], for finitely generated amenable groups since [\textit{T. G. Ceccherini-Silberstein} et al., Ann. Inst. Fourier 49, No. 2, 673--685 (1999; Zbl 0920.43001)] and for strongly irreducible SFT in those since [\textit{F. Fiorenzi}, Theor. Comput. Sci. 299, No. 1--3, 477--493 (2003; Zbl 1042.68077)]. These references also prove the converse, known as the Moore theorem (together they are known as the Garden of Eden theorem), but [\textit{F. Fiorenzi}, PU.M.A., Pure Math. Appl. 11, No. 3, 471--484 (2000; Zbl 0980.37004)] gives a counter-example over a strongly irreducible sofic subshift in \(\mathbb Z\). The proof is based on the fact that amenable groups are those that can be endowed with a somehow canonical notion of entropy, strongly irreducible subshifts are those that do not contain an equal-entropy strict subsystem, and pre-injective CA preserve entropy (hence their image is an equal-entropy subsystem).
0 references
shift
0 references
subshift
0 references
cellular automaton
0 references
Myhill property
0 references
strongly irreducible subshift
0 references
topologically mixing subshift
0 references
amenable group
0 references
entropy
0 references
Garden of Eden
0 references