Extensions to Barrington's M-program model

AbstractBarrington's “polynomal-length program over a monoid” is a model of computation which has been studied intensively in connection with the structure of the complexity class NC1 [Barrington (1986), Barrington and Thérien (1987, 1988), McKenzie and Thérien (1989), Péladeau (1989)]. Here two extensions of the model are considered. First, with the use of nonassociative structures (hence, groupoids) instead of (associative) monoids, polynomial-length program characterizations of complexity classes TC0, NL, and LOGCFL, as well as new characterizations of NC1, are given. New “word problems” complete for LOGCFL, for NL and for NC1 under DLOGTIME-reductions are obtained as corollaries. Second, using monoids but permitting the use of a different monoid to handle each input length, new complexity classes are defined. Combinatorial arguments are then developed to resolve the relationships between various such classes defined in terms of polynomial-length programs over growing abelian monoid sequences. Then the orders of growing abelian group and monoid sequences required to accept specific languages defined in terms of the presence of a given substring are investigated. Finally, the two extensions are combined to obtain characterizations of L and NL in terms of polynomial-length programs defined over polynomially growing groupoid sequences. It is further argued that such programs are generally no more powerful than LOGCFL