๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Cellular automata and finite fields

โœ Scribed by Franco Vivaldi

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
936 KB
Volume
79
Category
Article
ISSN
0167-2789

No coin nor oath required. For personal study only.

โœฆ Synopsis

We rewrite some concepts in the theory of one-dimensional periodic cellular automata in the language of finite fields. The state space of an automaton with N cell and q = pZ possible values for each cell (p prime) is identified with the finite field of qU elements, represented by means of a normal basis. The dynamics is given by a polynomial mapping with coefficients in the field of q elements. We illustrate the dynamical significance of several constructs of the theory of finite fields, and we suggest that cellular automata may provide a novel framework for the study of the dynamics of polynomials over finite fields.

๐Ÿ“œ SIMILAR VOLUMES

On the Computational Complexity of Finit
On the Computational Complexity of Finite Cellular Automata
โœ K. Sutner ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 932 KB

We study the computational complexity of several problems with the evolution of configurations on finite cellular automata. In many cases, the problems turn out to be complete in their respective classes. For example, the problem of deciding whether a configuration has a predecessor is shown to be N