Extensions to Barrington's M-program model

摘要

Groupoids are used instead of monoids to extend D.A. Barrington's(1988) successful polynomial length program over a monoid computationmodel to characterize complexity classes TC and LOGCFL. Further allowinggroupoid families instead of fixed groupoids, deterministic andnondeterministic logarithmic space are also characterized. Severallanguage classes arising from extended programs over Abelian monoidfamilies are investigated