A logic for constant-depth circuits

DOI10.1016/S0019-9958(84)80062-5zbMath0592.94023MaRDI QIDQ3722427

Harry R. Lewis, Yuri Gurevich

Publication date: 1984

Published in: Information and Control (Search for Journal in Brave)

zbMATH Keywords

computational complexityTuring machinesBoolean functionsBoolean circuitsextended first-order logicconcise representation of a family of parallel algorithmsunbounded-fan- in circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract data types; algebraic specification (68Q65) Classical first-order logic (03B10) Algorithms in computer science (68W99) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items

Threshold circuits of bounded depth ⋮ Parameterized Parallel Computing and First-Order Logic ⋮ Extensions of an idea of McNaughton ⋮ Tailoring recursion for complexity ⋮ y= 2xVS.y= 3x ⋮ Arithmetizing uniform \(NC\) ⋮ Tailoring recursion for complexity ⋮ Logically defined subsets of \(\mathbb{N}{}^ k\) ⋮ Formulas, regular languages and Boolean circuits ⋮ Typed Monoids – An Eilenberg-Like Theorem for Non Regular Languages ⋮ A model-theoretic characterization of constant-depth arithmetic circuits ⋮ Ehrenfeucht-Fraïssé Games on Random Structures ⋮ Languages defined with modular counting quantifiers