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 : International Symposium, LFCS 2022, Proceedings |
| Editors | Sergei Artemov, Anil Nerode |
| Number of pages | 18 |
| Place of Publication | Cham |
| Publisher | Springer International Publishing |
| Publication date | 2022 |
| Pages | 125-142 |
| ISBN (Print) | 978-3-030-93099-8 |
| ISBN (Electronic) | 978-3-030-93100-1 |
| DOIs | |
| Publication status | Published - 2022 |
| MoE publication type | A4 Article in conference proceedings |
| Event | Logical Foundations of Computer Science - Deerfield Beach, United States Duration: 10 Jan 2022 → 13 Jan 2022 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer |
| Volume | 13137 |
| ISSN (Electronic) | 1611-3349 |
Fields of Science
- 113 Computer and information sciences