TY - JOUR
T1 - Intrinsic universality in automata networks I
T2 - Families and simulations
AU - Ríos-Wilson, Martín
AU - Theyssier, Guillaume
N1 - Publisher Copyright:
© 2024 Elsevier B.V.
PY - 2024/5/27
Y1 - 2024/5/27
N2 - An automata network (AN) is a finite graph where each node holds a state from a finite alphabet and is equipped with a local map defining the evolution of the state of the node depending on its neighbors. They are studied both from the dynamical and the computational complexity point of view. Inspired from well-established notions in the context of cellular automata, we develop a theory of intrinsic simulations and universality for families of automata networks. We establish many consequences of intrinsic universality in terms of complexity of orbits (periods of attractors, transients, etc) as well as hardness of the standard well-studied decision problems for automata networks (short/long term prediction, reachability, etc). In the way, we prove orthogonality results for these problems: the hardness of a single one does not imply hardness of the others, while intrinsic universality implies hardness of all of them. We also compare our notions of universality to intrinsic universality of cellular automata. This paper is the first of a series of three: in the second one, we develop a proof technique to establish intrinsic universality based on an operation of glueing; in the third one we study the effect of update schedules on intrinsic universality for concrete symmetric families of automata networks.
AB - An automata network (AN) is a finite graph where each node holds a state from a finite alphabet and is equipped with a local map defining the evolution of the state of the node depending on its neighbors. They are studied both from the dynamical and the computational complexity point of view. Inspired from well-established notions in the context of cellular automata, we develop a theory of intrinsic simulations and universality for families of automata networks. We establish many consequences of intrinsic universality in terms of complexity of orbits (periods of attractors, transients, etc) as well as hardness of the standard well-studied decision problems for automata networks (short/long term prediction, reachability, etc). In the way, we prove orthogonality results for these problems: the hardness of a single one does not imply hardness of the others, while intrinsic universality implies hardness of all of them. We also compare our notions of universality to intrinsic universality of cellular automata. This paper is the first of a series of three: in the second one, we develop a proof technique to establish intrinsic universality based on an operation of glueing; in the third one we study the effect of update schedules on intrinsic universality for concrete symmetric families of automata networks.
KW - Automata networks
KW - Intrinsic universality
KW - Prediction problem
KW - Reachability problem
UR - http://www.scopus.com/inward/record.url?scp=85189452766&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2024.114511
DO - 10.1016/j.tcs.2024.114511
M3 - Article
AN - SCOPUS:85189452766
SN - 0304-3975
VL - 997
JO - Theoretical Computer Science
JF - Theoretical Computer Science
M1 - 114511
ER -