Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth

DOI10.1145/3209108.3209179zbMath1497.68225arXiv1710.01934OpenAlexW2963145533MaRDI QIDQ5145309

Arnaud Durand, Heribert Vollmer, Anselm Haak

Publication date: 20 January 2021

Published in: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

finite model theoryarithmetic circuitsdescriptive complexitycounting classes

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (3)

A logical characterization of constant-depth circuits over the reals ⋮ Descriptive complexity of \#P functions: a new perspective ⋮ Counting of Teams in First-Order Team Logics

This page was built for publication: Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth