Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Expansive automata networks.

Bridoux, Florian and Gadouleau, Maximilien and Theyssier, Guillaume (2020) 'Expansive automata networks.', Theoretical computer science., 843 . pp. 25-44.

Abstract

An Automata Network is a map 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. 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. A major trend in automata network theory is to understand how the interaction graph affects dynamical properties of f. Our first 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. Besides, we show striking differences between the linear and the general non-linear case, in particular we prove that deciding expansivity is PSPACE-complete in the general case, while it can be done in polynomial time in the linear case. Finally, 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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
(440Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1016/j.tcs.2020.06.019
Publisher statement:© 2020 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Date accepted:12 June 2020
Date deposited:06 August 2020
Date of first online publication:18 June 2020
Date first made open access:18 June 2021

Save or Share this output

Export:
Export
Look up in GoogleScholar