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. 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.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
﻿ Show simple item record