2024/04/09 by Castillo-Ramirez, Alonso, Veliz-Quintero, Eduardo · 1 citation
#37B15 #68Q80 #Cellular Automata and Lattice Gases (nlin.CG) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2404.06394
For a group G and a finite set A, a cellular automaton (CA) is a transformation τ: AG → AG defined via a finite memory set S ⊆ G and a local map μ: AS → A. Although memory sets are not unique, every CA admits a unique minimal memory set, which consists on all the essential elements of S that affect the behavior of the local map. In this paper, we study the links between the minimal memory set and the generating patterns P of μ; these are the patterns in AS that are not fixed when the cellular automaton is applied. In particular, we show that when \vert S \vert ≥ 2 and \vert P \vert is not a multiple of \vert A \vert, then the minimal memory set must be S itself. Moreover, when \vert P \vert = \vert A \vert, \vert S \vert ≥ 3, and the restriction of μ to these patterns is well-behaved, then the minimal memory set must be S or S ∖ \s\, for some s ∈ S ∖ \e\. These are some of the first general theoretical results on the minimal memory set of a cellular automaton.