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