A logic for constant-depth circuits
dc.contributor.author | Gurevich, Yuri | en_US |
dc.contributor.author | Lewis, Harry R. | en_US |
dc.date.accessioned | 2006-04-07T18:29:05Z | |
dc.date.available | 2006-04-07T18:29:05Z | |
dc.date.issued | 1984-04 | en_US |
dc.identifier.citation | Gurevich, Yuri, Lewis, Harry R. (1984/04)."A logic for constant-depth circuits." Information and Control 61(1): 65-74. <http://hdl.handle.net/2027.42/24848> | en_US |
dc.identifier.uri | http://www.sciencedirect.com/science/article/B7MFM-4G3KBD1-S/2/e1f1c3ad5b87e53e750065b0f702506c | en_US |
dc.identifier.uri | https://hdl.handle.net/2027.42/24848 | |
dc.description.abstract | Consider a family of boolean circuitsC1,C2,...,Cn,..., constructed by some uniform, effective procedure operating on inputn. Such a procedure provides a concise representation of a family of parallel algorithms for computing boolean values. A formula of first-order logic may also be viewed as a concise representation of a family of parallel algorithms for evaluating boolean functions. The parallelism is implicit in the quantification (a formula [for all]x(x) is true if and only if each of the formulas(a) is true, and all these formulas can be checked simultaneously), and universes of different sizes give rise to boolean functions with different numbers of inputs (the boolean values of the formula's predicates on various combinations of elements of the universe). This note presents an extended first-order logic designed to be exactly equivalent in expressiveness to polynomialsize, constant-depth, unbounded-fan-in circuits constructed by Turing machines of bounded computational complexity. | en_US |
dc.format.extent | 543043 bytes | |
dc.format.extent | 3118 bytes | |
dc.format.mimetype | application/pdf | |
dc.format.mimetype | text/plain | |
dc.language.iso | en_US | |
dc.publisher | Elsevier | en_US |
dc.title | A logic for constant-depth circuits | en_US |
dc.type | Article | en_US |
dc.rights.robots | IndexNoFollow | en_US |
dc.subject.hlbsecondlevel | Science (General) | en_US |
dc.subject.hlbsecondlevel | Information and Library Science | en_US |
dc.subject.hlbsecondlevel | Computer Science | en_US |
dc.subject.hlbtoplevel | Science | en_US |
dc.subject.hlbtoplevel | Social Sciences | en_US |
dc.subject.hlbtoplevel | Engineering | en_US |
dc.description.peerreviewed | Peer Reviewed | en_US |
dc.contributor.affiliationum | University of Michigan, Ann Arbor, Michigan USA | en_US |
dc.contributor.affiliationother | Aiken Computation Laboratory, Harvard University, Cambridge, Massachusetts USA | en_US |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/24848/1/0000275.pdf | en_US |
dc.identifier.source | Information and Control | en_US |
dc.owningcollname | Interdisciplinary and Peer-Reviewed |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
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.