A logic for constant-depth circuits

Show simple item record

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 http://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.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
 Show simple item record

This item appears in the following Collection(s)


Search Deep Blue

Advanced Search

Browse by

My Account

Information

Coming Soon


MLibrary logo