### Definability by constant-depth polynomial-size circuits

by Denenberg and Gurevich and Shelah. [DGSh:213]

Information and Control, 1986

We investigate the expressive power of constant-depth polynomial-size
circuit models. In particular, we construct a circuit model whose
expressive power is precisely that of first-order logic.

Back to the list of publications