Complexity Results in Team Semantics: Nonemptiness Is Not So Complex

Aleksi Anttila; Fan Yang; Juha Kontinen

arxiv: 2510.08122 · v2 · pith:MVE2BEIFnew · submitted 2025-10-09 · 💻 cs.LO · math.LO

Complexity Results in Team Semantics: Nonemptiness Is Not So Complex

Aleksi Anttila , Juha Kontinen , Fan Yang This is my paper

Pith reviewed 2026-05-25 08:14 UTC · model grok-4.3

classification 💻 cs.LO math.LO

keywords team semanticsnonemptiness atomsatisfiabilityvaliditymodel checkingpropositional logicconvexity

0 comments

The pith

Adding the nonemptiness atom to propositional logic yields NP-complete satisfiability and coNP-complete validity.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper begins the study of complexity for convex logics interpreted in team semantics. It examines classical propositional logic extended by the nonemptiness atom, which preserves convexity and union closure. The central results are that satisfiability is NP-complete, validity is coNP-complete, and model checking lies in P. A sympathetic reader would care because the results locate these decision problems in the same classes already known for ordinary propositional logic.

Core claim

The satisfiability problem for the extension of classical propositional logic with the nonemptiness atom NE is NP-complete, its validity problem is coNP-complete, and its model-checking problem is in P.

What carries the argument

The nonemptiness atom NE, which requires that every team of assignments is nonempty.

If this is right

Satisfiability and validity remain in NP and coNP even though formulas are evaluated over teams rather than single assignments.
Model checking can be performed by a deterministic polynomial-time procedure.
Convexity and union closure suffice to keep the three problems from moving into higher complexity classes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar complexity bounds may hold for other convex and union-closed extensions of propositional logic.
One could test whether dropping union closure while retaining convexity changes the complexity of model checking.

Load-bearing premise

The extension of classical propositional logic with the nonemptiness atom is both convex and union closed.

What would settle it

A polynomial-time algorithm for satisfiability of formulas containing NE, or a reduction showing satisfiability is PSPACE-complete, would refute the stated complexity results.

read the original abstract

We initiate the study of the complexity-theoretic properties of convex logics in team semantics. We focus on the extension of classical propositional logic with the nonemptiness atom NE, a logic known to be both convex and union closed. We show that the satisfiability problem for this logic is NP-complete, that its validity problem is coNP-complete, and that its model-checking problem is in P.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives the first NP/coNP/P classifications for satisfiability, validity, and model checking in the convex logic CPL+NE under team semantics.

read the letter

The main result is that satisfiability for classical propositional logic plus the nonemptiness atom is NP-complete in team semantics, validity is coNP-complete, and model checking sits in P. The authors position this as the start of complexity work on convex logics in that setting, and the bounds look like the first explicit ones for this extension. They adapt standard propositional reductions, which makes sense once convexity and union closure are granted as background facts. That transfer is the part that works cleanly here. The proofs appear to reuse familiar SAT-to-satisfiability and TAUT-to-validity patterns without new machinery, and model checking stays easy because teams can be checked without exponential blow-up. Credit for spotting that this particular logic is a good first target. The soft spot is modest and sits in the reliance on convexity and union closure being exactly as stated in the team-semantics literature. If those properties have any boundary cases with nonemptiness that the reductions miss, the classifications could need adjustment, but nothing in the argument structure suggests they do. The citation pattern is standard and points back to the relevant dependence-logic papers. No circular definitions or unfalsifiable steps show up. This is narrow work aimed at people already inside team semantics and dependence logic who track complexity. A reader outside that subfield will not find much to use, but inside it the classifications close a small open question. The paper is coherent on its own terms and deserves a serious referee to check the reduction details.

Referee Report

0 major / 2 minor

Summary. The manuscript initiates the study of complexity-theoretic properties of convex logics in team semantics. It focuses on the extension of classical propositional logic with the nonemptiness atom NE (CPL+NE), a logic known to be both convex and union closed. The central claims are that the satisfiability problem is NP-complete, the validity problem is coNP-complete, and the model-checking problem is in P.

