Shereshevsky, Mark Alexandrovich (1992) On the ergodic theory of cellular automata and two-dimensional Markov shifts generated by them. PhD thesis, University of Warwick.

Preview

PDF WRAP_THESIS_Shereshevsky_1992.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (4Mb)

Abstract

In this thesis we study measurable and topological dynamics of certain classes of cellular automata and multi-dimensional subshifts. In Chapter 1 we consider one-dimensional 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: Pr-1+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 Z2-action on a two-dimensional 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 d-dimensional full shift PZd, where P is a finite set, and suppose that the Zd-action 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 G-action on X by homeomorphisms commuting with translations is not expansive. On the other hand, if growth(G) = d, then any G-action on X by homeomorphisms commuting with translations has positive topological entropy. Analogous results hold for semigroups. For a finite abelian group G define the two-dimensional 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 p-groups 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 measure-theoretically 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 shift-invariant 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

Request changes to a record

Actions (login required)

View Item