Canonical models and the complexity of modal team logic

Show simple item record

dc.identifier.uri http://dx.doi.org/10.15488/4218
dc.identifier.uri https://www.repo.uni-hannover.de/handle/123456789/4252
dc.contributor.author Lück, Martin
dc.date.accessioned 2018-12-19T11:04:41Z
dc.date.available 2018-12-19T11:04:41Z
dc.date.issued 2018
dc.identifier.citation Lück, M.: Canonical models and the complexity of modal team logic. In: Leibniz International Proceedings in Informatics, LIPIcs 119 (2018), 30. DOI: https://doi.org/10.4230/LIPIcs.CSL.2018.30
dc.description.abstract We study modal team logic MTL, the team-semantical extension of classical modal logic closed under Boolean negation. Its fragments, such as modal dependence, independence, and inclusion logic, are well-understood. However, due to the unrestricted Boolean negation, the satisfiability problem of full MTL has been notoriously resistant to a complexity theoretical classification. In our approach, we adapt the notion of canonical models for team semantics. By construction of such a model, we reduce the satisfiability problem of MTL to simple model checking. Afterwards, we show that this method is optimal in the sense that MTL-formulas can efficiently enforce canonicity. Furthermore, to capture these results in terms of computational complexity, we introduce a non-elementary complexity class, TOWER(poly), and prove that the satisfiability and validity problem of MTL are complete for it. We also show that the fragments of MTL with bounded modal depth are complete for the levels of the elementary hierarchy (with polynomially many alternations). eng
dc.language.iso eng
dc.publisher Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
dc.relation.ispartofseries Leibniz International Proceedings in Informatics, LIPIcs 119 (2018)
dc.rights CC BY 4.0 Unported
dc.rights.uri https://creativecommons.org/licenses/by/4.0/
dc.subject Complexity eng
dc.subject Modal logic eng
dc.subject Satisfiability eng
dc.subject Team semantics eng
dc.subject Computational complexity eng
dc.subject Linearization eng
dc.subject Model checking eng
dc.subject Semantics eng
dc.subject Canonical models eng
dc.subject Classical modal logic eng
dc.subject Complexity eng
dc.subject Complexity class eng
dc.subject Modal logic eng
dc.subject Satisfiability eng
dc.subject Satisfiability problems eng
dc.subject Simple modeling eng
dc.subject Computer circuits eng
dc.subject.ddc 004 | Informatik ger
dc.title Canonical models and the complexity of modal team logic eng
dc.type article
dc.type conferenceObject
dc.type Text
dc.relation.issn 18688969
dc.relation.doi https://doi.org/10.4230/LIPIcs.CSL.2018.30
dc.bibliographicCitation.volume 119
dc.bibliographicCitation.firstPage 30
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