Significance. If the results hold, they establish baseline complexity classifications for convex logics under team semantics and demonstrate that adding the NE atom does not increase complexity beyond that of classical propositional logic. The adaptation of standard propositional reductions while leveraging the known convexity and union-closure properties provides a clean foundation for future work on other convex team-based logics.

minor comments (2)

[Abstract] The abstract states the three complexity results without indicating the proof techniques or reduction strategies employed; adding one sentence on the high-level approach would improve accessibility.
The manuscript would benefit from an explicit statement of the team-semantics definitions for the connectives and the NE atom early in the paper to make the reductions self-contained.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive recommendation to accept the manuscript and for the accurate summary of our results on the complexity of CPL+NE under team semantics.

Circularity Check

0 steps flagged

No circularity in standard complexity classifications

full rationale

The paper establishes NP-completeness of satisfiability, coNP-completeness of validity, and P membership of model-checking for CPL+NE by adapting standard propositional reductions to team semantics. Convexity and union closure are invoked as known external properties of the logic rather than derived internally. No equations, fitted parameters, self-definitional steps, or load-bearing self-citations appear in the derivation chain; the results rest on independent reductions and do not reduce to their own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Only the abstract is available; no free parameters, invented entities, or non-standard axioms are mentioned. The work relies on the standard definition of team semantics and the convexity/union-closure property of the NE logic.

axioms (2)

standard math Classical propositional logic axioms and semantics
The logic is defined as an extension of classical propositional logic.
domain assumption Team semantics definition and convexity/union-closure of NE
Abstract states the logic with NE is convex and union closed.

pith-pipeline@v0.9.0 · 5584 in / 1241 out tokens · 48448 ms · 2026-05-25T08:14:06.159222+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages

[1]

The Bulletin of Symbolic Logic pp

Abramsky, S., Puljuj¨ arvi, J., V¨ a¨ an¨ anen, J.: Team semantics and independence notions in quantum physics. The Bulletin of Symbolic Logic pp. 1–58 (2025). https://doi.org/10.1017/bsl.2025.10089

work page doi:10.1017/bsl.2025.10089 2025
[2]

Albert, R., Gr¨ adel, E.: Unifying hidden-variable problems from quantum mechan- ics by logics of dependence and independence. Ann. Pure Appl. Logic173(10), Paper No. 103088 (2022).https://doi.org/https://doi.org/10.1016/j.apal. 2022.103088

work page doi:10.1016/j.apal 2022
[3]

Semantics and Pragmat- ics15(5) (2022).https://doi.org/10.3765/sp.15.5

Aloni, M.: Logic and conversation: the case of free choice. Semantics and Pragmat- ics15(5) (2022).https://doi.org/10.3765/sp.15.5

work page doi:10.3765/sp.15.5 2022
[4]

Notre Dame J

Aloni, M., Anttila, A., Yang, F.: State-based modal logics for free choice. Notre Dame J. Form. Log.65(4), 367–413 (2024).https://doi.org/10.1215/ 00294527-2024-0027

work page 2024
[5]

Anttila, A.: Further remarks on the dual negation in team logics (2024),https: //arxiv.org/abs/2410.07067

work page arXiv 2024
[6]

Anttila, A., Knudstorp, S.B.: Convex team logics (2025),https://arxiv.org/abs/ 2503.21850

work page arXiv 2025
[7]

Buss, S.R.: The Boolean formula value problem is in ALOGTIME. Proceedings of the nineteenth annual ACM symposium on Theory of computing (1987),https: //api.semanticscholar.org/CorpusID:6489222 Complexity Results in Team Semantics: Nonemptiness Is Not So Complex 11

work page 1987
[8]

Ciardelli, I.: Inquisitive Logic—Consequence and Inference in the Realm of Ques- tions, Trends in Logic—Studia Logica Library, vol. 60. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-09706-5

work page doi:10.1007/978-3-031-09706-5 2022
[9]

