This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/71212
Description
Title
Automata on Cayley Graphs
Author(s)
Garzon, Maximiliano
Issue Date
1984
Department of Study
Mathematics
Discipline
Mathematics
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(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 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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
