A model-theoretic characterization of constant-depth arithmetic circuits

DOI10.1016/j.apal.2019.04.006zbMath1477.03120arXiv1603.09531OpenAlexW2950006226WikidataQ128073019 ScholiaQ128073019MaRDI QIDQ2273012

Anselm Haak, Heribert Vollmer

Publication date: 18 September 2019

Published in: Annals of Pure and Applied Logic, Logic, Language, Information, and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1603.09531

zbMATH Keywords

finite model theoryarithmetic circuitsSkolem functioncounting classesFagin's theorem

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Logic in computer science (03B70) Specification and verification (program logics, model checking, etc.) (68Q60) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Applications of model theory (03C98) Descriptive complexity and finite models (68Q19) Classical models of computation (Turing machines, etc.) (68Q04) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (2)

A logical characterization of constant-depth circuits over the reals ⋮ Descriptive complexity of \#P functions: a new perspective

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Model-checking games for logics of imperfect information
• Elements of finite model theory.
• Nondeterministic \(NC^1\) computation
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• Descriptive complexity of \(\#\)P functions
• On uniformity within \(NC^ 1\)
• A logic for constant-depth circuits
• Languages that Capture Complexity Classes
• Circuit Definitions of Nondeterministic Complexity Classes
• Descriptive Complexity of #AC^0 Functions

This page was built for publication: A model-theoretic characterization of constant-depth arithmetic circuits