Canonical bases, also called SAGBI bases, for subalgebras of the non-commutative polynomial ring are investigated. The process of subalgebra reduction is defined. Methods, including generalizations of the standard Gr obner bases techniques, are developed for the test whether bases are canonical, and for the completion procedure of constructing canonical bases. The special case of homogeneous subalgebras is discussed.

In this paper we study canonical bases, analogs of Gr obner bases for ideals, for subalgebras of K (X), the free associative algebra over the field K in the set of indeterminates X. Following the paper [8] by Robbiano and Sweedler, we will call these bases SAGBI bases, where SAGBI is an abbreviation for Subalgebra Analog to Gr obner Bases for Ideals. SAGBI bases theory was introduced, for commutative polynomial rings, by Kapur and Madlener (see [3]), and independently by Robbiano and Sweedler ([8]). This paper follows the approach of Robbiano and Sweedler. The subject has been studied further by eg Ollivier in [6], where also an implementation in a computer algebra system is discussed. See also [10] for additional references. The SAGBI theory is strongly influenced by the theory of Gr obner bases, introduced by Bruno Buchberger in his thesis [2]. The reader familiar with Gr obner bases techniques will recognize many of Buchberger's basic ideas. Some problems concerning subalgebras, eg subalgebra membership, can be reduced to Gr obner basis problems. This has been performed for commutative polynomial rings by Shannon and Sweedler ([9]), and the easy generalization to the non-commutative case can be found in [5]. We will later refer to some of these techniques. We then of course need the theory of non-commutative Gr obner bases; the standard reference here is the paper [4] by Mora. In the commutative case, SAGBI bases differ from Gr obner bases at one essential point; they may be infinite even for finitely generated subalgebras. This implies that