Details
| Original language | English |
|---|---|
| Pages (from-to) | 1624-1644 |
| Number of pages | 21 |
| Journal | J. Log. Comput. |
| Volume | 32 |
| Issue number | 8 |
| Early online date | 14 Nov 2022 |
| Publication status | Published - Dec 2022 |
Abstract
In this paper, we investigate the parameterized complexity of model checking for Dependence and Independence logic, which are well studied logics 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
- Team semantics, dependence logic, independence logic, model checking, parameterized complexity
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Computer Science(all)
- Software
- Arts and Humanities(all)
- Arts and Humanities (miscellaneous)
- Computer Science(all)
- Hardware and Architecture
- Mathematics(all)
- Logic
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: J. Log. Comput., Vol. 32, No. 8, 12.2022, p. 1624-1644.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - A parameterized view on the complexity of dependence and independence logic
AU - Kontinen, Juha
AU - Meier, Arne
AU - Mahmood, Yasir
N1 - Funding Information: This research was funded by the German Research Foundation (DFG) [project ME4279/1-2], and the Academy of Finland [grants 308712 and 338259].
PY - 2022/12
Y1 - 2022/12
N2 - In this paper, we investigate the parameterized complexity of model checking for Dependence and Independence logic, which are well studied logics 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 and Independence logic, which are well studied logics 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 - Team semantics
KW - dependence logic
KW - independence logic
KW - model checking
KW - parameterized complexity
UR - http://www.scopus.com/inward/record.url?scp=85148428732&partnerID=8YFLogxK
U2 - 10.1093/logcom/exac070
DO - 10.1093/logcom/exac070
M3 - Article
VL - 32
SP - 1624
EP - 1644
JO - J. Log. Comput.
JF - J. Log. Comput.
SN - 1465-363X
IS - 8
ER -