Third Annual IEEE Symposium on

Logic in Computer Science (LICS 1988)

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

Authors: Kevin J. Compton Claude Laflamme


An algebra and a logic characterizing the complexity class NC1, which consists of functions computed by uniform sequences of polynomial-size, log depth circuits, are presented. In both characterizations, NC1 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


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