Details
| Originalsprache | Englisch |
|---|---|
| Seiten (von - bis) | 1008-1029 |
| Seitenumfang | 22 |
| Fachzeitschrift | Annals of Pure and Applied Logic |
| Jahrgang | 170 |
| Ausgabenummer | 9 |
| Frühes Online-Datum | 11 Apr. 2019 |
| Publikationsstatus | Veröffentlicht - 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.
ASJC Scopus Sachgebiete
- Mathematik (insg.)
- Logik
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
in: Annals of Pure and Applied Logic, Jahrgang 170, Nr. 9, 09.2019, S. 1008-1029.
Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › 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 -