Details
| Originalsprache | Englisch |
|---|---|
| Seiten (von - bis) | 1624-1644 |
| Seitenumfang | 21 |
| Fachzeitschrift | J. Log. Comput. |
| Jahrgang | 32 |
| Ausgabenummer | 8 |
| Frühes Online-Datum | 14 Nov. 2022 |
| Publikationsstatus | Veröffentlicht - Dez. 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.
ASJC Scopus Sachgebiete
- Mathematik (insg.)
- Theoretische Informatik
- Informatik (insg.)
- Software
- Geisteswissenschaftliche Fächer (insg.)
- Geisteswissenschaftliche Fächer (sonstige)
- Informatik (insg.)
- Hardware und Architektur
- Mathematik (insg.)
- Logik
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
in: J. Log. Comput., Jahrgang 32, Nr. 8, 12.2022, S. 1624-1644.
Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › 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 -