A logic for constant-depth circuits

DOI10.1016/S0019-9958(84)80062-5MaRDI QIDQ3722427zbMATH OpenFDO

Authors Harry R. Lewis, Yuri Gurevich

Publication date 1984

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

Full work available at URL https://doi.org/10.1016/S0019-9958(84)80062-5

zbMATH Keywords

Boolean circuitsBoolean functionscomputational complexityconcise representation of a family of parallel algorithmsextended first-order logicTuring machinesunbounded-fan- in circuits

Mathematics Subject Classification ID

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

Recommendations

• Definability by constant-depth polynomial-size circuits
• scientific article; zbMATH DE number 1086678
• Limiting Negations in Constant Depth Circuits
• A constant-space sequential model of computation for first-order logic
• On uniformity within \(NC^ 1\)

Cited in

(29)

• Arithmetizing uniform NC
• Logically defined subsets of \(\mathbb{N}{}^ k\)
• Formulas, regular languages and Boolean circuits
• Languages defined with modular counting quantifiers
• A logical characterization of constant-depth circuits over the reals
• Logical language of description of polynomial computing
• Threshold circuits of bounded depth
• Typed monoids -- an Eilenberg-like theorem for non regular languages
• The quantifier complexity of polynomial-size iterated definitions in first-order logic
• Extensions of an idea of McNaughton
• Propositional Logic for Circuit Classes
• Ehrenfeucht-Fraïssé Games on Random Structures
• A Depth-Universal Circuit
• Limiting Negations in Constant Depth Circuits
• scientific article; zbMATH DE number 408789 (Why is no real title available?)
• y= 2xVS.y= 3x
• scientific article; zbMATH DE number 1072417 (Why is no real title available?)
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• Tailoring recursion for complexity
• Tailoring recursion for complexity
• Parameterized Parallel Computing and First-Order Logic
• A constant-space sequential model of computation for first-order logic
• Unary and two-variable interval logics
• Quantum first-order logics and quantum natural deduction
• Towards new characterizations of small circuit classes via discrete ordinary differential equations
• The \(\text{AC}^0\)-complexity of visibly pushdown languages
• Quantum first-order logics that capture logarithmic-time/space quantum computability
• A new characterization of FAC^0 via discrete ordinary differential equations
• Characterizing small circuit classes from FAC^0 to FAC^1 via discrete ordinary differential equations

This page was built for publication: A logic for constant-depth circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3722427)