Files in this item



application/pdf8409771.pdf (3MB)Restricted to U of Illinois
(no description provided)PDF


Title:Automata on Cayley Graphs
Author(s):Garzon, Maximiliano
Department / Program:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Abstract:Two fundamental properties of the ordinary doubly infinite tape of a Turing machine are hidden behind the contents of the symbols written on it. An observer standing on a blank tape will be unable to distinguish one cell from another on the sole basis of their local appearance or relative position: the tape is homogeneous and isotropic. Therefore, an attempt to generalize the notion of a tape should lead to an object which, while preserving these properties allows, on the other hand, the flexibility of interpretation to realize very general kinds of inputs. Any graph with the above two properties of a tape must, in fact, be the Cayley graph of a suitable group. Recent investigations by various authors have begun to shed some light on what promises to be intimate connections between the geometry of a Cayley graph and the group-theoretic properties of the underlying group.
A Cayley automation consists of a finite control capable of assuming any of a finite number of given states while it scans the vertices of an input Cayley graph. Any such device uncapable of writing will be lost in the homogeneity of its input. Thus a Cayley automaton is further endowed with a finite number of pebbles which it can manipulate on its input graphs with a distinguished origin. Initially, the finite control is poised in a designated initial state over a vertex arbitrarily distinguished on the graph as the identity element of the associated group. Thereafter, the automaton moves about from vertex to vertex, 'sliding' along the labelled edges of its input in successive discrete time steps, switching from one state to another in accordance with the transition function of the automaton. It will accept the current input graph if any state of a special subset of final states is ever entered in the course of its computation. The automaton thus defines a collection, or 'language', consisting precisely of those Cayley graphs which it accepts.
The purpose of this thesis is twofold: first, it is to identify the fundamental properties of Cayley graph languages in relation to the group-theoretic properties of the underlying groups; and, secondly, it is to investigate the solvability or unsolvability of their decision problems. It is shown that most decision problems are effectively solvable for 1-pebble automata but recursively unsolvable for 2-pebble deterministic Cayley automata on cyclic cayley graphs. Various characterizations of the computational power of general cayley automata are also investigated.
Issue Date:1984
Description:99 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1984.
Other Identifier(s):(UMI)AAI8409771
Date Available in IDEALS:2014-12-16
Date Deposited:1984

This item appears in the following Collection(s)

Item Statistics