{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T20:46:26Z","timestamp":1783111586405,"version":"3.54.6"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,10,29]],"date-time":"2024-10-29T00:00:00Z","timestamp":1730160000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2024,10,31]]},"abstract":"\n We study functional dependencies together with two different probabilistic dependency notions: unary marginal identity and unary marginal distribution equivalence. A unary marginal identity states that two variables\n \n \\(x\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(y\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n are identically distributed. A unary marginal distribution equivalence states that the multiset consisting of the marginal probabilities of all the values for variable\n \n \\(x\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is the same as the corresponding multiset for\n \n \\(y\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . We present a sound and complete axiomatization for the class of these dependencies and show that it has Armstrong relations. The axiomatization is infinite, but we show that there can be no finite axiomatization. The implication problem for the subclass that contains only functional dependencies and unary marginal identities can be simulated with functional dependencies and unary inclusion atoms, and therefore the problem is in polynomial-time. This complexity bound also holds in the case of the full class, which we show by constructing a polynomial-time algorithm.\n <\/jats:p>","DOI":"10.1145\/3677120","type":"journal-article","created":{"date-parts":[[2024,7,18]],"date-time":"2024-07-18T16:31:53Z","timestamp":1721320313000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["The Implication Problem for Functional Dependencies and Variants of Marginal Distribution Equivalences"],"prefix":"10.1145","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2701-9620","authenticated-orcid":false,"given":"Minna","family":"Hirvonen","sequence":"first","affiliation":[{"name":"University of Helsinki, Helsinki, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,10,29]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"Samson Abramsky Joni Puljuj\u00e4rvi and Jouko V\u00e4\u00e4n\u00e4nen. 2021. Team semantics and independence notions in quantum physics. arXiv:2107.10817. Retrieved from https:\/\/arxiv.org\/abs\/2107.10817#"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2022.103088"},{"key":"e_1_3_2_4_2","first-page":"580","volume-title":"Proceedings of the IFIP World Computer Congress","author":"Armstrong William W.","year":"1974","unstructured":"William W. Armstrong. 1974. Dependency structures of data base relationships. In Proceedings of the IFIP World Computer Congress, 580\u2013583."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/320064.320066"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2422.322414"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214049"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/78935.78937"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-017-9568-4"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/322344.322347"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90005-4"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2011.08.005"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90077-F"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11225-013-9479-2"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-19570-0_20"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.02.007"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91458-9_21"},{"key":"e_1_3_2_18_2","doi-asserted-by":"crossref","unstructured":"Miika Hannula and Jonni Virtema. 2021. Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals. arXiv:2012.12830. Retrieved from https:\/\/arxiv.org\/abs\/2012.12830","DOI":"10.1007\/978-3-030-75775-5_18"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-11321-5_8"},{"issue":"4","key":"e_1_3_2_20_2","first-page":"539","article-title":"Compositional semantics for a language of imperfect information","volume":"5","author":"Hodges Wilfrid","year":"1997","unstructured":"Wilfrid Hodges. 1997. Compositional semantics for a language of imperfect information. Journal of the Interest Group in Pure and Applied Logics 5 (4) (1997), 539\u2013563.","journal-title":"Journal of the Interest Group in Pure and Applied Logics"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2009.11.002"},{"key":"e_1_3_2_22_2","unstructured":"Cheuk Ting Li. 2022. Undecidability of network coding conditional information inequalities and conditional independence implication. arXiv:2205.11461. Retrieved from https:\/\/arxiv.org\/abs\/2205.11461"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90015-2"},{"key":"e_1_3_2_24_2","first-page":"377","volume-title":"Proceedings of the Transactions of the 11th Prague Conference on Information Theory, Statistical Decision Functions and Random Processes","author":"Studen\u00fd Milan","year":"1992","unstructured":"Milan Studen\u00fd. 1992. Conditional independence relations have no finite complete characterization. In Proceedings of the Transactions of the 11th Prague Conference on Information Theory, Statistical Decision Functions and Random Processes. S. Kubik and J.A. Visek (Eds.), Vol. B, Kluwer, 377\u2013396."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-55860-332-5.50074-2"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511611193"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3677120","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3677120","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:06:17Z","timestamp":1750291577000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3677120"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,29]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,10,31]]}},"alternative-id":["10.1145\/3677120"],"URL":"https:\/\/doi.org\/10.1145\/3677120","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,29]]},"assertion":[{"value":"2023-03-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-07-02","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}