Abstract
A one-dimensional linear cellular automaton with periodic boundary conditions consists of a lattice of sites on a cylinder evolving according to a linear local interaction rule. Limit cycles for such a system are studied as sets of strings on which the rule acts as a shift of sizes/h; i.e., each string in the limit cycle cyclically shifts bys sites inh iterations of the rule. For any given rule, the size of the shift varies with the cylinder sizen. The analysis of shifts establishes an equivalence between the strings of values appearing in limit cycles for these automata, and linear recurring sequences in finite fields. Specifically, it is shown that a string appears in a limit cycle for a linear automaton rule on a cylinder sizen iff its values satisfy a linear recurrence relation defined by the shift value for thatn. The rich body of results on recurring sequences and finite fields can then be used to obtain detailed information on periodic behavior for these systems. Topics considered here include the inverse problem of identifying the set of linear automata rules for which a given string appears in a limit cycle, and the structure under operations (such as addition and complementation) of sets of limit cycle strings.
Similar content being viewed by others
References
Martin, O., Odlyzko, A., Wolfram, S.: Algebraic properties of cellular automata. Commun. Math. Phys.93, 219–259 (1984)
Guan, P., He, Y.: Exact results for deterministic cellular automata. J. Stat. Phys.43, 463 (1986)
Guan, P., He, Y.: Upper bound on the number of cycles in border-decisive cellular automata. Complex Systems1, 181 (1987)
Jen, E.: Cylindrical cellular automata. Commun. Math. Phys.118, 569–590 (1988)
Lidl, R., Niederreiter, H.: Finite fields. Reading, MA: Addison-Wesley 1983
Zierler, N.: Linear recurring sequences. J. SIAM7, 31 (1959)
Zierler, N., Mills, W. H.: Products of linear recurring sequences. J. Algebra27, 147 (1973)
McEliece, R.: Finite fields for computer scientist and engineers. Boston, MA: Kluwer Academic 1987
Berlekamp, E.: Algebraic coding theory. New York: McGraw-Hill 1968
Author information
Authors and Affiliations
Additional information
Communicated by J. L. Lebowitz
Rights and permissions
About this article
Cite this article
Jen, E. Linear cellular automata and recurring sequences in finite fields. Commun.Math. Phys. 119, 13–28 (1988). https://doi.org/10.1007/BF01218258
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01218258