  The program-over-monoid model of computation originates with Barrington's
proof that it captures the complexity class NC$^1$. Here we make progress in
understanding the subtleties of the model. First, we identify a new tameness
condition on a class of monoids that entails a natural characterization of the
regular languages recognizable by programs over monoids from the class. Second,
we prove that the class known as DA satisfies tameness and hence that the
regular languages recognized by programs over monoids in DA are precisely those
recognizable in the classical sense by morphisms from QDA. Third, we show by
contrast that the well studied class of monoids called J is not tame. Finally,
we exhibit a program-length-based hierarchy within the class of languages
recognized by programs over monoids from DA.
