Files in this item



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


Title:Groups and Simple Languages
Author(s):Haring-Smith, Robert Henry
Department / Program:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Abstract:With any finitely generated presentation (pi) = of a group G, one can associate a formal language WP(,0)((pi)), the reduced word problem of (pi), consisting of all words on the generators and their inverses which are equal to the identity of G but have no proper prefix equal to the identity. A general problem, then, is to determine what the nature of the reduced word problem implies about the structure of the group G, or, conversely, how the properties of G affect WP(,0)((pi)).
The simple languages form a class of prefix-free languages properly contained in the class of context-free languages. Simple languages can be accepted by one-state deterministic pushdown automata which read an input symbol at every step in a computation. The main results of the thesis are:
Theorem. A finitely generated presentation (pi) of a group G has a simple reduced word problem if and only if there are only a finite number of simple closed paths passing through each vertex in the Cayley diagram of (pi).
Theorem. A group G has a presentation with a simple reduced word problem if and only if G is the free product of a finitely generated free group and a finite number of finite groups.
Issue Date:1981
Description:77 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1981.
Other Identifier(s):(UMI)AAI8203480
Date Available in IDEALS:2014-12-14
Date Deposited:1981

This item appears in the following Collection(s)

Item Statistics