Surjective cellular automata far from the Garden of Eden

Abstract : One of the first and most famous results of cellular automata theory, Moore's Garden-of-Eden theorem has been proven to hold if and only if the underlying group possesses the measure-theoretic properties suggested by von Neumann to be the obstacle to the Banach-Tarski paradox. We show that several other results from the literature, already known to characterize surjective cellular automata in dimension d, hold precisely when the Garden-of-Eden theorem does. We focus in particular on the balancedness theorem, which has been proven by Bartholdi to fail on amenable groups, and we measure the amount of such failure.
Document type :
Journal articles
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-00966380
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Wednesday, March 26, 2014 - 3:16:24 PM
Last modification on : Friday, May 10, 2019 - 1:44:06 PM
Long-term archiving on : Thursday, June 26, 2014 - 11:31:55 AM

File

2336-8374-1-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00966380, version 1

Collections

Citation

Silvio Capobianco, Pierre Guillon, Jarkko Kari. Surjective cellular automata far from the Garden of Eden. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 3 (3), pp.41--60. ⟨hal-00966380⟩

Share

Metrics

Record views

750

Files downloads

685