Details
| Originalsprache | Englisch |
|---|---|
| Titel des Sammelwerks | LICS '18 |
| Untertitel | Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science |
| Erscheinungsort | New York |
| Herausgeber (Verlag) | Association for Computing Machinery (ACM) |
| Seiten | 354-363 |
| Seitenumfang | 10 |
| ISBN (elektronisch) | 9781450355834 |
| Publikationsstatus | Veröffentlicht - 9 Juli 2018 |
| Veranstaltung | 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018 - Oxford, Großbritannien / Vereinigtes Königreich Dauer: 9 Juli 2018 → 12 Juli 2018 |
Publikationsreihe
| 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.
ASJC Scopus Sachgebiete
- Informatik (insg.)
- Software
- Mathematik (insg.)
- Allgemeine Mathematik
Zitieren
- 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. S. 354-363 (Proceedings - Symposium on Logic in Computer Science).
Publikation: Beitrag in Buch/Bericht/Sammelwerk/Konferenzband › Aufsatz in Konferenzband › Forschung › 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 -