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) 
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 
Actions (login required)
View Item 