A Parameterized View on the Complexity of Dependence Logic

Juha Kontinen, Arne Meier, Yasir Mahmood

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


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 languageEnglish
Title of host publicationLogical Foundations of Computer Science : International Symposium, LFCS 2022, Proceedings
EditorsSergei Artemov, Anil Nerode
Number of pages18
Place of PublicationCham
PublisherSpringer International Publishing
Publication date2022
ISBN (Print)978-3-030-93099-8
ISBN (Electronic)978-3-030-93100-1
Publication statusPublished - 2022
MoE publication typeA4 Article in conference proceedings
EventLogical Foundations of Computer Science - Deerfield Beach, United States
Duration: 10 Jan 202213 Jan 2022

Publication series

Name Lecture Notes in Computer Science
ISSN (Electronic)1611-3349

Fields of Science

  • 113 Computer and information sciences

Cite this