Ciardelli, I.: Inquisitive neighborhood logic (2024),https://arxiv.org/abs/2411. 04031

work page 2024
[10]

Oxford Univer- sity Press (2018).https://doi.org/10.1093/oso/9780198814788.001.0001

Ciardelli, I., Groenendijk, J., Roelofsen, F.: Inquisitive Semantics. Oxford Univer- sity Press (2018).https://doi.org/10.1093/oso/9780198814788.001.0001

work page doi:10.1093/oso/9780198814788.001.0001 2018
[11]

In: Proceedings of the Third Annual ACM Symposium

Cook, S.A.: The complexity of theorem proving procedures. In: Proceedings of the Third Annual ACM Symposium. pp. 151–158. ACM, New York (1971).https: //doi.org/10.1145/800157.805047

work page doi:10.1145/800157.805047 1971
[12]

Corander, J., Hyttinen, A., Kontinen, J., Pensar, J., V¨ a¨ an¨ anen, J.: A logical ap- proach to context-specific independence. Ann. Pure Appl. Logic170(9), 975–992 (2019).https://doi.org/10.1016/j.apal.2019.04.004

work page doi:10.1016/j.apal.2019.04.004 2019
[13]

In: Foundations of Information and Knowledge Systems

Durand, A., Hannula, M., Kontinen, J., Meier, A., Virtema, J.: Probabilistic team semantics. In: Foundations of Information and Knowledge Systems. pp. 186–206. Lecture Notes in Computer Science, Springer International Publishing (2018). https://doi.org/10.1007/978-3-319-90050-6_11

work page doi:10.1007/978-3-319-90050-6_11 2018
[14]

ACM Transactions on Computational Logic 23(1), 3:1–3:21 (2022).https://doi.org/10.1145/3471618

Durand, A., Kontinen, J., de Rugy-Altherre, N., V¨ a¨ an¨ anen, J.: Tractability frontier of data complexity in team semantics. ACM Transactions on Computational Logic 23(1), 3:1–3:21 (2022).https://doi.org/10.1145/3471618

work page doi:10.1145/3471618 2022
[15]

Durand, A., Kontinen, J., V¨ a¨ an¨ anen, J.: Modular SAT-based techniques for reason- ing tasks in team semantics. J. Comput. Syst. Sci.146, Paper No. 103575 (2024). https://doi.org/https://doi.org/10.1016/j.jcss.2024.103575

work page doi:10.1016/j.jcss.2024.103575 2024
[16]

In: Bielikov´ a, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Tur´ an, G

Ebbing, J., Lohmann, P.: Complexity of model checking for modal dependence logic. In: Bielikov´ a, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Tur´ an, G. (eds.) SOFSEM 2012: Theory and Practice of Computer Science. pp. 226–237. Springer Berlin Heidelberg, Berlin, Heidelberg (2012).https://doi.org/10.1007/ 978-3-642-27660-6_19

work page 2012
[17]

Galliani, P.: Inclusion and exclusion dependencies in team semantics — On some logics of imperfect information. Ann. Pure Appl. Logic163(1), 68–84 (2012), https://doi.org/10.1016/j.apal.2011.08.005

work page doi:10.1016/j.apal.2011.08.005 2012
[18]

Journal of Logic and Computation30(8), 1541–1566 (2020).https://doi.org/10.1093/logcom/ exaa048

Hannula, M., Kontinen, J., Virtema, J.: Polyteam semantics. Journal of Logic and Computation30(8), 1541–1566 (2020).https://doi.org/10.1093/logcom/ exaa048

work page doi:10.1093/logcom/ 2020
[19]

ACM Trans

Hannula, M., Kontinen, J., Virtema, J., Vollmer, H.: Complexity of propositional logics in team semantic. ACM Trans. Comput. Logic19(1) (Jan 2018).https: //doi.org/10.1145/3157054

work page doi:10.1145/3157054 2018
[20]

Linguistics and Philosophy44(2), 475–511 (2020).https://doi.org/10.1007/ s10988-020-09295-7

