Expansive automata networks

DOI10.1016/J.TCS.2020.06.019zbMATH Open1460.68050arXiv1902.08007OpenAlexW3036601938MaRDI QIDQ2003992FDOQ2003992

Florian Bridoux, Guillaume Theyssier, Maximilien Gadouleau

Publication date: 13 October 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: An Automata Network is a map $f:Q^{n}ightarrow{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.

Full work available at URL: https://arxiv.org/abs/1902.08007

zbMATH Keywords

PSPACE-completenessMDS codesexpansivityautomata networks

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Orthogonal arrays. Theory and applications
• Theory of cellular automata: a survey
• Expansive Subdynamics
• Orthogonal Arrays of Index Unity
• Simple dynamics on graphs
• Algebraic coding theory
• Handbook of finite fields
• Digraphs
• Graph-Theoretical Constructions for Graph Entropy and Network Coding Based Communications
• Unstable Homeomorphisms
• Observability of Boolean networks: a graph-theoretic approach
• Uniqueness Theorems for Periodic Functions
• Dynamical properties of expansive one-sided cellular automata
• Nondegenerate 𝑞-biresolving textile systems and expansive automorphisms of onesided full shifts
• Systems of distinct representatives and linear algebra
• Positive expansiveness versus network dimension in symbolic dynamical systems
• Cellular graph automata. I. basic concepts, graph property measurement, closure properties
• Cellular graph automata. II. graph and subgraph isomorphism, graph structure recognition
• On dynamical complexity of surjective ultimately right-expansive cellular automata
• On the rank and periodic rank of finite dynamical systems

Cited In (2)

• Resource Driven Automata Nets
• Commutative automata networks

This page was built for publication: Expansive automata networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2003992)