On NC1 Language Recognition
Elizabeth Capel · Summit (Simon Fraser University) · 1989
The objective of this thesis is to give a self-contained account of some recent work in automata theory and complexity theory.This account will focus primarily on David A.Barrington's work on bounded width branching programs and the parallel complexity class NC'.Preliminary topics necessary for a full understanding of the new work, including languages, monoids, and Boolean circuits, are presented, a detailed reconstruction of the proof of Barrington's main result is given, and related results are discussed.