Details
| Original language | English |
|---|---|
| Title of host publication | LICS '18 |
| Subtitle of host publication | Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science |
| Place of Publication | New York |
| Publisher | Association for Computing Machinery (ACM) |
| Pages | 354-363 |
| Number of pages | 10 |
| ISBN (electronic) | 9781450355834 |
| Publication status | Published - 9 Jul 2018 |
| Event | 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018 - Oxford, United Kingdom (UK) Duration: 9 Jul 2018 → 12 Jul 2018 |
Publication series
| Name | Proceedings - Symposium on Logic in Computer Science |
|---|---|
| ISSN (Print) | 1043-6871 |
Abstract
In this paper we give a characterization of both Boolean and arithmetic circuit classes of logarithmic depth in the vein of descriptive complexity theory, i.e., the Boolean classes NC1, SAC1 and AC1 as well as their arithmetic counterparts #NC1, #SAC1 and #AC1. We build on Immerman's characterization of constant-depth polynomial-size circuits by formulae of first-order logic, i.e., AC0 = FO, and augment the logical language with an operator for defining relations in an inductive way. Considering slight variations of the new operator, we obtain uniform characterizations of the three just mentioned Boolean classes. The arithmetic classes can then be characterized by functions counting winning strategies in semantic games for formulae characterizing languages in the corresponding Boolean class.
Keywords
- Arithmetic circuits, Counting classes, Descriptive complexity, Finite model theory
ASJC Scopus subject areas
- Computer Science(all)
- Software
- Mathematics(all)
- General Mathematics
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
LICS '18: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science. New York: Association for Computing Machinery (ACM), 2018. p. 354-363 (Proceedings - Symposium on Logic in Computer Science).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › peer review
}
TY - GEN
T1 - Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth
AU - Durand, Arnaud
AU - Haak, Anselm
AU - Vollmer, Heribert
PY - 2018/7/9
Y1 - 2018/7/9
N2 - In this paper we give a characterization of both Boolean and arithmetic circuit classes of logarithmic depth in the vein of descriptive complexity theory, i.e., the Boolean classes NC1, SAC1 and AC1 as well as their arithmetic counterparts #NC1, #SAC1 and #AC1. We build on Immerman's characterization of constant-depth polynomial-size circuits by formulae of first-order logic, i.e., AC0 = FO, and augment the logical language with an operator for defining relations in an inductive way. Considering slight variations of the new operator, we obtain uniform characterizations of the three just mentioned Boolean classes. The arithmetic classes can then be characterized by functions counting winning strategies in semantic games for formulae characterizing languages in the corresponding Boolean class.
AB - In this paper we give a characterization of both Boolean and arithmetic circuit classes of logarithmic depth in the vein of descriptive complexity theory, i.e., the Boolean classes NC1, SAC1 and AC1 as well as their arithmetic counterparts #NC1, #SAC1 and #AC1. We build on Immerman's characterization of constant-depth polynomial-size circuits by formulae of first-order logic, i.e., AC0 = FO, and augment the logical language with an operator for defining relations in an inductive way. Considering slight variations of the new operator, we obtain uniform characterizations of the three just mentioned Boolean classes. The arithmetic classes can then be characterized by functions counting winning strategies in semantic games for formulae characterizing languages in the corresponding Boolean class.
KW - Arithmetic circuits
KW - Counting classes
KW - Descriptive complexity
KW - Finite model theory
UR - http://www.scopus.com/inward/record.url?scp=85051105270&partnerID=8YFLogxK
U2 - https://arxiv.org/pdf/1710.01934.pdf
DO - https://arxiv.org/pdf/1710.01934.pdf
M3 - Conference contribution
AN - SCOPUS:85051105270
T3 - Proceedings - Symposium on Logic in Computer Science
SP - 354
EP - 363
BT - LICS '18
PB - Association for Computing Machinery (ACM)
CY - New York
T2 - 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018
Y2 - 9 July 2018 through 12 July 2018
ER -