Hawke, P., Steinert-Threlkeld, S.: Semantic expressivism for epistemic modals. Linguistics and Philosophy44(2), 475–511 (2020).https://doi.org/10.1007/ s10988-020-09295-7

work page 2020
[21]

Journal of Logic and Computation29(5), 605–630 (2019).https://doi.org/10.1093/logcom/exz008

Hella, L., Kuusisto, A., Meier, A., Virtema, J.: Model checking and validity in propositional and modal inclusion logics. Journal of Logic and Computation29(5), 605–630 (2019).https://doi.org/10.1093/logcom/exz008

work page doi:10.1093/logcom/exz008 2019
[22]

ACM Trans

Hella, L., Kuusisto, A., Meier, A., Vollmer, H.: Satisfiability of modal inclusion logic: Lax and strict semantics. ACM Trans. Comput. Logic21(1) (2019).https: //doi.org/10.1145/3356043

work page doi:10.1145/3356043 2019
[23]

In: Advances in modal logic

Hella, L., Luosto, K., Sano, K., Virtema, J.: The expressive power of modal depen- dence logic. In: Advances in modal logic. Vol. 10, pp. 294–312. Coll. Publ., London (2014),http://www.aiml.net/volumes/volume10/Hella-Luosto-Sano-Virtema. pdf 12 A. Anttila et al

work page 2014
[24]

Mathemati- cal Structures in Computer Science34(5), 410–454 (2024).https://doi.org/10

Hella, L., Luosto, K., V¨ a¨ an¨ anen, J.: Dimension in team semantics. Mathemati- cal Structures in Computer Science34(5), 410–454 (2024).https://doi.org/10. 1017/S0960129524000021

work page 2024
[25]

Cambridge University Press, Cambridge (1996).https://doi.org/10.1017/CBO9780511624919

Hintikka, J.: The Principles of Mathematics Revisited. Cambridge University Press, Cambridge (1996).https://doi.org/10.1017/CBO9780511624919

work page doi:10.1017/cbo9780511624919 1996
[26]

In: Logic, methodology and philosophy of science, VIII (Moscow, 1987), Stud

Hintikka, J., Sandu, G.: Informational independence as a semantical phenomenon. In: Logic, methodology and philosophy of science, VIII (Moscow, 1987), Stud. Logic Found. Math., vol. 126, pp. 571–589. North-Holland, Amsterdam (1989). https://doi.org/10.1016/S0049-237X(08)70066-1

work page doi:10.1016/s0049-237x(08)70066-1 1987
[27]

ACM Trans

Hirvonen, M.: The implication problem for functional dependencies and variants of marginal distribution equivalences. ACM Trans. Comput. Log.25(4), 1–23 (2024). https://doi.org/10.1145/3677120

work page doi:10.1145/3677120 2024
[28]

Hodges, W.: Compositional semantics for a language of imperfect information. Log. J. IGPL5(4), 539–563 (1997).https://doi.org/10.1093/jigpal/5.4.539

work page doi:10.1093/jigpal/5.4.539 1997
[29]

In: Logic, Language, Information, and Computation

Kontinen, J., Link, S., V¨ a¨ an¨ anen, J.: Independence in database relations. In: Logic, Language, Information, and Computation. Lecture Notes in Computer Science, vol. 8071, pp. 179–193. Springer Berlin Heidelberg (2013).https://doi.org/10. 1007/978-3-642-39992-3_17

work page 2013
[30]

In: 24th EACSL Annual Conference on Computer Science Logic, LIPIcs

Kontinen, J., M¨ uller, J.S., Schnoor, H., Vollmer, H.: A van Benthem theorem for modal team semantics. In: 24th EACSL Annual Conference on Computer Science Logic, LIPIcs. Leibniz Int. Proc. Inform., vol. 41, pp. 277–291. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2015).https://doi.org/10.4230/LIPIcs.CSL. 2015.277

work page doi:10.4230/lipics.csl 2015
[31]

Problems of Information Transmission9, 115–116 (1973)

