02113949

j

02113949 Nishio, Hidenosuke Saito, Takashi Information dynamics of cellular automata. I: An algebraic study. Fundam. Inform. 58, No. 3-4, 399-420 (2003). 2003 Polish Mathematical Society, Warsaw; IOS Press, Amsterdam EN polynomials over finite fields dynamical system Summary: Information dynamics of Cellular Automata (CA) is studied using polynomials over finite fields. The information about the uncertainty of cell states is expressed by an indeterminate $X$ called information variable and its dynamics is investigated by extending CA to CA[$X$] whose cell states are polynomials in $X$. For the global configuration of extended CA[$X$], new notions of completeness and degeneracy are defined and their dynamical properties are investigated. A theorem is proved that completeness equals non-degeneracy. With respect to the reversibility, we prove that a CA is reversible, if and only if its extension CA[$X$] preserves the set of complete configurations. Information dynamics of finite CAs and linear CAs are treated in separate sections. Decision problems are also referred to.