Automata and Symbolic Dynamics

A "shift" is a collection of bi-infinite strings over a finite alphabet membership of which is determined by the absence of a certain proscribed set of forbidden substrings. Shifts can also be characterised as those sets of strings closed under shifting of the position of the 0th letter and closed under the topology of simple convergence (as will be explained). The shifts that arise in the storage of information on CDs and the like are the Finite Shifts which are those that can be defined by a finite set of forbidden words. The mathematical description of finite shifts however quickly leads one outside of this class as the contiunuous image of a finite shift is not in general a finite shift but rather a so-called sofic shift - one that can be read on a finite automaton. This extended class is however complete under topological closure and these features of the basic theory will be among those highlighted and explained in the talk through representative examples.