A Parameterized View on the Complexity of Dependence Logic.

Juha Kontinen; Arne Meier; Yasir Mahmood

doi:10.1007/978-3-030-93100-1_9

A Parameterized View on the Complexity of Dependence Logic.

Juha Kontinen, Arne Meier, Yasir Mahmood^*

^*Korrespondierende*r Autor*in für diese Arbeit

Institut für Theoretische Informatik

Universität Helsinki

Publikation: Beitrag in Buch/Bericht/Sammelwerk/Konferenzband › Aufsatz in Konferenzband › Forschung › Peer-Review

Abstract

In this paper, we investigate the parameterized complexity of model checking for Dependence Logic which is a well studied logic in the area of Team Semantics. We start with a list of nine immediate parameterizations for this problem, namely: the number of disjunctions (i.e., splits)/(free) variables/universal quantifiers, formula-size, the tree-width of the Gaifman graph of the input structure, the size of the universe/team, and the arity of dependence atoms. We present a comprehensive picture of the parameterized complexity of model checking and obtain a division of the problem into tractable and various intractable degrees. Furthermore, we also consider the complexity of the most important variants (data and expression complexity) of the model checking problem by fixing parts of the input.

Originalsprache	Englisch
Titel des Sammelwerks	Logical Foundations of Computer Science
Untertitel	International Symposium, LFCS 2022, Deerfield Beach, FL, USA, January 10-13, 2022, Proceedings.
Herausgeber/-innen	Sergei Artemov, Anil Nerode
Erscheinungsort	Cham
Seiten	125-142
Seitenumfang	18
ISBN (elektronisch)	978-3-030-93100-1
DOIs	https://doi.org/10.1007/978-3-030-93100-1_9
Publikationsstatus	Veröffentlicht - 2022
Veranstaltung	International Symposium on Logical Foundations of Computer Science, LFCS 2020 - Deerfield Beach, USA / Vereinigte Staaten Dauer: 4 Jan. 2020 → 7 Jan. 2020

Publikationsreihe

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Band	13137 LNCS
ISSN (Print)	0302-9743
ISSN (elektronisch)	1611-3349

Konferenz

Konferenz	International Symposium on Logical Foundations of Computer Science, LFCS 2020
Land/Gebiet	USA / Vereinigte Staaten
Ort	Deerfield Beach
Zeitraum	4 Jan. 2020 → 7 Jan. 2020

ASJC Scopus Sachgebiete

Theoretische Informatik
Allgemeine Computerwissenschaft

Zugriff auf Dokument

10.1007/978-3-030-93100-1_9

https://arxiv.org/abs/2109.09342Lizenz: Arxiv nonexclusive-distrib 1.0

Andere Dateien und Links

Verknüpfung zur Publikation in Scopus

Nichtklassische Logiken: Parametrisierte Komplexität und Enumeration
Meier, A. (Projektleiter*in (Principal Investigator)), Mahmood, Y. (Projektmitarbeiter*in) & Schindler, I. (Projektmitarbeiter*in)
1 Okt. 2013 → 31 Juli 2022
Projekt: Forschung

Dieses zitieren

Kontinen, J., Meier, A., & Mahmood, Y. (2022). A Parameterized View on the Complexity of Dependence Logic. in S. Artemov, & A. Nerode (Hrsg.), Logical Foundations of Computer Science: International Symposium, LFCS 2022, Deerfield Beach, FL, USA, January 10-13, 2022, Proceedings. (S. 125-142). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 13137 LNCS).. https://doi.org/10.1007/978-3-030-93100-1_9

Kontinen, Juha ; Meier, Arne ; Mahmood, Yasir. / A Parameterized View on the Complexity of Dependence Logic. Logical Foundations of Computer Science: International Symposium, LFCS 2022, Deerfield Beach, FL, USA, January 10-13, 2022, Proceedings.. Hrsg. / Sergei Artemov ; Anil Nerode. Cham, 2022. S. 125-142 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b3856d30d0f34ca2aca0cc8377491f30,

title = "A Parameterized View on the Complexity of Dependence Logic.",

abstract = "In this paper, we investigate the parameterized complexity of model checking for Dependence Logic which is a well studied logic in the area of Team Semantics. We start with a list of nine immediate parameterizations for this problem, namely: the number of disjunctions (i.e., splits)/(free) variables/universal quantifiers, formula-size, the tree-width of the Gaifman graph of the input structure, the size of the universe/team, and the arity of dependence atoms. We present a comprehensive picture of the parameterized complexity of model checking and obtain a division of the problem into tractable and various intractable degrees. Furthermore, we also consider the complexity of the most important variants (data and expression complexity) of the model checking problem by fixing parts of the input.",

keywords = "Dependence logic, Model checking, Parameterized complexity, Team semantics",

