A model-theoretic characterization of constant-depth arithmetic circuits

DOI10.1016/J.APAL.2019.04.006MaRDI QIDQ6828200zbMATH OpenFDO

Authors Anselm Haak, Heribert Vollmer

Publication date 18 September 2019

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.APAL.2019.04.006

zbMATH Keywords

arithmetic circuitscounting classesFagin's theoremfinite model theorySkolem function

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Classical models of computation (Turing machines, etc.) (68Q04) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Cited in

(1)

• A logical characterization of constant-depth circuits over the reals

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

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