A Certain System of Equations Described byCellular Automata and Gardens of Eden

In this talk we investigate the behavior of non-amenablegroups with the approach of configurations defined by Rosenblattand Willis in ۲۰۰۱. In that paper the authors introduce finite linearsystems of equations that their normalized solutions characterizethe amenability of groups. These systems are used to constructparadoxical decompositions for non-amenable groups andconsequently to achieve upper bounds for their Tarski numbers.On the other hand Bartholdi proved that amenability of groupscan also be characterized by a theorem related to cellularautomata known as Myhill’s theorem. Indeed he proved that adiscrete group is amenable if and only if every cellular automatonwith its carrier that has gardens of Eden also has mutuallyerasable patterns. We in particular intend to explore paradoxicaldecompositions for certain non-amenable groups, usingBartholdi’s theorem. This is the main motivation of the currenttalk.

کلیدواژه ها:

cellular automata ، group ، amenability ، configuration ، Garden of Eden pattern ، mutually erasable patterns