Vol. 61, No. 2, 1975

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 305: 1  2
Vol. 304: 1  2
Vol. 303: 1  2
Vol. 302: 1  2
Vol. 301: 1  2
Vol. 300: 1  2
Vol. 299: 1  2
Vol. 298: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Editorial Board
Subscriptions
Officers
Special Issues
Submission Guidelines
Submission Form
Contacts
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Author Index
To Appear
 
Other MSP Journals
The word problem and power problem in 1-relator groups are primitive recursive

Frank Benjamin Cannonito and Ronald Wallace Gatterdam

Vol. 61 (1975), No. 2, 351–359
Abstract

The purpose of this paper is to show the solution to the word problem in a 1-relator group can be computed with respect to an effective indexing of the group by an algorithm at level at most 2 + σ(R) of the Grzegorczyk hierarchy, where σ(R) is the length of the relator, and by a primitive recursive function, always. As a consequence, it is shown that the power problem in a 1-relator group can be solved similarly. An example is given in which the Magnus algorithm for the extended word problem is at leve1 4 but not 3 of the Grzegorczyk hierarchy even though the word problem is solvable at leve1 3.

Mathematical Subject Classification 2000
Primary: 02F47, 02F47
Secondary: 20F10, 20E10
Milestones
Received: 5 July 1974
Revised: 5 August 1975
Published: 1 December 1975
Authors
Frank Benjamin Cannonito
Ronald Wallace Gatterdam