Logic in Computer Science (LICS 1988)

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

Authors: Kevin J. Compton Claude Laflamme

Abstract

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