{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,16]],"date-time":"2026-09-16T08:36:25Z","timestamp":1789547785255,"version":"build-2803163510"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,1,14]],"date-time":"2022-01-14T00:00:00Z","timestamp":1642118400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DFG","award":["RTG 2236"],"award-info":[{"award-number":["RTG 2236"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2022,4,30]]},"abstract":"<jats:p>Team semantics is the mathematical basis of modern logics of dependence and independence. In contrast to classical Tarski semantics, a formula is evaluated not for a single assignment of values to the free variables, but on a set of such assignments, called a team. Team semantics is appropriate for a purely logical understanding of dependency notions, where only the presence or absence of data matters, but being based on sets, it does not take into account multiple occurrences of data values. It is therefore insufficient in scenarios where such multiplicities matter, in particular for reasoning about probabilities and statistical independencies. Therefore, an extension from teams to multiteams (i.e.\u00a0multisets of assignments) has been proposed by several authors.<\/jats:p>\n          <jats:p>In this paper we aim at a systematic development of logics of dependence and independence based on multiteam semantics. We study atomic dependency properties of finite multiteams and discuss the appropriate meaning of logical operators to extend the atomic dependencies to full-fledged logics for reasoning about dependence properties in a multiteam setting. We explore properties and expressive power of a wide spectrum of different multiteam logics and compare them to second-order logic and to logics with team semantics. In many cases the results resemble what is known in team semantics, but there are also interesting differences. While in team semantics, the combination of inclusion and exclusion dependencies leads to a logic with the full power of both independence logic and existential second-order logic, independence properties of multiteams are not definable by any combination of properties that are downwards closed or union closed and thus are strictly more powerful than inclusion-exclusion logic. We also study the relationship of logics with multiteam semantics with existential second-order logic for a specific class of metafinite structures. It turns out that inclusion-exclusion logic can be characterised in a precise sense by the Presburger fragment of this logic, but for capturing independence, we need to go beyond it and add some form of multiplication. Finally, we also consider multiteams with weights in the reals and study the expressive power of formulae by means of topological properties.<\/jats:p>","DOI":"10.1145\/3487579","type":"journal-article","created":{"date-parts":[[2022,1,14]],"date-time":"2022-01-14T12:02:07Z","timestamp":1642161727000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Logics with Multiteam Semantics"],"prefix":"10.1145","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8950-9991","authenticated-orcid":false,"given":"Erich","family":"Gr\u00e4del","sequence":"first","affiliation":[{"name":"Mathematical Foundations of Computer Science, RWTH Aachen University, Ahornstrasse, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Wilke","sequence":"additional","affiliation":[{"name":"Mathematical Foundations of Computer Science, RWTH Aachen University, Ahornstrasse, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,1,14]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/2994186"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/153850.153856"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-017-9568-4"},{"key":"e_1_3_1_5_2","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1007\/978-3-319-90050-6_11","volume-title":"Foundations of Information and Knowledge Systems","author":"Durand A.","year":"2018","unstructured":"A. Durand, M. Hannula, J. Kontinen, A. Meier, and J. Virtema. 2018. Probabilistic team semantics. In Foundations of Information and Knowledge Systems. Springer, 186\u2013206."},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2011.08.005"},{"key":"e_1_3_1_7_2","first-page":"281","volume-title":"Computer Science Logic 2013","author":"Galliani P.","year":"2013","unstructured":"P. Galliani and L. Hella. 2013. Inclusion logic and fixed point logic. In Computer Science Logic 2013. 281\u2013295."},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.10.033"},{"key":"e_1_3_1_9_2","volume-title":"Dependence Logic. Theory and Applications","author":"Gr\u00e4del E.","year":"2016","unstructured":"E. Gr\u00e4del. 2016. Games for inclusion logic and fixed-point logic. In Dependence Logic. Theory and Applications, S. Abramsky, J. Kontinen, J. V\u00e4\u00e4n\u00e4nen, and H. Vollmer (Eds). Birkh\u00e4user."},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2675"},{"key":"e_1_3_1_11_2","first-page":"35:1\u201335:18","volume-title":"Computer Science Logic 2016","author":"Gr\u00e4del E.","year":"2016","unstructured":"E. Gr\u00e4del and S. Hegselmann. 2016. Counting in team semantics. In Computer Science Logic 2016, Vol. 62. 35:1\u201335:18."},{"key":"e_1_3_1_12_2","unstructured":"E. Gr\u00e4del P. Kolaitis J. Kontinen and H. Vollmer. 2019. Logics for dependence and independence (Dagstuhl seminar 19031). 9 1 (2019) 28\u201346."},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11225-013-9479-2"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-19570-0_20"},{"key":"e_1_3_1_15_2","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1007\/978-3-030-14812-6_16","volume-title":"Theory and Applications of Models of Computation","author":"Hirvonen \u00c5.","year":"2019","unstructured":"\u00c5. Hirvonen, J. Kontinen, and A. Pauly. 2019. Continuous team semantics. In Theory and Applications of Models of Computation. Springer, 262\u2013278."},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/5.4.539"},{"key":"e_1_3_1_17_2","first-page":"25:1\u201325:16","volume-title":"28th EACSL Annual Conference on Computer Science Logic (CSL 2020)","author":"Hoelzel M.","year":"2020","unstructured":"M. Hoelzel and R. Wilke. 2020. On the union closed fragment of existential second-order logic and logics with team semantics. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Dagstuhl, Germany, 25:1\u201325:16. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2020.25"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1755020315000192"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-017-0535-x"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142363"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10849-009-9082-0"},{"key":"e_1_3_1_22_2","volume-title":"Independence-Friendly Logic. A Game-Theoretic Approach","author":"Mann A.","year":"2012","unstructured":"A. Mann, G. Sandu, and M. Sevenster. 2012. Independence-Friendly Logic. A Game-Theoretic Approach. Cambridge University Press."},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511611193"},{"key":"e_1_3_1_24_2","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/978-3-319-47843-2_12","volume-title":"Rohit Parikh on Logic, Language and Society","author":"V\u00e4\u00e4n\u00e4nen J.","year":"2017","unstructured":"J. V\u00e4\u00e4n\u00e4nen. 2017. The logic of approximate dependence. In Rohit Parikh on Logic, Language and Society, C. Baskent, L. Moss, and R. Ramanujam (Eds.). Springer, 227\u2013234."},{"key":"e_1_3_1_25_2","volume-title":"Workshop on Logics of Dependence and Independence","author":"Wilke R.","year":"2020","unstructured":"R. Wilke. 2020. On the Presburger fragment of logics with multiteam semantics. In Workshop on Logics of Dependence and Independence, J. V\u00e4\u00e4n\u00e4nen and F. Yang (Eds.)."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3487579","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3487579","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:21Z","timestamp":1750188681000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3487579"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,14]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4,30]]}},"alternative-id":["10.1145\/3487579"],"URL":"https:\/\/doi.org\/10.1145\/3487579","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,14]]},"assertion":[{"value":"2020-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}