Decidability of predicate logics with team semantics

Zur Kurzanzeige

dc.identifier.uri http://dx.doi.org/10.15488/1949
dc.identifier.uri http://www.repo.uni-hannover.de/handle/123456789/1974
dc.contributor.author Kontinen, Juha
dc.contributor.author Kuusisto, Antti
dc.contributor.author Virtema, Jonni
dc.date.accessioned 2017-09-22T12:52:57Z
dc.date.available 2017-09-22T12:52:57Z
dc.date.issued 2016
dc.identifier.citation Kontinen, J.; Kuusisto, A.; Virtema, J.: Decidability of predicate logics with team semantics. In: Leibniz International Proceedings in Informatics, LIPIcs 58 (2016), No. 60. DOI: https://doi.org/10.4230/LIPIcs.MFCS.2016.60
dc.description.abstract We study the complexity of predicate logics based on team semantics. We show that the satisfiability problems of two-variable independence logic and inclusion logic are both NEXPTIMEcomplete. Furthermore, we show that the validity problem of two-variable dependence logic is undecidable, thereby solving an open problem from the team semantics literature. We also briefly analyse the complexity of the Bernays-Schönfinkel-Ramsey prefix classes of dependence logic. eng
dc.description.sponsorship Academy of Finland
dc.description.sponsorship ERC/647289
dc.description.sponsorship Jenny and Antti Wihuri Foundation
dc.description.sponsorship Vilho, Yrjö and Kalle Väisälä Foundation
dc.language.iso eng
dc.publisher Saarbrücken : Dagstuhl Publishing
dc.relation.ispartofseries Leibniz International Proceedings in Informatics, LIPIcs 58 (2016)
dc.rights CC BY 3.0 Unported
dc.rights.uri https://creativecommons.org/licenses/by/3.0
dc.subject Complexity eng
dc.subject Dependence logic eng
dc.subject Team semantics eng
dc.subject Two-variable logic eng
dc.subject Formal logic eng
dc.subject Problem solving eng
dc.subject Semantics eng
dc.subject Complexity eng
dc.subject Dependence logic eng
dc.subject Predicate logic eng
dc.subject Satisfiability problems eng
dc.subject Two-variable logic eng
dc.subject Computer circuits eng
dc.subject.classification Konferenzschrift ger
dc.subject.ddc 004 | Informatik ger
dc.subject.ddc 510 | Mathematik ger
dc.title Decidability of predicate logics with team semantics eng
dc.type Article
dc.type Text
dc.relation.issn 18688969
dc.relation.doi https://doi.org/10.4230/LIPIcs.MFCS.2016.60
dc.bibliographicCitation.volume 58
dc.bibliographicCitation.firstPage 60
dc.description.version publishedVersion
tib.accessRights frei zug�nglich


Thumbnail
Name: Kontinen et al 2017, ...
Größe: 548.7Kb
Format: PDF
Öffnen

Die Publikation erscheint in Sammlung(en):

Zur Kurzanzeige

 

Suche im Repositorium


Durchblättern

Mein Nutzer/innenkonto

Nutzungsstatistiken