HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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 metadata

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-00966380
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Wednesday, March 26, 2014 - 3:16:24 PM
Last modification on : Tuesday, March 30, 2021 - 3:18:46 AM
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

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. ⟨10.46298/dmtcs.618⟩. ⟨hal-00966380⟩

Share

Metrics

Record views

352

Files downloads

789