Parameterized complexity of weighted team definability

verfasst von

Juha Kontinen, Yasir Mahmood, Arne Meier, Heribert Vollmer

Abstract

In this article, we study the complexity of weighted team definability for logics with team semantics. This problem is a natural analog of one of the most studied problems in parameterized complexity, the notion of weighted Fagin-definability, which is formulated in terms of satisfaction of first-order formulas with free relation variables. We focus on the parameterized complexity of weighted team definability for a fixed formula ϕ of central team-based logics. Given a first-order structure A and the parameter value k ∈ N as input, the question is to determine whether A, T |= ϕ for some team T of size k. We show several results on the complexity of this problem for dependence, independence, and inclusion logic formulas. Moreover, we also relate the complexity of weighted team definability to the complexity classes in the well-known W-hierarchy as well as paraNP.

Organisationseinheit(en)

Institut für Theoretische Informatik

Externe Organisation(en)

Universität Helsinki
Heinz Nixdorf Institut (HNI)
Universität Paderborn

Typ

Artikel

Journal

Mathematical Structures in Computer Science

Band

34

Seiten

375-389

Anzahl der Seiten

15

ISSN

0960-1295

Publikationsdatum

05.2024

Publikationsstatus

Veröffentlicht

Peer-reviewed

Ja

ASJC Scopus Sachgebiete

Mathematik (sonstige), Angewandte Informatik

Elektronische Version(en)

https://doi.org/10.48550/arXiv.2302.00541 (Zugang: Offen)
https://doi.org/10.1017/S0960129524000033 (Zugang: Offen)