International Journal of Algebra and Computation

By exploiting a new technique for proving undecidability results developed by A. Sattler-Klein in her doctoral dissertation (1996) it is shown that it is undecidable in general whether or not a finitely presented monoid with a polynomial-time decidable word problem has finite derivation type (FDT). This improves upon the undecidability result of R. Cremanns and F. Otto (1996), which was based on the undecidability of the word problem for the finitely presented monoids considered.

A sequence is defined for a monoid consisting of upper triangular matrices. This sequence is analogous to the derived sequence of the solvable group. The relationship between the two sequences is investigated and sets of upper triangular partial permutation matrices, which arise naturally from this relation, are examined.

The G -spectrum of a class of algebras is the function that counts, up to isomorphism, the number of at most k -generated algebras in the class, for k =1,2,… . We consider the G -spectra of the varieties of algebras generated by a single two-element algebra. We show that such spectra are either polynomial, exponential, or at least doubly exponential as a function of k . For the varieties that have polynomial or exponential G -spectra we provide an exact formula for the function.

Let F be a free group with basis a, b, …, and let u, w ∈ F . We say that u is a root of w if w belongs to the normal closure of u in F . We show that if w is of the form a^kb^l then w has only a finite number of conjugacy classes of roots, and that given k and l the set of roots of w can be algorithmically determined. We also classify the roots of elements of the form a^kba^-kb^-1.

It has been shown that the axioms of iteration theories capture the equational properties of iteration in several different models related to computer science. Iteration theories are axiomatizable by the Conway identities and the group-identities corresponding to the finite (simple) groups. In this paper we provide a complete analysis of these identities by giving a concrete description of the free theories in the variety axiomatized by the Conway identities and any given subcollection of the group-identities. It follows that when the group-identities are effectively given, the equational theory of the variety is decidable.