Parameterized complexity of weighted team definability

authored by

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.

Organisation(s)

Institute of Theoretical Computer Science

External Organisation(s)

University of Helsinki
Heinz Nixdorf Institute
Paderborn University

Type

Article

Journal

Mathematical Structures in Computer Science

Volume

34

Pages

375-389

No. of pages

15

ISSN

0960-1295

Publication date

05.2024

Publication status

Published

Peer reviewed

Yes

ASJC Scopus subject areas

Mathematics (miscellaneous), Computer Science Applications

Electronic version(s)

https://doi.org/10.48550/arXiv.2302.00541 (Access: Open)
https://doi.org/10.1017/S0960129524000033 (Access: Open)