Counting of Teams in First-Order Team Logics

Anselm Haak, Juha Kontinen, Fabian Müller, Heribert Vollmer, Fan Yang

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

Abstract

We study descriptive complexity of counting complexity classes in the range from $\#$P to $\#\cdot$NP. A corollary of Fagin's characterization of NP by existential second-order logic is that $\#$P can be logically described as the class of functions counting satisfying assignments to free relation variables in first-order formulae. In this paper we extend this study to classes beyond $\#$P and extensions of first-order logic with team semantics. These team-based logics are closely related to existential second-order logic and its fragments, hence our results also shed light on the complexity of counting for extensions of FO in Tarski's semantics. Our results show that the class $\#\cdot$NP can be logically characterized by independence logic and existential second-order logic, whereas dependence logic and inclusion logic give rise to subclasses of $\#\cdot$NP and $\#$P , respectively. Our main technical result shows that the problem of counting satisfying assignments for monotone Boolean $\Sigma_1$-formulae is $\#\cdot$NP-complete as well as complete for the function class generated by dependence logic.
Original languageEnglish
Title of host publication44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
EditorsPeter Rossmanith, Pinar Heggernes, Joost-Pieter Katoen
Number of pages15
Volume138
Publication dateAug 2019
Pages19:1-19:15
ISBN (Electronic)978-3-95977-117-7
DOIs
Publication statusPublished - Aug 2019
MoE publication typeA4 Article in conference proceedings
EventThe 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) - Aachen, Germany
Duration: 26 Aug 201931 Aug 2019
https://tcs.rwth-aachen.de/mfcs2019/

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherDagstuhl Publishing
Volume138
ISSN (Electronic)1868-8969

Fields of Science

  • cs.LO
  • cs.CC
  • 111 Mathematics

Cite this

Haak, A., Kontinen, J., Müller, F., Vollmer, H., & Yang, F. (2019). Counting of Teams in First-Order Team Logics. In P. Rossmanith, P. Heggernes, & J-P. Katoen (Eds.), 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) (Vol. 138, pp. 19:1-19:15). (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 138). https://doi.org/10.4230/LIPIcs.MFCS.2019.19