Abstract:
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.