## Paper: An algebra and a logic for NC¹ (at LICS 1988)

**Kevin J. Compton Claude Laflamme**

### Abstract

An algebra and a logic characterizing the complexity class NC^{1}, which consists of functions computed by uniform sequences of polynomial-size, log depth circuits, are presented. In both
characterizations, NC^{1} functions are regarded as functions from one class of finite relational structures to another. In the algebraic characterization,
upward and downward tree recursion are applied to a class of simple functions. In the logical characterization, first-order
logic is augmented by an operator for defining relations by primitive recursion. It is assumed that every structure has an
underlying relation giving the binary representations of integers

### BibTeX

@InProceedings{ComptonLaflamme-Analgebraandalogicf, author = {Kevin J. Compton and Claude Laflamme}, title = {An algebra and a logic for NC¹}, booktitle = {Proceedings of the Third Annual IEEE Symposium on Logic in Computer Science (LICS 1988)}, year = {1988}, month = {July}, pages = {12--21}, location = {Edinburgh, Scotland, UK}, publisher = {IEEE Computer Society Press} }