Details
| Original language | English |
|---|---|
| Article number | 103163 |
| Journal | Annals of Pure and Applied Logic |
| Volume | 173 |
| Issue number | 10 |
| Early online date | 14 Jun 2022 |
| Publication status | Published - Dec 2022 |
Abstract
Keywords
- cs.LO, Enumeration problem, Polynomial delay, Team-based logics
ASJC Scopus subject areas
- Mathematics(all)
- Logic
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Annals of Pure and Applied Logic, Vol. 173, No. 10, 103163, 12.2022.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Enumerating teams in first-order team logics
AU - Haak, Anselm
AU - Meier, Arne
AU - Müller, Fabian
AU - Vollmer, Heribert
N1 - Funding information: Funded by the German Research Foundation (DFG), project ME4279/1-2. Arne Meier reports financial support was provided by German Research Foundation.
PY - 2022/12
Y1 - 2022/12
N2 - We start the study of the enumeration complexity of different satisfiability problems in first-order team logics. Since many of our problems go beyond DelP, we use a framework for hard enumeration analogous to the polynomial hierarchy, which was recently introduced by Creignou et al. (Discret. Appl. Math. 2019). We show that the problem to enumerate all satisfying teams of a fixed formula in a given first-order structure is DelNP-complete for certain formulas of dependence logic and independence logic. For inclusion logic formulas, this problem is even in DelP. Furthermore, we study the variants of this problems where only maximal, minimal, maximum and minimum solutions, respectively, are considered. For the most part these share the same complexity as the original problem. An exception is the minimum-variant for inclusion logic, which is DelNP-complete.
AB - We start the study of the enumeration complexity of different satisfiability problems in first-order team logics. Since many of our problems go beyond DelP, we use a framework for hard enumeration analogous to the polynomial hierarchy, which was recently introduced by Creignou et al. (Discret. Appl. Math. 2019). We show that the problem to enumerate all satisfying teams of a fixed formula in a given first-order structure is DelNP-complete for certain formulas of dependence logic and independence logic. For inclusion logic formulas, this problem is even in DelP. Furthermore, we study the variants of this problems where only maximal, minimal, maximum and minimum solutions, respectively, are considered. For the most part these share the same complexity as the original problem. An exception is the minimum-variant for inclusion logic, which is DelNP-complete.
KW - cs.LO
KW - Enumeration problem
KW - Polynomial delay
KW - Team-based logics
UR - http://www.scopus.com/inward/record.url?scp=85135033629&partnerID=8YFLogxK
U2 - 10.1016/j.apal.2022.103163
DO - 10.1016/j.apal.2022.103163
M3 - Article
VL - 173
JO - Annals of Pure and Applied Logic
JF - Annals of Pure and Applied Logic
SN - 0003-4843
IS - 10
M1 - 103163
ER -