Parameterized complexity of weighted team definability
J. Kontinen, Y. Mahmood, A. Meier, H. Vollmer, Mathematical Structures in Computer Science 34 (2024) 375–389.
Download
No fulltext has been uploaded.
Journal Article
| Published
| English
Author
Kontinen, Juha;
Mahmood, YasirLibreCat;
Meier, Arne;
Vollmer, Heribert
Department
Abstract
<jats:title>Abstract</jats:title><jats:p>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 <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" xlink:href="S0960129524000033_inline1.png"/><jats:tex-math>
$\varphi$
</jats:tex-math></jats:alternatives></jats:inline-formula> of central team-based logics. Given a first-order structure <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" xlink:href="S0960129524000033_inline2.png"/><jats:tex-math>
$\mathcal{A}$
</jats:tex-math></jats:alternatives></jats:inline-formula> and the parameter value <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" xlink:href="S0960129524000033_inline3.png"/><jats:tex-math>
$k\in \mathbb N$
</jats:tex-math></jats:alternatives></jats:inline-formula> as input, the question is to determine whether <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" xlink:href="S0960129524000033_inline4.png"/><jats:tex-math>
$\mathcal{A},T\models \varphi$
</jats:tex-math></jats:alternatives></jats:inline-formula> for some team <jats:italic>T</jats:italic> of size <jats:italic>k</jats:italic>. 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.</jats:p>
Publishing Year
Journal Title
Mathematical Structures in Computer Science
Volume
34
Issue
5
Page
375-389
LibreCat-ID
Cite this
Kontinen J, Mahmood Y, Meier A, Vollmer H. Parameterized complexity of weighted team definability. Mathematical Structures in Computer Science. 2024;34(5):375-389. doi:10.1017/s0960129524000033
Kontinen, J., Mahmood, Y., Meier, A., & Vollmer, H. (2024). Parameterized complexity of weighted team definability. Mathematical Structures in Computer Science, 34(5), 375–389. https://doi.org/10.1017/s0960129524000033
@article{Kontinen_Mahmood_Meier_Vollmer_2024, title={Parameterized complexity of weighted team definability}, volume={34}, DOI={10.1017/s0960129524000033}, number={5}, journal={Mathematical Structures in Computer Science}, publisher={Cambridge University Press (CUP)}, author={Kontinen, Juha and Mahmood, Yasir and Meier, Arne and Vollmer, Heribert}, year={2024}, pages={375–389} }
Kontinen, Juha, Yasir Mahmood, Arne Meier, and Heribert Vollmer. “Parameterized Complexity of Weighted Team Definability.” Mathematical Structures in Computer Science 34, no. 5 (2024): 375–89. https://doi.org/10.1017/s0960129524000033.
J. Kontinen, Y. Mahmood, A. Meier, and H. Vollmer, “Parameterized complexity of weighted team definability,” Mathematical Structures in Computer Science, vol. 34, no. 5, pp. 375–389, 2024, doi: 10.1017/s0960129524000033.
Kontinen, Juha, et al. “Parameterized Complexity of Weighted Team Definability.” Mathematical Structures in Computer Science, vol. 34, no. 5, Cambridge University Press (CUP), 2024, pp. 375–89, doi:10.1017/s0960129524000033.
Google Scholar