Title :
Extensions to Barrington´s M-program model
Author :
Bédard, François ; Lemieux, François ; Mckenzie, Pierre
Author_Institution :
Dept. d´´Inf. et Recherche Oper., Montreal Univ., Que., Canada
Abstract :
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
Keywords :
automata theory; computational complexity; formal languages; Abelian monoid families; LOGCFL; M-program model; TC; complexity classes; groupoid families; language classes; logarithmic space; monoid computation model; polynomial length program; Circuits; Computational modeling; Context modeling; Polynomials; Scholarships;
Conference_Titel :
Structure in Complexity Theory Conference, 1990, Proceedings., Fifth Annual
Conference_Location :
Barcelona
Print_ISBN :
0-8186-6072-4
DOI :
10.1109/SCT.1990.113968
