Silvio Capobianco ; Pierre Guillon ; Jarkko Kari - Surjective cellular automata far from the Garden of Eden

dmtcs:618 - Discrete Mathematics & Theoretical Computer Science, October 18, 2013, Vol. 15 no. 3 -
Surjective cellular automata far from the Garden of Eden

Authors: Silvio Capobianco ORCID-iD1; Pierre Guillon ORCID-iD2,3; Jarkko Kari ORCID-iD2

  • 1 Institute of Cybernetics [Tallinn]
  • 2 Department of Mathematics
  • 3 Institut de mathématiques de Luminy

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.

Volume: Vol. 15 no. 3
Section: Automata, Logic and Semantics
Published on: October 18, 2013
Accepted on: June 9, 2015
Submitted on: December 7, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
    Source : OpenAIRE Graph
  • Cellular automata and discrete dynamical systems; Funder: Academy of Finland; Code: 131558

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1016/s0019-9958(76)90195-9
  • 10.1016/s0019-9958(76)90195-9
Condition for Injectivity of global maps for tessellation automata

1 Document citing this article

Consultation statistics

This page has been seen 341 times.
This article's PDF has been downloaded 383 times.