Finite Dynamical Systems, Hat Games, and Coding Theory
Finite Dynamical Systems, Hat Games, and Coding Theory
复制标题
有限动力系统、帽子游戏和编码理论
DOI：
10.1137/15m1044758
复制
发表时间：
2018
影响因子：
0.8
通讯作者：
Gadouleau M
中科院分区：
文献类型：
--
作者：
Gadouleau M
在编码理论问题的背景下，如网络编码和索引编码，以及在帽子博弈的背景下，如猜谜博弈和Winkler帽子博弈，研究了有限动力系统(FDSS)的性质。在本文中，我们将上述问题与离散离散系统的性质联系起来，包括不动点个数、不动点的稳定性和不稳定性。我们首先介绍了有向图的FDS及其对应的猜想维度和陪集维度。在陪集维度的基础上，对网络编码和索引编码之间已有的等价关系进行了提炼。我们还引入了FDSS的不稳定性的概念，研究了有向图的稳定性和不稳定性。我们证明了对于足够大的字母表，不稳定性总是达到最小反馈顶点集的大小。我们还得到了一些与图的顶点数无关的非稳定界。然后，我们将稳定性和不稳定性与猜测数联系起来。我们还展示了一类具有高稳定性和高不稳定性的大围长稀疏图；我们的方法是码论的，并使用猜测维度。最后，我们证明了仿射不稳定性总是渐近大于或等于线性猜想数。
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.