Levin, L.A.: Universal search problems [in Russian]. Problems of Information Transmission9, 115–116 (1973)

work page 1973
[32]

Lohmann, P., Vollmer, H.: Complexity results for modal dependence logic. Stud. Log.101(2), 343–366 (Apr 2013).https://doi.org/10.1007/s11225-013-9483-6

work page doi:10.1007/s11225-013-9483-6 2013
[33]

L¨ uck, M.: Team Logic: Axioms, Expressiveness, Complexity. Ph.D. thesis, Leibniz University Hannover (2020).https://doi.org/10.15488/9376

work page doi:10.15488/9376 2020
[34]

M¨ uller, J.S.: Satisfiability and Model Checking in Team Based Logics. Ph.D. thesis, Leibniz University Hannover (2014)

work page 2014
[35]

Informa- tion and Computation253, 224–236 (2017).https://doi.org/https://doi.org/ 10.1016/j.ic.2016.07.008

Virtema, J.: Complexity of validity for propositional dependence logics. Informa- tion and Computation253, 224–236 (2017).https://doi.org/https://doi.org/ 10.1016/j.ic.2016.07.008

work page doi:10.1016/j.ic.2016.07.008 2017
[36]

V¨ a¨ an¨ anen, J.: Dependence Logic: A New Approach to Independence Friendly Logic, London Mathematical Society Student Texts, vol. 70. Cambridge University Press, Cambridge (2007).https://doi.org/10.1017/CBO9780511611193

work page doi:10.1017/cbo9780511611193 2007
[37]

In: Interpreting G¨ odel, pp

V¨ a¨ an¨ anen, J.: Multiverse set theory and absolutely undecidable propositions. In: Interpreting G¨ odel, pp. 180–208. Cambridge Univ. Press, Cambridge (2014). https://doi.org/10.1017/CBO9780511756306.013

work page doi:10.1017/cbo9780511756306.013 2014
[38]

Yang, F.: Propositional union closed team logics. Ann. Pure Appl. Logic173(6), Paper No. 103102 (2022).https://doi.org/10.1016/j.apal.2022.103102

work page doi:10.1016/j.apal.2022.103102 2022
[39]

Yang, F., V¨ a¨ an¨ anen, J.: Propositional logics of dependence. Ann. Pure Appl. Logic 167(7), 557–589 (2016).https://doi.org/10.1016/j.apal.2016.03.003

work page doi:10.1016/j.apal.2016.03.003 2016
[40]

Yang, F., V¨ a¨ an¨ anen, J.: Propositional team logics. Ann. Pure Appl. Logic168(7), 1406–1441 (2017).https://doi.org/10.1016/j.apal.2017.01.007

work page doi:10.1016/j.apal.2017.01.007 2017

[1] [1]

The Bulletin of Symbolic Logic pp

Abramsky, S., Puljuj¨ arvi, J., V¨ a¨ an¨ anen, J.: Team semantics and independence notions in quantum physics. The Bulletin of Symbolic Logic pp. 1–58 (2025). https://doi.org/10.1017/bsl.2025.10089

work page doi:10.1017/bsl.2025.10089 2025

[2] [2]

Albert, R., Gr¨ adel, E.: Unifying hidden-variable problems from quantum mechan- ics by logics of dependence and independence. Ann. Pure Appl. Logic173(10), Paper No. 103088 (2022).https://doi.org/https://doi.org/10.1016/j.apal. 2022.103088

work page doi:10.1016/j.apal 2022

[3] [3]

Semantics and Pragmat- ics15(5) (2022).https://doi.org/10.3765/sp.15.5

Aloni, M.: Logic and conversation: the case of free choice. Semantics and Pragmat- ics15(5) (2022).https://doi.org/10.3765/sp.15.5

work page doi:10.3765/sp.15.5 2022

[4] [4]

Notre Dame J

Aloni, M., Anttila, A., Yang, F.: State-based modal logics for free choice. Notre Dame J. Form. Log.65(4), 367–413 (2024).https://doi.org/10.1215/ 00294527-2024-0027

