{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T22:17:40Z","timestamp":1770070660758,"version":"3.49.0"},"reference-count":26,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2024,2,20]],"date-time":"2024-02-20T00:00:00Z","timestamp":1708387200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2024,5]]},"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>\n$\\varphi$\n<\/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>\n$\\mathcal{A}$\n<\/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>\n$k\\in \\mathbb N$\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>\n$\\mathcal{A},T\\models \\varphi$\n<\/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>","DOI":"10.1017\/s0960129524000033","type":"journal-article","created":{"date-parts":[[2024,2,20]],"date-time":"2024-02-20T09:29:51Z","timestamp":1708421391000},"page":"375-389","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Parameterized complexity of weighted team definability"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0115-5154","authenticated-orcid":false,"given":"Juha","family":"Kontinen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5651-5391","authenticated-orcid":false,"given":"Yasir","family":"Mahmood","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8061-5376","authenticated-orcid":false,"given":"Arne","family":"Meier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9292-1960","authenticated-orcid":false,"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2024,2,20]]},"reference":[{"key":"S0960129524000033_ref8","author":"Galliani","year":"2013"},{"key":"S0960129524000033_ref16","doi-asserted-by":"publisher","DOI":"10.1145\/3356043"},{"key":"S0960129524000033_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03182-7"},{"key":"S0960129524000033_ref14","doi-asserted-by":"publisher","DOI":"10.1145\/3157054"},{"key":"S0960129524000033_ref4","doi-asserted-by":"publisher","DOI":"10.1145\/3471618"},{"key":"S0960129524000033_ref6","author":"Flum","year":"2006"},{"key":"S0960129524000033_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-021-09730-w"},{"key":"S0960129524000033_ref21","unstructured":"Mahmood, Y. and Virtema, J. (2021). Parameterised complexity of propositional logic in team semantics. CoRR, abs\/2105.14887."},{"key":"S0960129524000033_ref2","doi-asserted-by":"crossref","unstructured":"Downey, R. G. , Fellows, M. R. and Regan, K. W. (1998). Descriptive Complexity and the W Hierarchy, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 39, AMS, 119\u2013134.","DOI":"10.1090\/dimacs\/039\/07"},{"key":"S0960129524000033_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s11225-013-9479-2"},{"key":"S0960129524000033_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2022.103163"},{"key":"S0960129524000033_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s10849-009-9082-0"},{"key":"S0960129524000033_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"S0960129524000033_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-90050-6_17"},{"key":"S0960129524000033_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-90050-6"},{"key":"S0960129524000033_ref11","unstructured":"Haak, A. , Kontinen, J. , M\u00fcller, F. , Vollmer, H. and Yang, F. (2019). Counting of teams in first-order team logics. In: MFCS, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, vol. 138, 19:1\u201319:15."},{"key":"S0960129524000033_ref10","doi-asserted-by":"publisher","DOI":"10.1145\/3531130.3533360"},{"key":"S0960129524000033_ref24","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511611193"},{"key":"S0960129524000033_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4"},{"key":"S0960129524000033_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2017.01.007"},{"key":"S0960129524000033_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2011.08.005"},{"key":"S0960129524000033_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/3373718.3394773"},{"key":"S0960129524000033_ref15","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exz008"},{"key":"S0960129524000033_ref19","article-title":"Canonical models and the complexity of modal team logic","volume":"15","author":"L\u00fcck","year":"2019","journal-title":"Logical Methods in Computer Science"},{"key":"S0960129524000033_ref17","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exac070"},{"key":"S0960129524000033_ref23","unstructured":"Papadimitriou, C. H. (1994). Computational Complexity, Addison-Wesley."}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129524000033","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,2]],"date-time":"2024-10-02T13:16:12Z","timestamp":1727874972000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129524000033\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,20]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["S0960129524000033"],"URL":"https:\/\/doi.org\/10.1017\/s0960129524000033","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,20]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}