An algebra and a logic for \(NC^ 1\) (Q2638772)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An algebra and a logic for \(NC^ 1\) |
scientific article |
Statements
An algebra and a logic for \(NC^ 1\) (English)
0 references
1990
0 references
This paper, which appeared in an earlier version \textit{K. Compton} and \textit{C. Laflamme} [A logic and an Algebra for \(NC^ 1\) in: Proc. 3rd Annual Conference on Logic in Computer Science, (1988; Washington (IEEE Computer Society Press)], presents an algebra and a logic characterizing the complexity class \(NC^ 1\). In the algebraic characterization a recursion scheme called upward tree recursion is 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 provided that every structure has a relation giving the binary representations of integers.
0 references
complexity class \(NC^ 1\)
0 references