work page 2024

[5] [5]

Anttila, A.: Further remarks on the dual negation in team logics (2024),https: //arxiv.org/abs/2410.07067

work page arXiv 2024

[6] [6]

Anttila, A., Knudstorp, S.B.: Convex team logics (2025),https://arxiv.org/abs/ 2503.21850

work page arXiv 2025

[7] [7]

Buss, S.R.: The Boolean formula value problem is in ALOGTIME. Proceedings of the nineteenth annual ACM symposium on Theory of computing (1987),https: //api.semanticscholar.org/CorpusID:6489222 Complexity Results in Team Semantics: Nonemptiness Is Not So Complex 11

work page 1987

[8] [8]

Ciardelli, I.: Inquisitive Logic—Consequence and Inference in the Realm of Ques- tions, Trends in Logic—Studia Logica Library, vol. 60. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-09706-5

work page doi:10.1007/978-3-031-09706-5 2022

[9] [9]

Ciardelli, I.: Inquisitive neighborhood logic (2024),https://arxiv.org/abs/2411. 04031

work page 2024

[10] [10]

Oxford Univer- sity Press (2018).https://doi.org/10.1093/oso/9780198814788.001.0001

Ciardelli, I., Groenendijk, J., Roelofsen, F.: Inquisitive Semantics. Oxford Univer- sity Press (2018).https://doi.org/10.1093/oso/9780198814788.001.0001

work page doi:10.1093/oso/9780198814788.001.0001 2018

[11] [11]

In: Proceedings of the Third Annual ACM Symposium

Cook, S.A.: The complexity of theorem proving procedures. In: Proceedings of the Third Annual ACM Symposium. pp. 151–158. ACM, New York (1971).https: //doi.org/10.1145/800157.805047

work page doi:10.1145/800157.805047 1971

[12] [12]

Corander, J., Hyttinen, A., Kontinen, J., Pensar, J., V¨ a¨ an¨ anen, J.: A logical ap- proach to context-specific independence. Ann. Pure Appl. Logic170(9), 975–992 (2019).https://doi.org/10.1016/j.apal.2019.04.004

work page doi:10.1016/j.apal.2019.04.004 2019

[13] [13]

In: Foundations of Information and Knowledge Systems

Durand, A., Hannula, M., Kontinen, J., Meier, A., Virtema, J.: Probabilistic team semantics. In: Foundations of Information and Knowledge Systems. pp. 186–206. Lecture Notes in Computer Science, Springer International Publishing (2018). https://doi.org/10.1007/978-3-319-90050-6_11

work page doi:10.1007/978-3-319-90050-6_11 2018

[14] [14]

ACM Transactions on Computational Logic 23(1), 3:1–3:21 (2022).https://doi.org/10.1145/3471618

Durand, A., Kontinen, J., de Rugy-Altherre, N., V¨ a¨ an¨ anen, J.: Tractability frontier of data complexity in team semantics. ACM Transactions on Computational Logic 23(1), 3:1–3:21 (2022).https://doi.org/10.1145/3471618

work page doi:10.1145/3471618 2022

[15] [15]

Durand, A., Kontinen, J., V¨ a¨ an¨ anen, J.: Modular SAT-based techniques for reason- ing tasks in team semantics. J. Comput. Syst. Sci.146, Paper No. 103575 (2024). https://doi.org/https://doi.org/10.1016/j.jcss.2024.103575

work page doi:10.1016/j.jcss.2024.103575 2024

[16] [16]

In: Bielikov´ a, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Tur´ an, G

Ebbing, J., Lohmann, P.: Complexity of model checking for modal dependence logic. In: Bielikov´ a, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Tur´ an, G. (eds.) SOFSEM 2012: Theory and Practice of Computer Science. pp. 226–237. Springer Berlin Heidelberg, Berlin, Heidelberg (2012).https://doi.org/10.1007/ 978-3-642-27660-6_19

work page 2012

[17] [17]

