论文标题
列举一阶团队逻辑的团队
Enumerating Teams in First-Order Team Logics
论文作者
论文摘要
我们开始研究一阶团队逻辑中不同可满足问题的枚举复杂性。由于我们的许多问题超出了DELP，因此我们使用一个类似于多项式层次结构的框架来进行硬枚举，这是Creignou等人最近引入的。 （Dipt。Appl。Math。2019）。我们表明，在给定的一阶结构中列举所有固定公式的所有满足团队的问题对于依赖逻辑和独立逻辑的某些公式而言是Delnp complete。对于包含逻辑公式，此问题甚至在DELP中。此外，我们研究了这种问题的变体，在这些问题中，仅考虑最大，最小，最大和最小解决方案。在大多数情况下，它们具有与原始问题相同的复杂性。一个例外是包含逻辑的最小变化，该逻辑是Delnp完整的。
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.
