TERMINATION FOR A CLASS OF ALGORITHMS FOR CONSTRUCTING ALGEBRAS GIVENBY GENERATORS AND RELATIONS

We consider a certain type of algorithm designed to construct the mult iplication table of algebras given by generators and relations. These computations may be performed for various classes of (not necessarily associative) algebras, such as Lie (super)algebras, Jordan algebras, a ssociative algebras; in general, for any class of algebras axiomatised by suitable polynomial identities. The type of algorithm considered i s based on straightforward computations in the free non-associative al gebra on the generators, which do not depend in an essential way on th e axioms of the class of algebras, in particular no concept of ''repre sentation'' of the algebra is used. The algorithm itself is only parti ally specified: it proceeds by repeatedly taking steps chosen from a l imited repertoire of very simple possibilities, but no fixed strategy for selecting steps is assumed. We study the question whether terminat ion of the algorithm is guaranteed for those inputs that actually desc ribe a finite-dimensional algebra (the question whether some arbitrary input has this property is not algorithmically decidable). We prove u nder certain assumptions about the strategy that termination is indeed guaranteed in this case. (C) 1997 Elsevier Science B.V.