The authors consider the test pattern generation problem for circuits that compute expressions over free monoids. They study two computations, expression evaluation and parallel prefix computation. In both cases, the family of all finite monoids can be partitioned into three classes corresponding to constant, logarithmic, and linear test complexity. For instance, groups belong to the first class. Circuits with optimal test sets are presented, and efficient methods for determining the test complexity of a finite monoid are given.