Extensions to Barrington's M-program model
François Bédard, François Lemieux, Pierre McKenzie · 2002
Groupoids are used instead of monoids to extend D.A. Barrington's (1988) successful polynomial length program over a monoid computation model to characterize complexity classes TC and LOGCFL. Further allowing groupoid families instead of fixed groupoids, deterministic and nondeterministic logarithmic space are also characterized. Several language classes arising from extended programs over Abelian monoid families are investigated.>