### Abstract

Original language | English |
---|---|

Title of host publication | Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) |

Publication date | Aug 2019 |

Publication status | Published - Aug 2019 |

MoE publication type | A4 Article in conference proceedings |

Event | The 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) - Aachen, Germany Duration: 26 Aug 2019 → 31 Aug 2019 https://tcs.rwth-aachen.de/mfcs2019/ |

### Fields of Science

- cs.LO
- cs.CC

### Cite this

*Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)*

}

*Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019).*The 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), Aachen, Germany, 26/08/2019.

**Counting of Teams in First-Order Team Logics.** / Haak, Anselm; Kontinen, Juha; Müller, Fabian; Vollmer, Heribert; Yang, Fan.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Counting of Teams in First-Order Team Logics

AU - Haak, Anselm

AU - Kontinen, Juha

AU - Müller, Fabian

AU - Vollmer, Heribert

AU - Yang, Fan

PY - 2019/8

Y1 - 2019/8

N2 - 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.

AB - 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.

KW - cs.LO

KW - cs.CC

M3 - Conference contribution

BT - Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

ER -