An algebra and a logic for \(NC^ 1\) (Q2638772)

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.