Files in this item
Files  Description  Format 

application/pdf 8409771.pdf (3MB)  (no description provided) 
Description
Title:  Automata on Cayley Graphs 
Author(s):  Garzon, Maximiliano 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Mathematics 
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 grouptheoretic 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 grouptheoretic 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 1pebble automata but recursively unsolvable for 2pebble deterministic Cayley automata on cyclic cayley graphs. Various characterizations of the computational power of general cayley automata are also investigated. 
Issue Date:  1984 
Type:  Text 
Description:  99 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1984. 
URI:  http://hdl.handle.net/2142/71212 
Other Identifier(s):  (UMI)AAI8409771 
Date Available in IDEALS:  20141216 
Date Deposited:  1984 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois