- Home
- →
- Fakultäten
- →
- Fakultät für Elektrotechnik und Informatik
- →
- View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.
Original version
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
Repository version
To cite the version in the repository, please use this identifier:
https://doi.org/10.15488/1225
Files in this item
| 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.
|
|
| License of this version: | CC BY-NC-ND 3.0 Unported - https://creativecommons.org/licenses/by-nc-nd/3.0/ |
| Publication type: | Article |
| Publishing status: | publishedVersion |
| Publication date: | 2011 |
| Keywords english: | Counting hierarchy, Dependence logic, Descriptive complexity, Finite model theory, Majority quantifier, Second order logic, Counting hierarchy, Dependence logic, Descriptive complexity, Finite model theory, Majority quantifier, Second-order logic, Software engineering, Formal logic |
| DDC: | 004 | Informatik |
| Controlled keywords(GND): | Konferenzschrift |
This item appears in the following Collection(s):
-
Fakultät für Elektrotechnik und Informatik
Frei zugängliche Publikationen aus der Fakultät für Elektrotechnik und Informatik