2026-09-20T08:28:26Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/68190 2023-07-11 col_2142_5131 col_2142_16340 com_2142_5130 com_2142_16339 com_2142_8903

Haring-Smith, Robert Henry 2014-12-14T13:09:52Z 2014-12-14T13:09:52Z 10000-01-01 1981 1981 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. Made available in DSpace on 2014-12-14T13:09:52Z (GMT). No. of bitstreams: 1 8203480.pdf: 2129536 bytes, checksum: 470dcb09d22e97b91c16b509fb2ca804 (MD5) Previous issue date: 1981 Embargo set by: Seth Robbins for item 68368 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs U of I Only 77 p. Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1981. http://hdl.handle.net/2142/68190 (UMI)AAI8203480 eng Mathematics Groups and Simple Languages text Mathematics Mathematics University of Illinois at Urbana-Champaign Dissertation Ph.D.