Expansive automata networks

DOI10.1016/J.TCS.2020.06.019MaRDI QIDQ2003992zbMATHOpenAlexFDO

Authors Florian Bridoux, Maximilien Gadouleau, Guillaume Theyssier

Publication date 13 October 2020

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

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)

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.

Recommendations

• Dynamics of positive automata networks
• Dynamics of equivalence relations in automata networks
• Generalized Automata Networks
• scientific article; zbMATH DE number 1355187
• Entropies of the automata networks with additive rule

Cites work

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

Cited in

(3)

• Commutative automata networks
• Resource Driven Automata Nets
• Intrinsic universality in automata networks. I: Families and simulations

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)