Browse Theses

A subshift $K$ $\subseteq$ $S\sp{\rm Z}$ (closed, shift-invariant subset) of the full shift on a finite set $S$, is determined by the language ${\cal L}(K$) of finite subblocks of elements of $K$. There is a bijective correspondence between subshifts and a class of languages called admissible languages. This correspondence allows a subshift $K$ to be described in terms of the complexity of the language ${\cal L}(K$). A study is made of subshifts which correspond to the classes of languages which make up the Chomsky Hierarchy comprising recursively enumerable languages, context-sensitive languages, context-free languages, and regular languages.

A cellular automaton map $F~: S\sp{\rm Z}$ $\to$ $S\sp{\rm Z}$ is a continuous shift-commuting self-map on the shift. The image $F(S\sp{\rm Z}$) of $F$, the limit set $\Lambda (F)$, the non-wandering set $\Omega (F)$, and the closure $\Pi (F)$ of the points periodic under $F$ are studied. The image of a cellular automaton map, $F(S\sp{\rm Z}$) has the property that its finite subblocks ${\cal L}(F(S\sp{\rm Z}))$ form a regular language. Equivalently $F(S\sp{\rm Z})$ is a sofic system. The remaining sets can give rise to more complicated languages.

Examples are given of cellular automata for which the finite strings in the limit set ${\cal L}(\Lambda(F))$ form a non-regular context-free language, and a non-context-free context-sensitive language. In each case the language determined by the periodic points ${\cal L}(\Pi(F))$ and the non-wandering set ${\cal L}(\Omega(F))$ yield languages of the same level of complexity.

A rule $F\sb{u}$ is constructed for which ${\cal L}(\Lambda(F\sb{u}))$ is not recursively enumerable.

Membership in each of the Chomsky classes is preserved under cellular automaton maps. If $K$ $\subseteq$ $S\sp{\rm Z}$ is a subshift, $F$ a cellular automaton map, and ${\cal L}(K)$ is a language of a given class, ${\cal L}(F(K))$ is a language in the same class. It is shown, however, that membership in a language class is not generally preserved by inverse CA maps.

Given a CA rule $F$: $S\sp{\rm Z}$ $\to$ $S\sp{\rm Z}$, and a subshift $K$ $\subseteq$ $S\sp{\rm Z}$ such that ${\cal L}(K)$ is a regular language (equivalently $K$ is a sofic system), algorithms are described which take a Finite Automaton recognizing ${\cal L}(K)$ and produce Finite Automata recognizing ${\cal L}(F(K))$ and ${\cal L}(F\sp{-1}(K))$.