dc.identifier.uri |
http://dx.doi.org/10.15488/1948 |
|
dc.identifier.uri |
http://www.repo.uni-hannover.de/handle/123456789/1973 |
|
dc.contributor.author |
Durand, Arnaud
|
|
dc.contributor.author |
Haak, Anselm
|
|
dc.contributor.author |
Kontinen, Juha
|
|
dc.contributor.author |
Vollmer, Heribert
|
|
dc.date.accessioned |
2017-09-22T12:52:57Z |
|
dc.date.available |
2017-09-22T12:52:57Z |
|
dc.date.issued |
2016 |
|
dc.identifier.citation |
Durand, A.; Haak, A.; Kontinen, J.; Vollmer, H.: Descriptive complexity of #AC0 functions. In: Leibniz International Proceedings in Informatics, LIPIcs 62 (2016). DOI: https://doi.org/10.4230/LIPIcs.CSL.2016.20 |
|
dc.description.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 #AC0 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 #AC0 which can be descriptively characterized as a class in our framework. |
eng |
dc.language.iso |
eng |
|
dc.publisher |
Saarbrücken : Dagstuhl Publishing |
|
dc.relation.ispartofseries |
Leibniz International Proceedings in Informatics, LIPIcs 62 (2016) |
|
dc.rights |
CC BY 3.0 Unported |
|
dc.rights.uri |
https://creativecommons.org/licenses/by/3.0 |
|
dc.subject |
Arithmetic circuits |
eng |
dc.subject |
Counting classes |
eng |
dc.subject |
Fagin's theorem |
eng |
dc.subject |
Finite model theory |
eng |
dc.subject |
Skolem function |
eng |
dc.subject |
Computational complexity |
eng |
dc.subject |
Logic circuits |
eng |
dc.subject |
Arithmetic circuit |
eng |
dc.subject |
Arithmetic computations |
eng |
dc.subject |
Counting class |
eng |
dc.subject |
Descriptive complexity |
eng |
dc.subject |
Fagin's theorem |
eng |
dc.subject |
Finite model theory |
eng |
dc.subject |
Function variables |
eng |
dc.subject |
Inclusion structure |
eng |
dc.subject |
Computer circuits |
eng |
dc.subject.classification |
Konferenzschrift |
ger |
dc.subject.ddc |
004 | Informatik
|
ger |
dc.subject.ddc |
510 | Mathematik
|
ger |
dc.title |
Descriptive complexity of #AC0 functions |
eng |
dc.type |
Article |
|
dc.type |
Text |
|
dc.relation.issn |
18688969 |
|
dc.relation.doi |
https://doi.org/10.4230/LIPIcs.CSL.2016.20 |
|
dc.bibliographicCitation.volume |
62 |
|
dc.description.version |
publishedVersion |
|
tib.accessRights |
frei zug�nglich |
|