Abstract
The tessellation automaton is a specific model of an infinite cellular array of uniform, interconnected finite state machines. A TA is specified as a four component system, M = (A,Zd, X,I). A is the finite set of states assumable by each individual machine in the array. The tessellation space or array is Zd, the set of lattice points of d-dimensional Euclidean space. Each lattice point is called a cell of the space, and a single finite state machine occupies each cell. The interconnections among the machines are specified by the neighborhood index, X, an ordered sequence of points of Zd. An individual machine is connected to the set of machines, which occupy the positions relative to it as specified in X. The array operates synchronously, with each machine taking on a state at discrete time intervals. The complete set of states of all machines in the array is called a configuration of the array. Transitions between successive array configurations are governed by a set of local transformations, which define the next state of an individual machine in terms of the present states of the machines connected to it. The fourth TA component, I, is the set of admissible global transformations determined by simultaneous application of local transformations to the entire array. This work is a study of the preservation of tessellation space configuration properties by tessellation automaton transformations. A property is any subset of the set of all configurations assumable by the space. A property P is preserved by a transformation T, if application of T to any configuration in P yields another configuration in P. The primary goal here is to find well-structured classes of transformations, which preserve properties. Properties of configurations studied include homogeneity, finite support periodicity, one and d-dimensional palindromes, and configurations in Z2 invariant under mappings of the dihedral group of the square. Transformation classes that preserve some of the above properties are the set of all global transformations, symmetric transformations, and transformations defined in terms of the dihedral group mappings. A study is also made of properties of classes of TA space configurations. This includes, in one dimension, the formal languages, and in d dimensions the linear predicates, classes of finite configurations recognizable in linear time by a bounded cellular space. A class of transformations that preserve linear predicates is found; this class might be useful in establishing a conjecture that all bounded cellular space recognizable predicates are linear. The final chapter studies the preservation and reproduction of individual finite patterns (sub configurations) in the tessellation space. A transformation is presented which preserves and reproduces any finite pattern of d-dimensional space, in a number of steps, which may be calculated from the size of the initial pattern.