Details
| 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 |
| 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 |
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
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Computer Science(all)
- General Computer Science
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
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 - 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 -