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 -