author = "Juha Kontinen and Arne Meier and Yasir Mahmood",

note = "Funding Information: First author funded by grants 308712 and 338259 of the Academy of Finland. Second and third authors funded by German Research Foundation (DFG), project ME 4279/ 1-2.; International Symposium on Logical Foundations of Computer Science, LFCS 2020 ; Conference date: 04-01-2020 Through 07-01-2020",

year = "2022",

doi = "10.1007/978-3-030-93100-1_9",

language = "English",

isbn = "978-3-030-93099-8",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "125--142",

editor = "Sergei Artemov and Anil Nerode",

booktitle = "Logical Foundations of Computer Science",

}

Kontinen, J, Meier, A & Mahmood, Y 2022, A Parameterized View on the Complexity of Dependence Logic. in S Artemov & A Nerode (Hrsg.), Logical Foundations of Computer Science: International Symposium, LFCS 2022, Deerfield Beach, FL, USA, January 10-13, 2022, Proceedings.. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bd. 13137 LNCS, Cham, S. 125-142, International Symposium on Logical Foundations of Computer Science, LFCS 2020, Deerfield Beach, USA / Vereinigte Staaten, 4 Jan. 2020. https://doi.org/10.1007/978-3-030-93100-1_9

A Parameterized View on the Complexity of Dependence Logic. / Kontinen, Juha; Meier, Arne; Mahmood, Yasir.
Logical Foundations of Computer Science: International Symposium, LFCS 2022, Deerfield Beach, FL, USA, January 10-13, 2022, Proceedings.. Hrsg. / Sergei Artemov; Anil Nerode. Cham, 2022. S. 125-142 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 13137 LNCS).

Publikation: Beitrag in Buch/Bericht/Sammelwerk/Konferenzband › Aufsatz in Konferenzband › Forschung › Peer-Review

TY - GEN

T1 - A Parameterized View on the Complexity of Dependence Logic.

AU - Kontinen, Juha

AU - Meier, Arne

AU - Mahmood, Yasir

N1 - Funding Information: First author funded by grants 308712 and 338259 of the Academy of Finland. Second and third authors funded by German Research Foundation (DFG), project ME 4279/ 1-2.

PY - 2022

Y1 - 2022

N2 - In this paper, we investigate the parameterized complexity of model checking for Dependence Logic which is a well studied logic in the area of Team Semantics. We start with a list of nine immediate parameterizations for this problem, namely: the number of disjunctions (i.e., splits)/(free) variables/universal quantifiers, formula-size, the tree-width of the Gaifman graph of the input structure, the size of the universe/team, and the arity of dependence atoms. We present a comprehensive picture of the parameterized complexity of model checking and obtain a division of the problem into tractable and various intractable degrees. Furthermore, we also consider the complexity of the most important variants (data and expression complexity) of the model checking problem by fixing parts of the input.

AB - In this paper, we investigate the parameterized complexity of model checking for Dependence Logic which is a well studied logic in the area of Team Semantics. We start with a list of nine immediate parameterizations for this problem, namely: the number of disjunctions (i.e., splits)/(free) variables/universal quantifiers, formula-size, the tree-width of the Gaifman graph of the input structure, the size of the universe/team, and the arity of dependence atoms. We present a comprehensive picture of the parameterized complexity of model checking and obtain a division of the problem into tractable and various intractable degrees. Furthermore, we also consider the complexity of the most important variants (data and expression complexity) of the model checking problem by fixing parts of the input.

KW - Dependence logic

KW - Model checking

KW - Parameterized complexity

KW - Team semantics

UR - http://www.scopus.com/inward/record.url?scp=85122029991&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-93100-1_9

DO - 10.1007/978-3-030-93100-1_9

M3 - Conference contribution

SN - 978-3-030-93099-8

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 125

EP - 142

BT - Logical Foundations of Computer Science

A2 - Artemov, Sergei

A2 - Nerode, Anil

CY - Cham

T2 - International Symposium on Logical Foundations of Computer Science, LFCS 2020

Y2 - 4 January 2020 through 7 January 2020

ER -

Kontinen J, Meier A, Mahmood Y. A Parameterized View on the Complexity of Dependence Logic. in Artemov S, Nerode A, Hrsg., Logical Foundations of Computer Science: International Symposium, LFCS 2022, Deerfield Beach, FL, USA, January 10-13, 2022, Proceedings.. Cham. 2022. S. 125-142. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2021 Dez 16. doi: 10.1007/978-3-030-93100-1_9

A Parameterized View on the Complexity of Dependence Logic.

Abstract

Publikationsreihe

Konferenz

ASJC Scopus Sachgebiete

Zugriff auf Dokument

Andere Dateien und Links

Projekte

Nichtklassische Logiken: Parametrisierte Komplexität und Enumeration

Dieses zitieren