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.ispartofseries |
Leibniz International Proceedings in Informatics, LIPIcs 13 (2011) |
|
dc.rights |
CC BY-NC-ND 3.0 Unported |
|
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.classification |
Konferenzschrift |
ger |
dc.subject.ddc |
004 | Informatik
|
ger |
dc.title |
Dependence logic with a majority quantifier |
eng |
dc.type |
Article |
|
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.date |
|
|
dc.bibliographicCitation.firstPage |
252 |
|
dc.bibliographicCitation.lastPage |
263 |
|
dc.description.version |
publishedVersion |
|
tib.accessRights |
frei zug�nglich |
|