{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T16:52:57Z","timestamp":1773939177592,"version":"3.50.1"},"reference-count":35,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"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>We introduce three measures of complexity for families of sets. Each of the three measures, which we call dimensions, is defined in terms of the minimal number of convex subfamilies that are needed for covering the given family. For upper dimension, the subfamilies are required to contain a unique maximal set, for dual upper dimension a unique minimal set, and for cylindrical dimension both a unique maximal and a unique minimal set. In addition to considering dimensions of particular families of sets, we study the behavior of dimensions under operators that map families of sets to new families of sets. We identify natural sufficient criteria for such operators to preserve the growth class of the dimensions. We apply the theory of our dimensions for proving new hierarchy results for logics with team semantics. To this end we associate each atom with a natural notion or arity. First, we show that the standard logical operators preserve the growth classes of the families arising from the semantics of formulas in such logics. Second, we show that the upper dimension of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129524000021_inline1.png\"\/><jats:tex-math>\n$k+1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-ary dependence, inclusion, independence, anonymity, and exclusion atoms is in a strictly higher growth class than that of any <jats:italic>k<\/jats:italic>-ary atoms, whence the <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129524000021_inline2.png\"\/><jats:tex-math>\n$k+1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-ary atoms are not definable in terms of any atoms of smaller arity.<\/jats:p>","DOI":"10.1017\/s0960129524000021","type":"journal-article","created":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T03:43:35Z","timestamp":1710215015000},"page":"410-454","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":3,"title":["Dimension in team semantics"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9117-8124","authenticated-orcid":false,"given":"Lauri","family":"Hella","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0007-3911-766X","authenticated-orcid":false,"given":"Kerkko","family":"Luosto","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4356-7974","authenticated-orcid":false,"given":"Jouko","family":"V\u00e4\u00e4n\u00e4nen","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2024,3,12]]},"reference":[{"key":"S0960129524000021_ref32","doi-asserted-by":"crossref","unstructured":"V\u00e4\u00e4n\u00e4nen, J. (2007). Dependence Logic, London Mathematical Society Student Texts, vol. 70, Cambridge University Press, Cambridge. ISBN 978-0-521-70015-3; 0-521-70015-9. doi: 10.1017\/CBO9780511611193. A new approach to independence friendly logic.","DOI":"10.1017\/CBO9780511611193"},{"key":"S0960129524000021_ref35","doi-asserted-by":"crossref","unstructured":"Venema, Y. (2007). Algebras and coalgebras. In: Handbook of Modal Logic, Stud. Log. Pract. Reason., vol. 3, Elsevier B. V., Amsterdam, 331\u2013426. ISBN 978-0-444-51690-9; 0-444-51690-5.","DOI":"10.1016\/S1570-2464(07)80009-7"},{"key":"S0960129524000021_ref24","first-page":"78","article-title":"An upper bound for the mean length of a disjunctive normal form","volume":"3","author":"Makarov","year":"1964","journal-title":"Diskretnyi Analiz"},{"key":"S0960129524000021_ref34","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2440-0","volume-title":"The Nature of Statistical Learning Theory","author":"Vapnik","year":"1995"},{"key":"S0960129524000021_ref7","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/s10849-012-9162-4","article-title":"Generalized quantifiers in dependence logic","volume":"21","author":"Engstr\u00f6m","year":"2012","journal-title":"Journal of Logic, Language and Information"},{"key":"S0960129524000021_ref19","unstructured":"Kuznetsov, S. E. (1983). A lower bound for the length of the shortest d.n.f. of almost all Boolean functions. In: Probabilistic Methods and Cybernetics, vol. 19, Kazan. Gos. Univ., Kazan\u2019, 44\u201347."},{"key":"S0960129524000021_ref22","unstructured":"L\u00fcck, M. (2020). Team Logic: Axioms, Expressiveness, Complexity. Phd thesis, University of Hanover, Hannover, Germany. URL https:\/\/www.repo.uni-hannover.de\/handle\/123456789\/9430."},{"key":"S0960129524000021_ref2","unstructured":"Aslanyan, L. A. (1983). Length of the shortest disjunctive normal form of weakly defined Boolean functions. In: Applied Mathematics, No. 2. Erevan. Univ., Erevan, 32\u201340, 141\u2013142."},{"key":"S0960129524000021_ref31","volume-title":"Cambridge Studies in Advanced Mathematics","volume":"132","author":"V\u00e4\u00e4n\u00e4nen","year":"2011"},{"key":"S0960129524000021_ref10","unstructured":"Galliani, P. , Hannula, M. and Kontinen, J. (2013). Hierarchies in independence logic. In: Rocca, S. R. D. (ed.) Computer Science Logic 2013 (CSL 2013), CSL 2013, September 2\u20135, 2013, Torino, Italy, LIPIcs, vol. 23, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 263\u2013280. doi: 10.4230\/LIPIcs.CSL.2013.263."},{"key":"S0960129524000021_ref21","article-title":"On the succinctness of atoms of dependency","volume":"15","author":"L\u00fcck","year":"2019","journal-title":"Logical Methods in Computer Science"},{"key":"S0960129524000021_ref9","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/s11225-013-9478-3","article-title":"Epistemic operators in dependence logic","volume":"101","author":"Galliani","year":"2013","journal-title":"Studia Logica"},{"key":"S0960129524000021_ref20","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1111\/j.1755-2567.1966.tb00600.x","article-title":"First order predicate logic with generalized quantifiers","volume":"32","author":"Lindstr\u00f6m","year":"1966","journal-title":"Theoria"},{"key":"S0960129524000021_ref8","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.apal.2011.08.005","article-title":"Inclusion and exclusion dependencies in team semantics\u2014on some logics of imperfect information","volume":"163","author":"Galliani","year":"2012","journal-title":"Annals of Pure and Applied Logic"},{"key":"S0960129524000021_ref14","doi-asserted-by":"crossref","first-page":"16:1","DOI":"10.1145\/3204521","article-title":"Hierarchies in inclusion logic with lax semantics","volume":"19","author":"Hannula","year":"2018","journal-title":"ACM Transactions on Computational Logic"},{"key":"S0960129524000021_ref3","unstructured":"Bollob\u00e1s, B. (1986). Combinatorics, Cambridge University Press, Cambridge. ISBN 0-521-33059-9; 0-521-33703-8. Set systems, hypergraphs, families of vectors and combinatorial probability."},{"key":"S0960129524000021_ref5","unstructured":"Ciardelli, I. (2009). Inquisitive Semantics and Intermediate Logics. Master\u2019s thesis, University of Amsterdam."},{"key":"S0960129524000021_ref33","doi-asserted-by":"crossref","first-page":"1078","DOI":"10.1093\/jigpal\/jzac074","article-title":"An atom\u2019s worth of anonymity","volume":"31","author":"V\u00e4\u00e4n\u00e4nen","year":"2023","journal-title":"Logic Journal of the IGPL"},{"key":"S0960129524000021_ref12","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/s11225-013-9479-2","article-title":"Dependence and independence","volume":"101","author":"Gr\u00e4del","year":"2013","journal-title":"Studia Logica"},{"key":"S0960129524000021_ref17","author":"Kleene","year":"1952"},{"key":"S0960129524000021_ref18","first-page":"1","article-title":"An upper estimate of the complexity of the shortest disjunctive normal forms of almost all Boolean functions","volume":"6","author":"Kor\u0161unov","year":"1969","journal-title":"Kibernetika (Kiev)"},{"key":"S0960129524000021_ref25","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139814782","volume-title":"Analysis of Boolean Functions","author":"O\u2019Donnell","year":"2014"},{"key":"S0960129524000021_ref26","doi-asserted-by":"crossref","first-page":"0","DOI":"10.1080\/00029890.1955.11988710","article-title":"A way to simplify truth functions","volume":"62","author":"Quine","year":"1955","journal-title":"The American Mathematical Monthly"},{"key":"S0960129524000021_ref11","first-page":"770","article-title":"An estimate of the complexity of the contracted normal form for almost all functions of the logic of algebra","volume":"158","author":"Glagolev","year":"1964","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0960129524000021_ref4","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B. (2001). Random Graphs, 2nd edn., Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge. ISBN 0-521-80920-7; 0-521-79722-5. doi: 10.1017\/CBO9780511814068.","DOI":"10.1017\/CBO9780511814068"},{"key":"S0960129524000021_ref6","doi-asserted-by":"crossref","unstructured":"Durand, A. and Kontinen, J. (2012). Hierarchies in dependence logic. ACM Transactions on Computational Logic 13 (4) Art. 31, 21. ISSN 1529-3785. doi: 10.1145\/2362355.2362359.","DOI":"10.1145\/2362355.2362359"},{"key":"S0960129524000021_ref15","unstructured":"Hella, L. , Luosto, K. , Sano, K. and Virtema, J. (2014). The expressive power of modal dependence logic. In: Advances in Modal Logic, vol. 10, Colloquium Publications, London, 294\u2013312."},{"key":"S0960129524000021_ref1","doi-asserted-by":"crossref","unstructured":"Abramsky, S. and V\u00e4\u00e4n\u00e4nen, J. (2009). From IF to BI: a tale of dependence and separation. Synthese 167 (2, Knowledge, Rationality & Action) 207\u2013230. ISSN 0039-7857. doi: 10.1007\/s11229-008-9415-6.","DOI":"10.1007\/s11229-008-9415-6"},{"key":"S0960129524000021_ref13","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0168-0072(95)00072-0","article-title":"Arity hierarchies","volume":"82","author":"Grohe","year":"1996","journal-title":"Annals of Pure and Applied Logic"},{"key":"S0960129524000021_ref29","unstructured":"Weber, K. (1982). The length of random Boolean functions. Elektron. Informationsverarb. Kybernet. 18 (12) 659\u2013668. ISSN 0013-5712."},{"key":"S0960129524000021_ref16","doi-asserted-by":"crossref","unstructured":"Hella, L. and Stumpf, J. (2015). The expressive power of modal logic with inclusion atoms. In: Proceedings Sixth International Symposium on Games, Automata, Logics and Formal Verification, vol. 193, Electronic Proceedings in Theoretical Computer Science (EPTCS), EPTCS, [place of publication not identified], 129\u2013143. doi: 10.4204\/EPTCS.193.10.","DOI":"10.4204\/EPTCS.193.10"},{"key":"S0960129524000021_ref27","first-page":"88","article-title":"Estimate of the length of the shortest disjunctive normal form for the negation of the characteristic function of a Hamming code","volume":"39","author":"Romanov","year":"1983","journal-title":"Metody Diskret. Analiz."},{"key":"S0960129524000021_ref23","volume-title":"London Mathematical Society Lecture Note Series","volume":"386","author":"Mann","year":"2011"},{"key":"S0960129524000021_ref28","unstructured":"R\u00f6nnholm, R. (2018). Arity Fralments of Logics with Team Semantics (URN:ISBN:978-952-03-0912-1). Phd thesis, University of Tampere."},{"key":"S0960129524000021_ref30","unstructured":"Wilke, R. (2022). Reasoning about Dependence and Independence: Teams and Multiteams. Phd thesis, RWTH Aachen University, Germany. URL https:\/\/publications.rwth-aachen.de\/record\/842872."}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129524000021","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,2]],"date-time":"2024-10-02T13:16:14Z","timestamp":1727874974000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129524000021\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":35,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["S0960129524000021"],"URL":"https:\/\/doi.org\/10.1017\/s0960129524000021","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]},"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"}}]}}