Capobianco, Silvio and Guillon, Pierre and Kari, Jarkko - 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: Capobianco, Silvio and Guillon, Pierre and Kari, Jarkko

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.


Source : oai:HAL:hal-00966380v1
Volume: Vol. 15 no. 3
Section: Automata, Logic and Semantics
Published on: October 18, 2013
Submitted on: December 7, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 80 times.
This article's PDF has been downloaded 89 times.