Details
| Originalsprache | Englisch |
|---|---|
| Titel des Sammelwerks | Logic, Language, Information, and Computation |
| Untertitel | 23rd International Workshop, WoLLIC 2016, Puebla, Mexico, August 16-19th, 2016. Proceedings |
| Herausgeber/-innen | Jouko Väänänen, Åsa Hirvonen, Ruy de Queiroz |
| Erscheinungsort | Berlin |
| Herausgeber (Verlag) | Springer Verlag |
| Seiten | 234-248 |
| Seitenumfang | 15 |
| ISBN (elektronisch) | 978-3-662-52921-8 |
| ISBN (Print) | 9783662529201 |
| Publikationsstatus | Veröffentlicht - 6 Aug. 2016 |
Publikationsreihe
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Band | 9803 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (elektronisch) | 1611-3349 |
Abstract
We study the class #AC 0 of functions computed by constantdepth 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 class AC 0, we remedy this situation and develop such a characterization of #AC 0. Our characterization can be interpreted as follows: Functions in #AC 0 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 TC 0, the class of languages accepted by constant-depth polynomial-size majority circuits.
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
Logic, Language, Information, and Computation: 23rd International Workshop, WoLLIC 2016, Puebla, Mexico, August 16-19th, 2016. Proceedings. Hrsg. / Jouko Väänänen; Åsa Hirvonen; Ruy de Queiroz. Berlin: Springer Verlag, 2016. S. 234-248 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 9803 LNCS).
Publikation: Beitrag in Buch/Bericht/Sammelwerk/Konferenzband › Aufsatz in Konferenzband › Forschung › Peer-Review
}
TY - GEN
T1 - A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits
AU - Haak, Anselm
AU - Vollmer, Heribert
N1 - Funding Information: Supported by DFG grant VO 630/8-1.
PY - 2016/8/6
Y1 - 2016/8/6
N2 - We study the class #AC 0 of functions computed by constantdepth 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 class AC 0, we remedy this situation and develop such a characterization of #AC 0. Our characterization can be interpreted as follows: Functions in #AC 0 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 TC 0, the class of languages accepted by constant-depth polynomial-size majority circuits.
AB - We study the class #AC 0 of functions computed by constantdepth 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 class AC 0, we remedy this situation and develop such a characterization of #AC 0. Our characterization can be interpreted as follows: Functions in #AC 0 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 TC 0, the class of languages accepted by constant-depth polynomial-size majority circuits.
UR - http://www.scopus.com/inward/record.url?scp=84981526539&partnerID=8YFLogxK
U2 - 10.48550/arXiv.1603.09531
DO - 10.48550/arXiv.1603.09531
M3 - Conference contribution
SN - 9783662529201
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 234
EP - 248
BT - Logic, Language, Information, and Computation
A2 - Väänänen, Jouko
A2 - Hirvonen, Åsa
A2 - de Queiroz, Ruy
PB - Springer Verlag
CY - Berlin
ER -