Details
| Original language | English |
|---|---|
| Title of host publication | Computer Science Logic 2016, CSL 2016 |
| Editors | Jean-Marc Talbot, Laurent Regnier |
| ISBN (electronic) | 9783959770224 |
| Publication status | Published - 2016 |
Publication series
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 62 |
| ISSN (Print) | 1868-8969 |
Abstract
We introduce a new framework for a descriptive complexity approach to arithmetic computations. We define a hierarchy of classes based on the idea of counting assignments to free function variables in first-order formulae. We completely determine the inclusion structure and show that #P and #AC 0 appear as classes of this hierarchy. In this way, we unconditionally place #AC0 properly in a strict hierarchy of arithmetic classes within #P. We compare our classes with a hierarchy within #P defined in a model-theoretic way by Saluja et al. We argue that our approach is better suited to study arithmetic circuit classes such as #AC 0 which can be descriptively characterized as a class in our framework.
Keywords
- Arithmetic circuits, Counting classes, Fagin's theorem, Finite model theory, Skolem function
ASJC Scopus subject areas
- Computer Science(all)
- Software
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
Computer Science Logic 2016, CSL 2016. ed. / Jean-Marc Talbot; Laurent Regnier. 2016. (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 62).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › peer review
}
TY - GEN
T1 - Descriptive complexity of #AC0 functions
AU - Durand, A.
AU - Haak, A.
AU - Kontinen, J.
AU - Vollmer, H.
N1 - Publisher Copyright: © Arnaud Durand, Anselm Haak, Juha Kontinen, and Heribert Vollmer; licensed under Creative Commons License CC-BY.
PY - 2016
Y1 - 2016
N2 - We introduce a new framework for a descriptive complexity approach to arithmetic computations. We define a hierarchy of classes based on the idea of counting assignments to free function variables in first-order formulae. We completely determine the inclusion structure and show that #P and #AC 0 appear as classes of this hierarchy. In this way, we unconditionally place #AC0 properly in a strict hierarchy of arithmetic classes within #P. We compare our classes with a hierarchy within #P defined in a model-theoretic way by Saluja et al. We argue that our approach is better suited to study arithmetic circuit classes such as #AC 0 which can be descriptively characterized as a class in our framework.
AB - We introduce a new framework for a descriptive complexity approach to arithmetic computations. We define a hierarchy of classes based on the idea of counting assignments to free function variables in first-order formulae. We completely determine the inclusion structure and show that #P and #AC 0 appear as classes of this hierarchy. In this way, we unconditionally place #AC0 properly in a strict hierarchy of arithmetic classes within #P. We compare our classes with a hierarchy within #P defined in a model-theoretic way by Saluja et al. We argue that our approach is better suited to study arithmetic circuit classes such as #AC 0 which can be descriptively characterized as a class in our framework.
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=85012897496&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CSL.2016.20
DO - 10.4230/LIPIcs.CSL.2016.20
M3 - Conference contribution
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - Computer Science Logic 2016, CSL 2016
A2 - Talbot, Jean-Marc
A2 - Regnier, Laurent
ER -