
arXiv: 1902.08007
An Automata Network is a map ${f:Q^n\rightarrow Q^n}$ where $Q$ is a finite alphabet. It can be viewed as a network of $n$ entities, each holding a state from $Q$, and evolving according to a deterministic synchronous update rule in such a way that each entity only depends on its neighbors in the network's graph, called interaction graph. A major trend in automata network theory is to understand how the interaction graph affects dynamical properties of $f$. In this work we introduce the following property called expansivity: the observation of the sequence of states at any given node is sufficient to determine the initial configuration of the whole network. Our main result is a characterization of interaction graphs that allow expansivity. Moreover, we show that this property is generic among linear automata networks over such graphs with large enough alphabet. We show however that the situation is more complex when the alphabet is fixed independently of the size of the interaction graph: no alphabet is sufficient to obtain expansivity on all admissible graphs, and only non-linear solutions exist in some cases. Finally, among other results, we consider a stronger version of expansivity where we ask to determine the initial configuration from any large enough observation of the system. We show that it can be achieved for any number of nodes and naturally gives rise to maximum distance separable codes.
Cellular automata (computational aspects), FOS: Computer and information sciences, expansivity, 511, Formal languages and automata, Dynamical Systems (math.DS), Computer Science - Distributed, Parallel, and Cluster Computing, FOS: Mathematics, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Mathematics - Combinatorics, MDS codes, Distributed, Parallel, and Cluster Computing (cs.DC), Combinatorics (math.CO), Mathematics - Dynamical Systems, automata networks, PSPACE-completeness
Cellular automata (computational aspects), FOS: Computer and information sciences, expansivity, 511, Formal languages and automata, Dynamical Systems (math.DS), Computer Science - Distributed, Parallel, and Cluster Computing, FOS: Mathematics, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Mathematics - Combinatorics, MDS codes, Distributed, Parallel, and Cluster Computing (cs.DC), Combinatorics (math.CO), Mathematics - Dynamical Systems, automata networks, PSPACE-completeness
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
