Reversibility of 1D Cellular Automata with Periodic Boundary over Finite Fields Z(p)


Cinkir Z., Akin H., Siap I.

JOURNAL OF STATISTICAL PHYSICS, cilt.143, ss.807-823, 2011 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 143 Konu: 4
  • Basım Tarihi: 2011
  • Doi Numarası: 10.1007/s10955-011-0202-2
  • Dergi Adı: JOURNAL OF STATISTICAL PHYSICS
  • Sayfa Sayıları: ss.807-823

Özet

The reversibility problem for linear cellular automata with null boundary defined by a rule matrix in the form of a pentadiagonal matrix was studied recently over the binary field Z(2) (del Rey and Rodriguez Sanchez in Appl. Math. Comput., 2011, doi:10.1016/j.amc.2011.03.033). In this paper, we study one-dimensional linear cellular automata with periodic boundary conditions over any finite field Z(p). For any given p >= 2, we show that the reversibility problem can be reduced to solving a recurrence relation depending on the number of cells and the coefficients of the local rules defining the one-dimensional linear cellular automata. More specifically, for any given values (from any fixed field Z(p)) of the coefficients of the local rules, we outline a computer algorithm determining the recurrence relation which can be solved by testing reversibility of the cellular automaton for some finite number of cells. As an example, we give the full criteria for the reversibility of the one-dimensional linear cellular automata over the fields Z(2) and Z(3).