Galliani, P.: Inclusion and exclusion dependencies in team semantics — On some logics of imperfect information. Ann. Pure Appl. Logic163(1), 68–84 (2012), https://doi.org/10.1016/j.apal.2011.08.005

work page doi:10.1016/j.apal.2011.08.005 2012

[18] [18]

Journal of Logic and Computation30(8), 1541–1566 (2020).https://doi.org/10.1093/logcom/ exaa048

Hannula, M., Kontinen, J., Virtema, J.: Polyteam semantics. Journal of Logic and Computation30(8), 1541–1566 (2020).https://doi.org/10.1093/logcom/ exaa048

work page doi:10.1093/logcom/ 2020

[19] [19]

ACM Trans

Hannula, M., Kontinen, J., Virtema, J., Vollmer, H.: Complexity of propositional logics in team semantic. ACM Trans. Comput. Logic19(1) (Jan 2018).https: //doi.org/10.1145/3157054

work page doi:10.1145/3157054 2018

[20] [20]

Linguistics and Philosophy44(2), 475–511 (2020).https://doi.org/10.1007/ s10988-020-09295-7

Hawke, P., Steinert-Threlkeld, S.: Semantic expressivism for epistemic modals. Linguistics and Philosophy44(2), 475–511 (2020).https://doi.org/10.1007/ s10988-020-09295-7

work page 2020

[21] [21]

Journal of Logic and Computation29(5), 605–630 (2019).https://doi.org/10.1093/logcom/exz008

Hella, L., Kuusisto, A., Meier, A., Virtema, J.: Model checking and validity in propositional and modal inclusion logics. Journal of Logic and Computation29(5), 605–630 (2019).https://doi.org/10.1093/logcom/exz008

work page doi:10.1093/logcom/exz008 2019

[22] [22]

ACM Trans

Hella, L., Kuusisto, A., Meier, A., Vollmer, H.: Satisfiability of modal inclusion logic: Lax and strict semantics. ACM Trans. Comput. Logic21(1) (2019).https: //doi.org/10.1145/3356043

work page doi:10.1145/3356043 2019

[23] [23]

In: Advances in modal logic

Hella, L., Luosto, K., Sano, K., Virtema, J.: The expressive power of modal depen- dence logic. In: Advances in modal logic. Vol. 10, pp. 294–312. Coll. Publ., London (2014),http://www.aiml.net/volumes/volume10/Hella-Luosto-Sano-Virtema. pdf 12 A. Anttila et al

work page 2014

[24] [24]

Mathemati- cal Structures in Computer Science34(5), 410–454 (2024).https://doi.org/10

Hella, L., Luosto, K., V¨ a¨ an¨ anen, J.: Dimension in team semantics. Mathemati- cal Structures in Computer Science34(5), 410–454 (2024).https://doi.org/10. 1017/S0960129524000021

work page 2024

[25] [25]

Cambridge University Press, Cambridge (1996).https://doi.org/10.1017/CBO9780511624919

Hintikka, J.: The Principles of Mathematics Revisited. Cambridge University Press, Cambridge (1996).https://doi.org/10.1017/CBO9780511624919

work page doi:10.1017/cbo9780511624919 1996

[26] [26]

In: Logic, methodology and philosophy of science, VIII (Moscow, 1987), Stud

Hintikka, J., Sandu, G.: Informational independence as a semantical phenomenon. In: Logic, methodology and philosophy of science, VIII (Moscow, 1987), Stud. Logic Found. Math., vol. 126, pp. 571–589. North-Holland, Amsterdam (1989). https://doi.org/10.1016/S0049-237X(08)70066-1

work page doi:10.1016/s0049-237x(08)70066-1 1987

[27] [27]

ACM Trans

Hirvonen, M.: The implication problem for functional dependencies and variants of marginal distribution equivalences. ACM Trans. Comput. Log.25(4), 1–23 (2024). https://doi.org/10.1145/3677120

work page doi:10.1145/3677120 2024

[28] [28]

