Details
| Original language | English |
|---|---|
| Title of host publication | Logic, Language, Information, and Computation |
| Subtitle of host publication | 23rd International Workshop, WoLLIC 2016, Puebla, Mexico, August 16-19th, 2016. Proceedings |
| Editors | Jouko Väänänen, Åsa Hirvonen, Ruy de Queiroz |
| Place of Publication | Berlin |
| Publisher | Springer Verlag |
| Pages | 234-248 |
| Number of pages | 15 |
| ISBN (electronic) | 978-3-662-52921-8 |
| ISBN (print) | 9783662529201 |
| Publication status | Published - 6 Aug 2016 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 9803 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (electronic) | 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.
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
Logic, Language, Information, and Computation: 23rd International Workshop, WoLLIC 2016, Puebla, Mexico, August 16-19th, 2016. Proceedings. ed. / Jouko Väänänen; Åsa Hirvonen; Ruy de Queiroz. Berlin: Springer Verlag, 2016. p. 234-248 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9803 LNCS).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › 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 -