When Barrington gave his characterization of NC1 in terms of branching programs, it became clear that circuit classes have surprisingly strong connections to algebraic structures. The M-program model (for programs over a monoid M) was developed to investigate these connections, and much interesting work followed, investigating subclasses of NC1 in this framework.
Until the work of Bédard, Lemieux, and McKenzie, it seemed this algebraic approach had no application beyond NC1. In this paper, however, they show that considering the more general algebraic notion of a groupoid (that is, relaxing the requirement that the algebra be associative) characterizes the important complexity class LOGCFL. (LOGCFL is the class of languages that are logspace-reducible to context-free languages. Alternatively, it is the class of sets accepted by log-depth semi-unbounded fan-in circuits.)
The authors show that many other important complexity classes can be characterized by groupoid-programs, and they show that these characterizations succeed both when one constant-sized groupoid is used and when the groupoid is allowed to depend on the input size (so-called “growing” groupoids).
Programs over growing algebras had not been investigated previously in the M-program model. The final section of the paper presents upper and lower bounds on the expressive power of growing monoids and groups with the added restriction of being Abelian.
The results are important and the paper is well written. Pieces of the proof are left to the reader in a number of places, but these pieces can be filled in with reasonable effort on the reader’s part.
