The Library
On the ergodic theory of cellular automata and twodimensional Markov shifts generated by them
Tools
Shereshevsky, Mark Alexandrovich (1992) On the ergodic theory of cellular automata and twodimensional Markov shifts generated by them. PhD thesis, University of Warwick.

PDF
WRAP_THESIS_Shereshevsky_1992.pdf  Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (4Mb) 
Official URL: http://webcat.warwick.ac.uk/record=b1403708~S15
Abstract
In this thesis we study measurable and topological dynamics of certain
classes of cellular automata and multidimensional subshifts.
In Chapter 1 we consider onedimensional cellular automata, i.e. the maps
T: PZ > PZ (P is a finite set with more than one element) which are given by (Tx)i==F(xi+1, ..., xi+r), x=(xi)iEZ E PZ for some integers 1≤r and a mapping
F: Pr1+1 > P. We prove that if F is right (left) permutative (in Hedlund's
terminology) and 0≤1<r (resp. 1<r≤0), then the natural extension of the
dynamical system (PZ,B,μ,T) is a Bernoulli automorphism (μ stands for the
(1/p, ..., 1/p )Bernoulli measure on the full shift PZ). If r<0 or 1>0 and T
is surjective, then the natural extension of the system (PZ, B, μ, T) is a Kautomorphism.
We also prove that the shift Z2action on a twodimensional
subshift of finite type canonically associated with the cellular automaton T is
mixing, if F is both right and left permutative. Some more results about ergodic
properties of surjective cellular automata are obtained
Let X be a closed translationally invariant subset of the ddimensional
full shift PZd, where P is a finite set, and suppose that the Zdaction on X by
translations has positive topological entropy. Let G be a finitely generated group of
polynomial growth. In Chapter 2 we prove that if growth(G)<d, then any Gaction
on X by homeomorphisms commuting with translations is not expansive. On
the other hand, if growth(G) = d, then any Gaction on X by homeomorphisms
commuting with translations has positive topological entropy. Analogous results hold
for semigroups.
For a finite abelian group G define the twodimensional Markov shift
XG ={xEGZ2 : x(i,j) + x(i+1,j) + x(i,j+1) = 0 for all (i, j) E Z2 }. Let μG be the Haar
measure on the subgroup XG C GZ2. The group Z2 acts on the measure space
(XG, μG) by shifts. In Chapter 3 we prove that if G1 and G2 are pgroups and
E(G1)≠E(G2), where E(G) is the least common multiple of the orders of the
elements of G, then the shift actions on (XG1, μG1) and (XG2, μG2) are not
measuretheoretically isomorphic. We also prove that the shift actions on XG1 and
XG2 are topologically conjugate if and only if G1 and G2 are isomorphic.
In Chapter 4 we consider the closed shiftinvariant subgroups X<f> = = <f> ⊥c (Zp)Z2 defined by the principal ideals <f>c Zp [u±1, v±t] ≃ ((Zp)Z2)^
with f(u, v) = cf(0,0) + cf(1,0)u + cf(0,1)v, cf(i, j) E Zp\{0}, on which Z2
acts by shifts. We give the complete topological classification of these subshifts
with respect to measurable isomorphism.
Item Type:  Thesis or Dissertation (PhD) 

Subjects:  Q Science > QA Mathematics 
Library of Congress Subject Headings (LCSH):  Cellular automata, Transformations (Mathematics) 
Official Date:  1992 
Institution:  University of Warwick 
Theses Department:  Mathematics Institute 
Thesis Type:  PhD 
Publication Status:  Unpublished 
Supervisor(s)/Advisor:  Schmidt, Klaus, 1943 
Sponsors:  University of Warwick 
Extent:  119 leaves 
Language:  eng 
URI:  http://wrap.warwick.ac.uk/id/eprint/34640 
Request changes or add full text files to a record
Actions (login required)
View Item 
Downloads
Downloads per month over past year