Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

On the ergodic theory of cellular automata and two-dimensional Markov shifts generated by them

Tools
- Tools
+ Tools

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

[img]
Preview
PDF
WRAP_THESIS_Shereshevsky_1992.pdf - Requires a PDF viewer.

Download (4Mb)
Official URL: http://webcat.warwick.ac.uk/record=b1403708~S15

Request Changes to record.

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 (PhD)
Subjects: Q Science > QA Mathematics
Library of Congress Subject Headings (LCSH): Cellular automata, Transformations (Mathematics)
Official Date: 1992
Dates:
DateEvent
1992Submitted
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

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us