Show simple item record

Definability by constant-depth polynomial-size circuits

dc.contributor.authorDenenberg, Larryen_US
dc.contributor.authorGurevich, Yurien_US
dc.contributor.authorShelah, Saharonen_US
dc.date.accessioned2006-04-07T19:27:58Z
dc.date.available2006-04-07T19:27:58Z
dc.date.issued1986en_US
dc.identifier.citationDenenberg, Larry, Gurevich, Yuri, Shelah, Saharon (1986)."Definability by constant-depth polynomial-size circuits." Information and Control 70(2-3): 216-240. <http://hdl.handle.net/2027.42/26084>en_US
dc.identifier.urihttp://www.sciencedirect.com/science/article/B7MFM-4G3DGHT-32/2/4dfbaa4efc717c9117e3e98ee9e46945en_US
dc.identifier.urihttps://hdl.handle.net/2027.42/26084
dc.description.abstractA function of boolean arguments is symmetric if its value depends solely on the number of 1's among its arguments. In the first part of this paper we partially characterize those symmetric functions that can be computed by constant-depth polynomial-size sequences of boolean circuits, and discuss the complete characterization. (We treat both uniform and non-uniform sequences of circuits.) Our results imply that these circuits can compute functions that are not definable in first-order logic. In the second part of the paper we generalize from circuits computing symmetric functions to circuits recognizing first-order structures. By imposing fairly natural restrictions we develop a circuit model with precisely the power of first-order logic: a class of structures is first-order definable if and only if it can be recognized by a constant-depth polynomial-time sequence of such circuits.en_US
dc.format.extent1457745 bytes
dc.format.extent3118 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypetext/plain
dc.language.isoen_US
dc.publisherElsevieren_US
dc.titleDefinability by constant-depth polynomial-size circuitsen_US
dc.typeArticleen_US
dc.rights.robotsIndexNoFollowen_US
dc.subject.hlbsecondlevelScience (General)en_US
dc.subject.hlbsecondlevelInformation and Library Scienceen_US
dc.subject.hlbsecondlevelComputer Scienceen_US
dc.subject.hlbtoplevelScienceen_US
dc.subject.hlbtoplevelSocial Sciencesen_US
dc.subject.hlbtoplevelEngineeringen_US
dc.description.peerreviewedPeer Revieweden_US
dc.contributor.affiliationumUniversity of Michigan, Ann Arbor, Michigan USAen_US
dc.contributor.affiliationotherHarvard University, Cambridge, Massachusetts USAen_US
dc.contributor.affiliationotherHebrew University, Tel-Aviv, Israelen_US
dc.description.bitstreamurlhttp://deepblue.lib.umich.edu/bitstream/2027.42/26084/1/0000160.pdfen_US
dc.identifier.sourceInformation and Controlen_US
dc.owningcollnameInterdisciplinary and Peer-Reviewed


Files in this item

Show simple item record

Accessibility: If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.