clarke@csri.toronto.edu (Jim Clarke) (03/16/89)
THEORY SEMINAR - Thursday, March 30, 3 p.m. in Room GB 244
(GB = Galbraith Building, 35 St. George Street)
Denis Therien
McGill University
"NC^1: an algebraic point of view"
Bounded-width branching programs of polynomial length and constant
fan-in boolean circuits of O(log n) depth have the same computing power.
Observing that programs can be viewed as performing their computations
in finite monoids, we can parametrize the underlying complexity class by
res- tricting the algebraic structure of the monoids being invoved.
Several natural subclasses of NC^1 can thus be characterized: a
typical example is the correspondence between AC^0 and
computations in finite aperiodic monoids. A coherent framework to describe
the internal structure of NC^1 is obtained by adapting ideas from the
well-developed algebraic theory of automata. The talk will present an
overview of this approach, including recent results and conjectures.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
clarke@csri.toronto.edu or clarke@csri.utoronto.ca
or ...!{uunet, pyramid, watmath, ubc-cs}!utai!utcsri!clarke