id: 02113949
dt: j
an: 02113949
au: Nishio, Hidenosuke; Saito, Takashi
ti: Information dynamics of cellular automata. I: An algebraic study.
so: Fundam. Inform. 58, No. 3-4, 399-420 (2003).
py: 2003
pu: Polish Mathematical Society, Warsaw; IOS Press, Amsterdam
la: EN
cc: 
ut: polynomials over finite fields; dynamical system
ci: 
li: 
ab: 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.
rv: