University of Illinois Urbana-Champaign

Groups and Simple Languages

Haring-Smith, Robert Henry

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/68190

Description

Title
Groups and Simple Languages
Author(s)
Haring-Smith, Robert Henry
Issue Date
1981
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
Language
eng
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.
Graduation Semester
1981
Type of Resource
text
Permalink
http://hdl.handle.net/2142/68190

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Mathematics