Sh:213

• Denenberg, L., Gurevich, Y., & Shelah, S. (1986). Definability by constant-depth polynomial-size circuits. Inform. And Control, 70(2-3), 216–240. DOI: 10.1016/S0019-9958(86)80006-7 MR: 859107
• Abstract:
  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.
• published version (25p)

@article{Sh:213,
 author = {Denenberg, Larry and Gurevich, Yuri and Shelah, Saharon},
 title = {{Definability by constant-depth polynomial-size circuits}},
 journal = {Inform. and Control},
 fjournal = {Information and Control},
 volume = {70},
 number = {2-3},
 year = {1986},
 pages = {216--240},
 issn = {0019-9958},
 mrnumber = {859107},
 mrclass = {03G05 (03C40 06E30 68Q15 94C10)},
 doi = {10.1016/S0019-9958(86)80006-7}
}