{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T16:38:38Z","timestamp":1778085518304,"version":"3.51.4"},"reference-count":85,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"6","license":[{"start":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T00:00:00Z","timestamp":1685577600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T00:00:00Z","timestamp":1685577600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T00:00:00Z","timestamp":1685577600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"funder":[{"DOI":"10.13039\/501100002920","name":"Hong Kong Research Grant Council","doi-asserted-by":"publisher","award":["ECS CUHK 24205621"],"award-info":[{"award-number":["ECS CUHK 24205621"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004853","name":"Direct Grant for Research, The Chinese University of Hong Kong","doi-asserted-by":"publisher","award":["4055133"],"award-info":[{"award-number":["4055133"]}],"id":[{"id":"10.13039\/501100004853","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1109\/tit.2023.3247570","type":"journal-article","created":{"date-parts":[[2023,2,22]],"date-time":"2023-02-22T18:28:28Z","timestamp":1677090508000},"page":"3493-3510","source":"Crossref","is-referenced-by-count":12,"title":["Undecidability of Network Coding, Conditional Information Inequalities, and Conditional Independence Implication"],"prefix":"10.1109","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4803-212X","authenticated-orcid":false,"given":"Cheuk Ting","family":"Li","sequence":"first","affiliation":[{"name":"Department of Information Engineering, The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"ref13","article-title":"Representability of matroids by c-arrangements is undecidable","author":"k\u00fchne","year":"2019","journal-title":"arXiv 1912 06123"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.928963"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2009.5394800"},{"key":"ref56","author":"yeung","year":"2008","journal-title":"Information Theory and Network Coding"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.2307\/2275184"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.4310\/CIS.2002.v2.n2.a3"},{"key":"ref14","article-title":"Is network coding undecidable?","author":"dougherty","year":"2009","journal-title":"Applications of Matroid Theory and Combinatorial Optimization to Information and Coding Theory"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2201340"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1109\/18.641561"},{"key":"ref52","article-title":"On entropic and almost multilinear representability of matroids","author":"k\u00fchne","year":"2022","journal-title":"arXiv 2206 03465"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2010.2095490"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1109\/18.681320"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2094910"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1109\/18.641556"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.864474"},{"key":"ref16","article-title":"The undecidability of network coding with some fixed-size messages and edges","author":"ting li","year":"2021","journal-title":"arXiv 2109 08991"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1109\/SURV.2013.013013.00104"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.920209"},{"key":"ref51","first-page":"410","article-title":"Saturated conditional independence with fixed and undetermined sets of incomplete random variables","author":"koehler","year":"2014","journal-title":"Proc Conf Uncertainty of Artificial Intelligence"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2013.06.005"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1109\/ITW48936.2021.9611489"},{"key":"ref45","article-title":"Decision problems in information theory","author":"abo khamis","year":"2020","journal-title":"arXiv 2004 08783"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1109\/3468.895901"},{"key":"ref47","article-title":"First-order theory of probabilistic independence and single-letter characterizations of capacity regions","author":"ting li","year":"2021","journal-title":"arXiv 2108 07324"},{"key":"ref42","article-title":"Logical inference algorithms and matrix representations for probabilistic conditional independence","author":"niepert","year":"2012","journal-title":"arXiv 1205 2621"},{"key":"ref41","first-page":"226","article-title":"Quantifier elimination for statistical problems","author":"geiger","year":"1999","journal-title":"Proc 15th Conf Uncertainty Artif Intell"},{"key":"ref85","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8608-5"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-19570-0_20"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.05.010"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2010.01.011"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.874434"},{"key":"ref7","article-title":"Network coding","author":"lehman","year":"2005"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2009.5394818"},{"key":"ref4","article-title":"Deterministic network coding by matrix completion","author":"harvey","year":"2005"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.847712"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.881746"},{"key":"ref5","doi-asserted-by":"crossref","first-page":"2184","DOI":"10.1109\/INFCOM.2005.1498493","article-title":"On achieving optimal throughput with network coding","volume":"3","author":"li","year":"2005","journal-title":"Proc IEEE 24th Annu Joint Conf IEEE Comput Commun Societies"},{"key":"ref82","article-title":"The undecidability of conditional affine information inequalities and conditional independence implication with a binary constraint","author":"ting li","year":"2021","journal-title":"arXiv 2104 05634"},{"key":"ref81","author":"kurosh","year":"1963","journal-title":"Lectures in General Algebras"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176349407"},{"key":"ref84","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.851744"},{"key":"ref83","volume":"129","author":"fulton","year":"2013","journal-title":"Representation Theory a First Course"},{"key":"ref80","doi-asserted-by":"publisher","DOI":"10.2307\/1969481"},{"key":"ref35","first-page":"557","article-title":"A note on conditional independence","volume":"44","author":"mouchart","year":"1984","journal-title":"Statistica"},{"key":"ref79","doi-asserted-by":"publisher","DOI":"10.2307\/2267170"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/BF00258078"},{"key":"ref78","first-page":"215","article-title":"Impossibility of certain algorithms in the theory of associative systems","volume":"16","author":"markov","year":"1951","journal-title":"The Journal of Symbolic Logic"},{"key":"ref37","first-page":"3","article-title":"Multiinformation and the problem of characterization of conditional independence relations","author":"studen\u00fd","year":"1989","journal-title":"Problems Control Inf Theory"},{"key":"ref36","first-page":"357","article-title":"GRAPHOIDS: A graph-based logic for reasoning about relevance relations","author":"pearl","year":"1987","journal-title":"Advances in Artificial Intelligence II"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2048502"},{"key":"ref75","volume":"3","author":"oxley","year":"2006","journal-title":"Matroid Theory"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2023702"},{"key":"ref74","author":"keedwell","year":"2015","journal-title":"Latin Squares and Their Applications"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1979.tb01052.x"},{"key":"ref77","first-page":"93","article-title":"Frames of permuting equivalences","volume":"51","author":"herrmann","year":"1987","journal-title":"Acta Sci Math"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2414926"},{"key":"ref76","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.896862"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.807285"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1109\/18.850663"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90077-F"},{"key":"ref38","first-page":"377","article-title":"Conditional independence relations have no finite complete characterization","author":"studen\u00fd","year":"1992","journal-title":"Proc Inf Theory Stat Decis Functions Random Processes"},{"key":"ref71","doi-asserted-by":"publisher","DOI":"10.1109\/MBITS.2021.3123197"},{"key":"ref70","doi-asserted-by":"publisher","DOI":"10.1145\/3472391"},{"key":"ref73","first-page":"25","article-title":"The problem of equality of words for certain classes of semigroups","volume":"5","author":"gurevich","year":"1966","journal-title":"Algebra i Logika"},{"key":"ref72","first-page":"207","article-title":"Undecidability of the universal theory of finite groups","volume":"20","author":"slobodskoi","year":"1981","journal-title":"Algebra i Logika"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/320557.320571"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT45174.2021.9517792"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.09.002"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.2982642"},{"key":"ref26","first-page":"499","article-title":"Network coding: Does the model need tuning?","volume":"5","author":"lehman","year":"2005","journal-title":"Proc SODA"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.874405"},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1504\/IJICOT.2017.081456"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1109\/NetCod.2013.6570814"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2274614"},{"key":"ref63","article-title":"Non-Shannon information inequalities in four random variables","author":"dougherty","year":"2011","journal-title":"arXiv 1104 3602"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1148"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2019.8849309"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1109\/NETCOD.2014.6892127"},{"key":"ref65","author":"yeung","year":"1996","journal-title":"ITIP—Information Theoretic Inequality Prover"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.883634"},{"key":"ref27","first-page":"1","article-title":"Network coding: The case of multiple unicast sessions","volume":"16","author":"li","year":"2004","journal-title":"Proc Allerton Conf Commun"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2103753"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2006.261840"},{"key":"ref62","first-page":"2116","article-title":"A projection method for derivation of non-Shannon-type information inequalities","author":"xu","year":"2008","journal-title":"Proc IEEE Int Symp Inf Theory"},{"key":"ref61","first-page":"41","article-title":"Infinitely many information inequalities","author":"mat\u00fa\u0161","year":"2007","journal-title":"Proc IEEE Int Symp Inf Theory (ISIT)"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/18\/10130037\/10049584.pdf?arnumber=10049584","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,12]],"date-time":"2023-06-12T18:01:49Z","timestamp":1686592909000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/10049584\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6]]},"references-count":85,"journal-issue":{"issue":"6"},"URL":"https:\/\/doi.org\/10.1109\/tit.2023.3247570","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"value":"0018-9448","type":"print"},{"value":"1557-9654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6]]}}}