The formalism of programs over monoids has been studied for its close
connection to parallel complexity classes defined by small-depth
boolean circuits. We investigate two basic questions about this
model. When is a monoid rich enough that it can recognize arbitrary
languages (provided no restriction on length is imposed)? When is a
monoid weak enough that all its computations can be realized in
polynomial length? Surprisingly, these two properties appear to be
dual to each other.