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)
Official Date:	1992
Dates:	Date Event 1992 Submitted
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