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^*

^*Corresponding author for this work

Institute of Theoretical Computer Science

University of Helsinki

Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › 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.

Original language	English
Title of host publication	Logical Foundations of Computer Science
Subtitle of host publication	International Symposium, LFCS 2022, Deerfield Beach, FL, USA, January 10-13, 2022, Proceedings.
Editors	Sergei Artemov, Anil Nerode
Place of Publication	Cham
Pages	125-142
Number of pages	18
ISBN (Electronic)	978-3-030-93100-1
DOIs	https://doi.org/10.1007/978-3-030-93100-1_9
Publication status	Published - 2022
Event	International Symposium on Logical Foundations of Computer Science, LFCS 2020 - Deerfield Beach, United States Duration: 4 Jan 2020 → 7 Jan 2020

Publication series

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

Conference

Conference	International Symposium on Logical Foundations of Computer Science, LFCS 2020
Country/Territory	United States
City	Deerfield Beach
Period	4 Jan 2020 → 7 Jan 2020

Keywords

Dependence logic
Model checking
Parameterized complexity
Team semantics

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

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

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

Cite this

Kontinen, J., Meier, A., & Mahmood, Y. (2022). A Parameterized View on the Complexity of Dependence Logic. In S. Artemov, & A. Nerode (Eds.), Logical Foundations of Computer Science: International Symposium, LFCS 2022, Deerfield Beach, FL, USA, January 10-13, 2022, Proceedings. (pp. 125-142). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 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.. editor / Sergei Artemov ; Anil Nerode. Cham, 2022. pp. 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 (eds), 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), vol. 13137 LNCS, Cham, pp. 125-142, International Symposium on Logical Foundations of Computer Science, LFCS 2020, Deerfield Beach, United States, 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.. ed. / Sergei Artemov; Anil Nerode. Cham, 2022. p. 125-142 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13137 LNCS).

Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › 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 - https://www.scopus.com/pages/publications/85122029991

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, editors, Logical Foundations of Computer Science: International Symposium, LFCS 2022, Deerfield Beach, FL, USA, January 10-13, 2022, Proceedings.. Cham. 2022. p. 125-142. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2021 Dec 16. doi: 10.1007/978-3-030-93100-1_9

A Parameterized View on the Complexity of Dependence Logic.

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Nonclassical logics: parametrised and enumeration complexity

Cite this

A Parameterized View on the Complexity of Dependence Logic.

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Projects

Nonclassical logics: parametrised and enumeration complexity

Cite this