Dependence logic with a majority quantifier

Show simple item record

dc.identifier.uri http://dx.doi.org/10.15488/1225
dc.identifier.uri http://www.repo.uni-hannover.de/handle/123456789/1250
dc.contributor.author Durand, Arnaud
dc.contributor.author Ebbing, Johannes
dc.contributor.author Kontinen, Juha
dc.contributor.author Vollmer, Heribert
dc.date.accessioned 2017-03-31T06:25:34Z
dc.date.available 2017-03-31T06:25:34Z
dc.date.issued 2011
dc.identifier.citation Durand, A.; Ebbing, Johannes; Kontinen, J.; Vollmer, Heribert: Dependence logic with a majority quantifier. In: Leibniz International Proceedings in Informatics, LIPIcs 13 (2011), S. 252-263. DOI: https://doi.org/10.4230/LIPIcs.FSTTCS.2011.252
dc.description.abstract We study the extension of dependence logic D by a majority quantifier M over finite structures. We show that the resulting logic is equi-expressive with the extension of second-order logic by second-order majority quantifiers of all arities. Our results imply that, from the point of view of descriptive complexity theory, D(M) captures the complexity class counting hierarchy. © A. Durand, J. Ebbing, J. Kontinen, and H. Vollmer. eng
dc.language.iso eng
dc.publisher Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
dc.relation.ispartof 31st International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011, December 12-14 2011, Mumbai, India
dc.relation.ispartofseries Leibniz International Proceedings in Informatics, LIPIcs 13 (2011)
dc.rights CC BY-NC-ND 3.0
dc.rights.uri https://creativecommons.org/licenses/by-nc-nd/3.0/
dc.subject Counting hierarchy eng
dc.subject Dependence logic eng
dc.subject Descriptive complexity eng
dc.subject Finite model theory eng
dc.subject Majority quantifier eng
dc.subject Second order logic eng
dc.subject Counting hierarchy eng
dc.subject Dependence logic eng
dc.subject Descriptive complexity eng
dc.subject Finite model theory eng
dc.subject Majority quantifier eng
dc.subject Second-order logic eng
dc.subject Software engineering eng
dc.subject Formal logic eng
dc.subject.ddc 100 | Philosophie ger
dc.title Dependence logic with a majority quantifier
dc.type article
dc.type conferenceObject
dc.type Text
dc.relation.issn 1868-8969
dc.relation.doi https://doi.org/10.4230/LIPIcs.FSTTCS.2011.252
dc.bibliographicCitation.volume 13
dc.bibliographicCitation.firstPage 252
dc.bibliographicCitation.lastPage 263
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


Browse

My Account

Usage Statistics