Files in this item
Files  Description  Format 

application/pdf 8203480.pdf (2MB)  (no description provided) 
Description
Title:  Groups and Simple Languages 
Author(s):  HaringSmith, Robert Henry 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Mathematics 
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 prefixfree languages properly contained in the class of contextfree languages. Simple languages can be accepted by onestate 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 
Type:  Text 
Language:  English 
Description:  77 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1981. 
URI:  http://hdl.handle.net/2142/68190 
Other Identifier(s):  (UMI)AAI8203480 
Date Available in IDEALS:  20141214 
Date Deposited:  1981 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

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