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.
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a \(k\)-tree. SIAM J. Algebraic Discrete Meth. (1987). https://doi.org/10.1137/0608024
Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybern., 11(1–2), 1–21 (1993). https://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3417
Bodlaender, H.L.: Discovering treewidth. In: SOFSEM, vol. 3381 of Lecture Notes in Computer Science, pp. 1–16. Springer (2005). https://doi.org/10.1007/978-3-540-30577-4_1
Fundamentals of Parameterized Complexity. TCS. Springer, London (2013). https://doi.org/10.1007/978-1-4471-5559-1
Durand, A., Kontinen, J.: Hierarchies in dependence logic. ACM Trans. Comput. Logic (TOCL) 13(4), 31 (2012). https://doi.org/10.1145/2362355.2362359
Ebbinghaus, H.D., Flum, J.: Finite model theory. In: Perspectives in Mathematical Logic. Springer (1995). 978-3-540-60149-4, https://doi.org/10.1007/978-3-662-03182-7
Elberfeld, M., Stockhusen, C., Tantau, T.: On the space and circuit complexity of parameterized problems: classes and completeness. Algorithmica 71(3), 661–701 (2014). https://doi.org/10.1007/s00453-014-9944-y
Parameterized Complexity Theory. TTCSAES. Springer, Heidelberg (2006). https://doi.org/10.1007/3-540-29953-X
Galliani, P.: Inclusion and exclusion dependencies in team semantics: on some logics of imperfect information. Ann. Pure Appl. Logic 163(1), 68–84 (2012). https://doi.org/10.1016/j.apal.2011.08.005
Galliani, P.: On strongly first-order dependencies. In: Dependence Logic, pp. 53–71. Springer (2016). https://doi.org/10.1007/978-3-319-31803-5_4
Galliani, P., Hella, L.: Inclusion logic and fixed point logic. In: Rocca, S.R.D. (ed.) Computer science logic 2013 (CSL 2013), vol. 23 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 281–295, Dagstuhl, Germany, 2013. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.CSL.2013.281
Grädel, E.: Model-checking games for logics of imperfect information. Theor. Comput. Sci. 493, 2–14 (2013). https://doi.org/10.1016/j.tcs.2012.10.033
Grädel, E., Väänänen, J.: Dependence and independence. Studia Logica 101(2), 399–410 (2013). https://doi.org/10.1007/s11225-013-9479-2
Hannula, M., Kontinen, J., Bussche, J.V., Virtema, J.: Descriptive complexity of real computation and probabilistic independence logic. In: LICS, pp. 550–563. ACM (2020). https://doi.org/10.1145/3373718.3394773
Hannula, M., Kontinen, J., Virtema, J., Vollmer, H.: Complexity of propositional logics in team semantic. ACM Trans. Comput. Log. 19(1), 2:1–2:14 (2018). https://doi.org/10.1145/3157054
Kontinen, J.: Coherence and computational complexity of quantifier-free dependence logic formulas. Studia Logica 101(2), 267–291 (2013). https://doi.org/10.1007/s11225-013-9481-8
Libkin, L.: Elements of finite model theory. In: Texts in Theoretical Computer Science. An EATCS Series. Springer (2004). https://doi.org/10.1007/978-3-662-07003-1
Lohmann, P., Vollmer, H.: Complexity results for modal dependence logic. Stud. Logica 101(2), 343–366 (2013). https://doi.org/10.1007/s11225-013-9483-6
Lück, M.: Canonical models and the complexity of modal team logic. Log. Methods Comput. Sci. 15(2) (2019). https://doi.org/10.23638/LMCS-15(2:2)2019
Mahmood, Y., Meier, A.: Parameterised complexity of model checking and satisfiability in propositional dependence logic. In: Foundations of Information and Knowledge Systems - 11th International Symposium, FoIKS 2020, 17–21 February 2020, Dortmund, Germany, Proceedings, pp. 157–174 (2020). https://doi.org/10.1007/978-3-030-39951-1_10
Mahmood, Y., Virtema, J.: Parameterised complexity of propositional logic in team semantics. CoRR. arXiv: 2105.14887
Martin, B.: First-order model checking problems parameterized by the model. In: CiE, volume 5028 of Lecture Notes in Computer Science, pp. 417–427. Springer (2008). https://doi.org/10.1007/978-3-540-69407-6_45
Meier, A., Reinbold, C.: Enumeration complexity of poor man’s propositional dependence logic. In: FoIKS, volume 10833 of Lecture Notes in Computer Science, pp. 303–321. Springer (2018). https://doi.org/10.1007/978-3-319-90050-6_17
Papadimitriou, C.H.: Computational Complexity (1994). 978-0-201-53082-7 25
Robertson, N., Seymour, P.D.: Graph minors. III. planar tree-width. J. Comb. Theory Ser. B 36(1), 49–64 (1984). https://doi.org/10.1016/0095-8956(84)90013-3
Samer, M., Szeider, S.: Fixed-parameter tractability. In: Handbook of Satisfiability, volume 185 of Frontiers in Artificial Intelligence and Applications, pp. 425–454. IOS Press (2009). https://doi.org/10.3233/978-1-58603-929-5-425
Väänänen, J.A.: Dependence Logic - A New Approach to Independence Friendly Logic, volume 70 of London Mathematical Society student texts. Cambridge University Press (2007). 978-0-521-70015-3
Virtema, J.: Approaches to Finite Variable Dependence: Expressiveness and Computational Complexity. PhD thesis, School of Information Sciences of the University of Tampere (2014). 978-951-44-9472-7
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Kontinen, J., Meier, A., Mahmood, Y. (2022). A Parameterized View on the Complexity of Dependence Logic. In: Artemov, S., Nerode, A. (eds) Logical Foundations of Computer Science. LFCS 2022. Lecture Notes in Computer Science(), vol 13137. Springer, Cham. https://doi.org/10.1007/978-3-030-93100-1_9
Download citation
DOI: https://doi.org/10.1007/978-3-030-93100-1_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-93099-8
Online ISBN: 978-3-030-93100-1
eBook Packages: Computer ScienceComputer Science (R0)