On the complexity of team logic and its two-variable fragment

Download statistics - Document (COUNTER):

Lück, M.: On the complexity of team logic and its two-variable fragment. In: Leibniz International Proceedings in Informatics, LIPIcs 117 (2018), 27. DOI: https://doi.org/10.4230/LIPIcs.MFCS.2018.27

Repository version

To cite the version in the repository, please use this identifier: https://doi.org/10.15488/4219

Selected time period:


Sum total of downloads: 36

We study the logic FO(∼), the extension of first-order logic with team semantics by unrestricted Boolean negation. It was recently shown to be axiomatizable, but otherwise has not yet received much attention in questions of computational complexity. In this paper, we consider its two-variable fragment FO2(∼) and prove that its satisfiability problem is decidable, and in fact complete for the recently introduced non-elementary class TOWER(poly). Moreover, we classify the complexity of model checking of FO(∼) with respect to the number of variables and the quantifier rank, and prove a dichotomy between PSPACE- and ATIME-ALT(exp, poly)-complete fragments. For the lower bounds, we propose a translation from modal team logic MTL to FO2(∼) that extends the well-known standard translation from modal logic ML to FO2. For the upper bounds, we translate FO(∼) to fragments of second-order logic with PSPACE-complete and ATIME-ALT(exp, poly)-complete model checking, respectively.
License of this version: CC BY 4.0 Unported
Document Type: article
Publishing status: publishedVersion
Issue Date: 2018
Appears in Collections:Fakultät für Elektrotechnik und Informatik

distribution of downloads over the selected time period:

downloads by country:

pos. country downloads
total perc.
1 image of flag of Germany Germany 31 86.11%
2 image of flag of Hungary Hungary 2 5.56%
3 image of flag of United States United States 1 2.78%
4 image of flag of Latvia Latvia 1 2.78%
5 image of flag of Canada Canada 1 2.78%

Further download figures and rankings:


Zur Erhebung der Downloadstatistiken kommen entsprechend dem „COUNTER Code of Practice for e-Resources“ international anerkannte Regeln und Normen zur Anwendung. COUNTER ist eine internationale Non-Profit-Organisation, in der Bibliotheksverbände, Datenbankanbieter und Verlage gemeinsam an Standards zur Erhebung, Speicherung und Verarbeitung von Nutzungsdaten elektronischer Ressourcen arbeiten, welche so Objektivität und Vergleichbarkeit gewährleisten sollen. Es werden hierbei ausschließlich Zugriffe auf die entsprechenden Volltexte ausgewertet, keine Aufrufe der Website an sich.

Search the repository