Hodges, W.: Compositional semantics for a language of imperfect information. Log. J. IGPL5(4), 539–563 (1997).https://doi.org/10.1093/jigpal/5.4.539

work page doi:10.1093/jigpal/5.4.539 1997

[29] [29]

In: Logic, Language, Information, and Computation

Kontinen, J., Link, S., V¨ a¨ an¨ anen, J.: Independence in database relations. In: Logic, Language, Information, and Computation. Lecture Notes in Computer Science, vol. 8071, pp. 179–193. Springer Berlin Heidelberg (2013).https://doi.org/10. 1007/978-3-642-39992-3_17

work page 2013

[30] [30]

In: 24th EACSL Annual Conference on Computer Science Logic, LIPIcs

Kontinen, J., M¨ uller, J.S., Schnoor, H., Vollmer, H.: A van Benthem theorem for modal team semantics. In: 24th EACSL Annual Conference on Computer Science Logic, LIPIcs. Leibniz Int. Proc. Inform., vol. 41, pp. 277–291. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2015).https://doi.org/10.4230/LIPIcs.CSL. 2015.277

work page doi:10.4230/lipics.csl 2015

[31] [31]

Problems of Information Transmission9, 115–116 (1973)

Levin, L.A.: Universal search problems [in Russian]. Problems of Information Transmission9, 115–116 (1973)

work page 1973

[32] [32]

Lohmann, P., Vollmer, H.: Complexity results for modal dependence logic. Stud. Log.101(2), 343–366 (Apr 2013).https://doi.org/10.1007/s11225-013-9483-6

work page doi:10.1007/s11225-013-9483-6 2013

[33] [33]

L¨ uck, M.: Team Logic: Axioms, Expressiveness, Complexity. Ph.D. thesis, Leibniz University Hannover (2020).https://doi.org/10.15488/9376

work page doi:10.15488/9376 2020

[34] [34]

M¨ uller, J.S.: Satisfiability and Model Checking in Team Based Logics. Ph.D. thesis, Leibniz University Hannover (2014)

work page 2014

[35] [35]

Informa- tion and Computation253, 224–236 (2017).https://doi.org/https://doi.org/ 10.1016/j.ic.2016.07.008

Virtema, J.: Complexity of validity for propositional dependence logics. Informa- tion and Computation253, 224–236 (2017).https://doi.org/https://doi.org/ 10.1016/j.ic.2016.07.008

work page doi:10.1016/j.ic.2016.07.008 2017

[36] [36]

V¨ a¨ an¨ anen, J.: Dependence Logic: A New Approach to Independence Friendly Logic, London Mathematical Society Student Texts, vol. 70. Cambridge University Press, Cambridge (2007).https://doi.org/10.1017/CBO9780511611193

work page doi:10.1017/cbo9780511611193 2007

[37] [37]

In: Interpreting G¨ odel, pp

V¨ a¨ an¨ anen, J.: Multiverse set theory and absolutely undecidable propositions. In: Interpreting G¨ odel, pp. 180–208. Cambridge Univ. Press, Cambridge (2014). https://doi.org/10.1017/CBO9780511756306.013

work page doi:10.1017/cbo9780511756306.013 2014

[38] [38]

Yang, F.: Propositional union closed team logics. Ann. Pure Appl. Logic173(6), Paper No. 103102 (2022).https://doi.org/10.1016/j.apal.2022.103102

work page doi:10.1016/j.apal.2022.103102 2022

[39] [39]

Yang, F., V¨ a¨ an¨ anen, J.: Propositional logics of dependence. Ann. Pure Appl. Logic 167(7), 557–589 (2016).https://doi.org/10.1016/j.apal.2016.03.003

work page doi:10.1016/j.apal.2016.03.003 2016

[40] [40]

Yang, F., V¨ a¨ an¨ anen, J.: Propositional team logics. Ann. Pure Appl. Logic168(7), 1406–1441 (2017).https://doi.org/10.1016/j.apal.2017.01.007

work page doi:10.1016/j.apal.2017.01.007 2017