Paper Info
Title
A converse to Moore's theorem on cellular automata
Abstract
We prove a converse to Moore's "Garden-of-Eden" theorem: a group G is amenable if and only if all cellular automata living on G that admit mutually erasable patterns also admit gardens of Eden. It had already been conjectured in (11; 1, Conjecture 6.2) that amenability could be characterized by cellular automata. We prove the first part of that conjecture.
Year
DOI
Venue
2007
10.471/JEMS/196
Clinical Orthopaedics and Related Research
Keywords
Field
DocType
dynamic system,group theory,information theory,cellular automata
Converse,Discrete mathematics,Cellular automaton,Automata theory,Combinatorics,If and only if,Conjecture,Mathematics
Journal
Volume
ISSN
Citations 
abs/0709.4
J. Eur. Math. Soc. 12 (2010), 241-248
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Laurent Bartholdi1278.74