Files in this item
|(no description provided)|
|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.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1981.
|Date Available in IDEALS:||2014-12-14|