Show simple item record

dc.identifier.uri Durand, Arnaud Haak, Anselm Kontinen, Juha Vollmer, Heribert 2017-09-22T12:52:57Z 2017-09-22T12:52:57Z 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:
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
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.ddc 004 | Informatik ger
dc.subject.ddc 510 | Mathematik ger
dc.title Descriptive complexity of #AC0 functions
dc.type article
dc.type conferenceObject
dc.type Text
dc.relation.issn 18688969
dc.bibliographicCitation.volume 62
dc.description.version publishedVersion
tib.accessRights frei zug�nglich

Files in this item

This item appears in the following Collection(s):

Show simple item record


Search the repository


My Account

Usage Statistics