Definability by constant-depth polynomial-size circuits

Browse:


Log in to My Deep Blue to
	Deposit/Edit Items authorized users
	Receive email updates
	Edit Your Profile


Get more info
	About Deep Blue
	Help
	Contact Us

Deep Blue at the University of Michigan > Research Collections > Interdisciplinary and Peer-Reviewed >

Please use this persistent URL to cite or link to this item:

http://hdl.handle.net/2027.42/26084 ◀ bookmark this

Title:	Definability by constant-depth polynomial-size circuits
Authors:	Denenberg, Larry Gurevich, Yuri Shelah, Saharon
Issue Date:	1986
Publisher:	Elsevier
Citation:	Denenberg, 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>
Abstract:	A 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.
URI:	http://www.sciencedirect.com/science/article/B7MFM-4G3DGHT-3 2/2/4dfbaa4efc717c9117e3e98ee9e46945
Appears in Collections:	Interdisciplinary and Peer-Reviewed Electrical Engineering and Computer Science, Department of (EECS)

Files in This Item:

File	Description	Size	Format
0000160.pdf		1423Kb	Adobe PDF	View/Open

Deep Blue encourages the fair use of copyrighted material, and you are free to link to content here without asking for permission. Consult the document(s) and/or contact the copyright holder for additional rights questions and requests.