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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 3 (3), pp.41--60
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00966380
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 26 mars 2014 - 15:16:24
Dernière modification le : jeudi 18 janvier 2018 - 01:58:29
Document(s) archivé(s) le : jeudi 26 juin 2014 - 11:31:55

Fichier

2336-8374-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

620

Téléchargements de fichiers

213