Canonical forms for free k-semigroups

Abstract

The implicit signature kappa consists of the multiplication and the (omega-1)-power. We describe a procedure to transform each kappa-term over a finite alphabet A into a certain canonical form and show that different canonical forms have different interpretations over some finite semigroup. The procedure of construction of the canonical forms, which is inspired in McCammond's normal form algorithm for omega-termsninterpreted over the pseudovariety A of all finite aperiodic semigroups, consists in applying elementary changes determined by an elementary set Sigma of pseudoidentities. As an application, we deduce that the variety of kappa-semigroups generated by the pseudovariety S of all finite semigroups is defined by the set Sigma and that the free kappa-semigroup generated by the alphabet A in that variety has decidable word problem. Furthermore, we show that each omega-term has a unique omega-term in canonical form with the same value over A. In particular, the canonical forms provide new, simpler, representatives for omega-terms interpreted over that pseudovariety.