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

DOI: 10.2140/pjm.1975.61.351

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