Details
| Original language | English |
|---|---|
| Pages (from-to) | 1008-1029 |
| Number of pages | 22 |
| Journal | Annals of Pure and Applied Logic |
| Volume | 170 |
| Issue number | 9 |
| Early online date | 11 Apr 2019 |
| Publication status | Published - Sept 2019 |
Abstract
We study the class #AC0 of functions computed by constant-depth polynomial-size arithmetic circuits of unbounded fan-in addition and multiplication gates. No model-theoretic characterization for arithmetic circuit classes is known so far. Inspired by Immerman's characterization of the Boolean circuit class AC0, we remedy this situation and develop such a characterization of #AC0. Our characterization can be interpreted as follows: Functions in #AC0 are exactly those functions counting winning strategies in first-order model checking games. A consequence of our results is a new model-theoretic characterization of TC0, the class of languages accepted by constant-depth polynomial-size majority circuits.
Keywords
- Arithmetic circuits, Counting classes, Fagin's theorem, Finite model theory, Skolem function
ASJC Scopus subject areas
- Mathematics(all)
- Logic
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Annals of Pure and Applied Logic, Vol. 170, No. 9, 09.2019, p. 1008-1029.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - A model-theoretic characterization of constant-depth arithmetic circuits
AU - Haak, Anselm
AU - Vollmer, Heribert
N1 - Funding information: This work was partially supported by DFG VO 630/8-1. We are grateful to Lauri Hella (Tampere) and Juha Kontinen (Helsinki) for helpful discussion, leading in particular to Definition 12. We also thank the anonymous referees for helpful comments.
PY - 2019/9
Y1 - 2019/9
N2 - We study the class #AC0 of functions computed by constant-depth polynomial-size arithmetic circuits of unbounded fan-in addition and multiplication gates. No model-theoretic characterization for arithmetic circuit classes is known so far. Inspired by Immerman's characterization of the Boolean circuit class AC0, we remedy this situation and develop such a characterization of #AC0. Our characterization can be interpreted as follows: Functions in #AC0 are exactly those functions counting winning strategies in first-order model checking games. A consequence of our results is a new model-theoretic characterization of TC0, the class of languages accepted by constant-depth polynomial-size majority circuits.
AB - We study the class #AC0 of functions computed by constant-depth polynomial-size arithmetic circuits of unbounded fan-in addition and multiplication gates. No model-theoretic characterization for arithmetic circuit classes is known so far. Inspired by Immerman's characterization of the Boolean circuit class AC0, we remedy this situation and develop such a characterization of #AC0. Our characterization can be interpreted as follows: Functions in #AC0 are exactly those functions counting winning strategies in first-order model checking games. A consequence of our results is a new model-theoretic characterization of TC0, the class of languages accepted by constant-depth polynomial-size majority circuits.
KW - Arithmetic circuits
KW - Counting classes
KW - Fagin's theorem
KW - Finite model theory
KW - Skolem function
UR - http://www.scopus.com/inward/record.url?scp=85064631918&partnerID=8YFLogxK
U2 - 10.48550/arXiv.1603.09531
DO - 10.48550/arXiv.1603.09531
M3 - Article
AN - SCOPUS:85064631918
VL - 170
SP - 1008
EP - 1029
JO - Annals of Pure and Applied Logic
JF - Annals of Pure and Applied Logic
SN - 0168-0072
IS - 9
ER -