{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T12:07:38Z","timestamp":1753877258502,"version":"3.41.2"},"reference-count":28,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2025,3,30]],"date-time":"2025-03-30T00:00:00Z","timestamp":1743292800000},"content-version":"vor","delay-in-days":19,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,3,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We study the expressivity and the complexity of various logics in probabilistic team semantics with the Boolean negation. In particular, we study the extension of probabilistic independence logic with the Boolean negation, and a recently introduced logic first-order theory of random variables with probabilistic independence. We give several results that compare the expressivity of these logics with the most studied logics in probabilistic team semantics setting, as well as relating their expressivity to a numerical variant of second-order logic. In addition, we introduce novel entropy atoms and show that the extension of first-order logic by entropy atoms subsumes probabilistic independence logic. Finally, we obtain some results on the complexity of model checking, validity and satisfiability of our logics.<\/jats:p>","DOI":"10.1093\/logcom\/exaf021","type":"journal-article","created":{"date-parts":[[2025,3,31]],"date-time":"2025-03-31T19:59:00Z","timestamp":1743451140000},"source":"Crossref","is-referenced-by-count":0,"title":["Logics with probabilistic team semantics and the Boolean negation"],"prefix":"10.1093","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9637-6664","authenticated-orcid":false,"given":"Miika","family":"Hannula","sequence":"first","affiliation":[{"name":"Institute of Computer Science, University of Tartu , 51009 Tartu ,","place":["Estonia"]},{"name":"Department of Mathematics and Statistics, University of Helsinki , 00014 Helsinki ,","place":["Finland"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2701-9620","authenticated-orcid":false,"given":"Minna","family":"Hirvonen","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, University of Helsinki , 00014 Helsinki ,","place":["Finland"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0115-5154","authenticated-orcid":false,"given":"Juha","family":"Kontinen","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, University of Helsinki , 00014 Helsinki ,","place":["Finland"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5651-5391","authenticated-orcid":false,"given":"Yasir","family":"Mahmood","sequence":"additional","affiliation":[{"name":"Data Science Group, Heinz Nixdorf Institute, Paderborn University , 33098 Paderborn, DE"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8061-5376","authenticated-orcid":false,"given":"Arne","family":"Meier","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Theoretische Informatik, Leibniz Universit\u00e4t Hannover , 30167 Hannover, DE"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1582-3718","authenticated-orcid":false,"given":"Jonni","family":"Virtema","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Sheffield , S10 2TN Sheffield ,","place":["UK"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2025,3,30]]},"reference":[{"key":"2025042210120936700_ref1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","article-title":"$\\sum ^{1}_{1}$-formulae on finite structures","volume":"24","author":"Ajtai","year":"1983","journal-title":"Annals of Pure and Applied Logic"},{"key":"2025042210120936700_ref2","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1109\/SFCS.1988.21955","article-title":"On a theory of computation over the real numbers; NP completeness, recursive functions and universal machines (extended abstract)","volume-title":"[Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science","author":"Blum","year":"1988"},{"key":"2025042210120936700_ref3","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/j.jco.2005.11.001","article-title":"Counting complexity classes for numeric computations II: algebraic and semialgebraic sets","volume":"22","author":"B\u00fcrgisser","year":"2006","journal-title":"Journal of Complexity"},{"key":"2025042210120936700_ref4","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/s10472-017-9568-4","article-title":"Approximation and dependence via multiteam semantics","volume":"83","author":"Durand","year":"2018","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"2025042210120936700_ref5","first-page":"186","article-title":"Probabilistic team semantics","volume-title":"FoIKS. Lecture Notes in Computer Science","author":"Durand","year":"2018"},{"key":"2025042210120936700_ref6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3471618","article-title":"Tractability frontier of data complexity in team semantics","volume":"23","author":"Durand","year":"2022","journal-title":"ACM Transactions on Computational Logic"},{"volume-title":"Game Values and Equilibria for Undetermined Sentences of Dependence Logic","year":"2008","author":"Galliani","key":"2025042210120936700_ref7"},{"key":"2025042210120936700_ref8","first-page":"281","article-title":"Inclusion logic and fixed point logic","volume-title":"CSL LIPIcs","author":"Galliani","year":"2013"},{"key":"2025042210120936700_ref9","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.tcs.2012.10.033","article-title":"Model-checking games for logics of imperfect information","volume":"493","author":"Gr\u00e4del","year":"2013","journal-title":"Theoretical Computer Science"},{"key":"2025042210120936700_ref10","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1006\/inco.1997.2675","article-title":"Metafinite model theory","volume":"140","author":"Gr\u00e4del","year":"1998","journal-title":"Information and Computation"},{"key":"2025042210120936700_ref11","doi-asserted-by":"crossref","DOI":"10.1016\/j.ic.2021.104759","article-title":"Complexity thresholds in inclusion logic","volume":"287","author":"Hannula","year":"2022","journal-title":"Information and Computation"},{"key":"2025042210120936700_ref12","doi-asserted-by":"crossref","first-page":"103108","DOI":"10.1016\/j.apal.2022.103108","article-title":"Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals","volume":"173","author":"Hannula","year":"2022","journal-title":"Annals of Pure and Applied Logic"},{"key":"2025042210120936700_ref13","first-page":"198","article-title":"On quantified propositional logics and the exponential time hierarchy","volume-title":"GandALF EPTCS","author":"Hannula","year":"2016"},{"key":"2025042210120936700_ref14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3204521","article-title":"Complexity of propositional logics in team semantic","volume":"19","author":"Hannula","year":"2018","journal-title":"ACM Transactions on Computational Logic"},{"key":"2025042210120936700_ref15","first-page":"304","article-title":"Facets of distribution identities in probabilistic team semantics","volume-title":"JELIA. Lecture Notes in Computer Science","author":"Hannula","year":"2019"},{"key":"2025042210120936700_ref16","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1145\/3373718.3394773","article-title":"Descriptive complexity of real computation and probabilistic independence logic","volume-title":"LICS","author":"Hannula","year":"2020"},{"key":"2025042210120936700_ref17","doi-asserted-by":"crossref","first-page":"103104","DOI":"10.1016\/j.apal.2022.103104","article-title":"On elementary logics for quantitative dependencies","volume":"173","author":"Hannula","year":"2022","journal-title":"Annals of Pure and Applied Logic"},{"key":"2025042210120936700_ref18","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1007\/978-3-031-43619-2_45","article-title":"Logics with probabilistic team semantics and the Boolean negation","volume-title":"Logics in Artificial Intelligence","author":"Hannula","year":"2023"},{"key":"2025042210120936700_ref19","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1093\/jigpal\/5.4.539","article-title":"Compositional semantics for a language of imperfect information","volume":"5","author":"Hodges","year":"1997","journal-title":"Logic Journal of IGPL"},{"key":"2025042210120936700_ref20","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1007\/s00153-017-0535-x","article-title":"A logic for arguing about probabilities in measure teams","volume":"56","author":"Hyttinen","year":"2017","journal-title":"Archive for Mathematical Logic"},{"key":"2025042210120936700_ref21","first-page":"1093","article-title":"A polynomial algorithm in linear programming","volume":"244","author":"Khachiyan","year":"1979","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"2025042210120936700_ref22","doi-asserted-by":"crossref","first-page":"259","DOI":"10.3233\/FI-2011-386","article-title":"Team logic and second-order logic","volume":"106","author":"Kontinen","year":"2011","journal-title":"Fundamenta Informaticae"},{"key":"2025042210120936700_ref23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/jsl.2022.80","article-title":"Complete logics for elementary team properties","volume":"88","author":"Kontinen","year":"2022","journal-title":"The Journal of Symbolic Logic"},{"key":"2025042210120936700_ref24","first-page":"1536","article-title":"First-order theory of probabilistic independence and single-letter characterizations of capacity regions","volume-title":"ISIT","author":"Li","year":"2022"},{"volume-title":"Computational Complexity","year":"2007","author":"Papadimitriou","key":"2025042210120936700_ref25"},{"key":"2025042210120936700_ref26","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0747-7171(10)80003-3","article-title":"On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals","volume":"13","author":"Renegar","year":"1992","journal-title":"Journal of Symbolic Computation"},{"key":"2025042210120936700_ref27","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1007\/s00224-015-9662-0","article-title":"Fixed points, Nash equilibria, and the existential theory of the reals","volume":"60","author":"Schaefer","year":"2017","journal-title":"Theory of Computing Systems"},{"key":"2025042210120936700_ref28","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511611193","volume-title":"Dependence Logic - A New Approach to Independence Friendly Logic, London Mathematical Society Student Texts","author":"V\u00e4\u00e4n\u00e4nen","year":"2007"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/35\/3\/exaf021\/62811102\/exaf021.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/35\/3\/exaf021\/62811102\/exaf021.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,22]],"date-time":"2025-04-22T14:56:52Z","timestamp":1745333812000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/doi\/10.1093\/logcom\/exaf021\/8100473"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,11]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,3,11]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exaf021","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"type":"print","value":"0955-792X"},{"type":"electronic","value":"1465-363X"}],"subject":[],"published-other":{"date-parts":[[2025,4]]},"published":{"date-parts":[[2025,3,11]]},"article-number":"exaf021"}}