{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,19]],"date-time":"2026-09-19T11:52:54Z","timestamp":1789818774913,"version":"4.0.1"},"reference-count":51,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/K033956\/1"],"award-info":[{"award-number":["EP\/K033956\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>The properties of finite dynamical systems (FDSs) have been investigated in the context of coding theoretic problems, such as network coding and index coding, and in the context of hat games, such as the guessing game and Winkler's hat game. In this paper, we relate the problems mentioned above to properties of FDSs, including the number of fixed points, their stability, and their instability. We first introduce the guessing dimension and the coset dimension of an FDS and their counterparts for directed graphs. Based on the coset dimension, we then refine the existing equivalences between network coding and index coding. We also introduce the concept of the instability of FDSs and we study the stability and the instability of directed graphs. We prove that the instability always reaches the size of a minimum feedback vertex set for large enough alphabets. We also obtain some nonstable bounds independent of the number of vertices of the graph. We then relate the stability and the instability to the guessing number. We also exhibit a class of sparse graphs with large girth that have high stability and high instability; our approach is code-theoretic and uses the guessing dimension. Finally, we prove that the affine instability is always asymptotically greater than or equal to the linear guessing number.<\/jats:p>","DOI":"10.1137\/15m1044758","type":"journal-article","created":{"date-parts":[[2018,8,1]],"date-time":"2018-08-01T12:34:58Z","timestamp":1533126898000},"page":"1922-1945","source":"Crossref","is-referenced-by-count":11,"title":["Finite Dynamical Systems, Hat Games, and Coding Theory"],"prefix":"10.1137","volume":"32","author":[{"given":"Maximilien","family":"Gadouleau","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,8,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2010.07.007"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1109\/18.850663"},{"key":"atypb3","first-page":"823","author":"Alon N.","year":"2008","journal-title":"Proceedings of the IEEE Annual Symposium on Foundations of Computer Science"},{"key":"atypb4","unstructured":"L. Babai,\n                      Automorphism groups, isomorphism, reconstruction\n                      , Handbook of Combinatorics, North Holland, Amsterdam, 1994."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.12.061"},{"key":"atypb6","first-page":"197","author":"Bar-Yossef Z.","year":"2006","journal-title":"Proceedings of the IEEE Annual Symposium on Foundations of Computer Science"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2103753"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20512"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.874540"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"J. Bondy and U. Murty,\n                      Graph Theory\n                      , Grad. Texts Math. 244, Springer, New York, 2008.","DOI":"10.1007\/978-1-84628-970-5"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/060652774"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2012.03.027"},{"key":"atypb13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.37236\/679","volume":"18","author":"Christofides D.","year":"2011","journal-title":"Electron. J. Combin."},{"key":"atypb14","unstructured":"G. D. Cohen, I. Honkala, S. Litsyn, and A. C. Lobstein,\n                      Covering Codes\n                      , Elsevier, New York, 1997."},{"key":"atypb15","unstructured":"T. Ebert,\n                      Applications of recursive operators to randomness and complexity\n                      , Ph.D. thesis, University of California at Santa Barbara, 1998."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702415317"},{"key":"atypb17","first-page":"967","author":"Effros M.","year":"2013","journal-title":"Proceedings of the IEEE International Symposium on Information Theory"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2282293"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/130944680"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2544344"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/140988358"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2155618"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90057-X"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"E. Goles and S. Marti\u0301nez,\n                      Neural and Automata Networks: Dynamical Behavior and Applications\n                      , Kluwer Academic, Norwell, MA, 1990.","DOI":"10.1007\/978-94-009-0529-0_2"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/0165-4896(83)90023-9"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.79.8.2554"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1089\/10665270252833208"},{"key":"atypb28","first-page":"770","volume":"9","author":"Karlebach G.","year":"2008","journal-title":"Nature"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/0022-5193(69)90015-0"},{"key":"atypb30","first-page":"121","volume":"50","author":"Krzywkowski M.","year":"2010","journal-title":"Comment. Math."},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"M. Krzywkowski,\n                      Hat Problem on a Graph\n                      , Ph.D. thesis, University of Exeter, 2012.","DOI":"10.7494\/OpMath.2012.32.2.285"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1038\/nrg3885"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.807285"},{"key":"atypb34","first-page":"113","volume":"5","author":"Mac Culloch W. S.","year":"1943","journal-title":"Bull. Math. Biophys."},{"key":"atypb35","unstructured":"F. J. MacWilliams and N. J. A. Sloane,\n                      The Theory of Error-Correcting Codes\n                      , North-Holland, Amsterdam, 1977."},{"key":"atypb36","first-page":"1977","author":"Mazumdar A.","year":"2014","journal-title":"Proceedings of the IEEE International Symposium on Information Theory"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.05.034"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579347"},{"key":"atypb39","unstructured":"S. Riis,\n                      Linear versus non-linear Boolean functions in network flow\n                      , in Proceedings of the Annual Conference on Information Systems and Sciences (CISS), Princeton, NJ, 2004."},{"key":"atypb40","first-page":"866","author":"Riis S.","year":"2006","journal-title":"New York"},{"key":"atypb41","unstructured":"S. Riis,\n                      Graph Entropy, Network Coding and Guessing Games\n                      , arXiv:0711.4175, 2007."},{"key":"atypb42","doi-asserted-by":"crossref","first-page":"1","DOI":"10.37236\/962","volume":"14","author":"Riis S.","year":"2007","journal-title":"Electron. J. Combin."},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.907345"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2048502"},{"key":"atypb45","doi-asserted-by":"crossref","first-page":"1","DOI":"10.37236\/5135","volume":"24","author":"Szczechla W.","year":"2017","journal-title":"Electron. J. Combin."},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1016\/0022-5193(73)90247-6"},{"key":"atypb47","unstructured":"R. Thomas and R. D'Ari,\n                      Biological Feedback\n                      , CRC Press, Boca Raton, FL, 1990."},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1063\/1.1350439"},{"key":"atypb49","first-page":"301","author":"Winkler P.","year":"2001","journal-title":"MA"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.09.009"},{"key":"atypb51","first-page":"330","author":"Yeung R. W.","year":"2006","journal-title":"MA"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1044758","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:58:58Z","timestamp":1787320738000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1044758"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/15M1044758"],"URL":"https:\/\/doi.org\/10.1137\/15m1044758","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}