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:

Complete simulation of automata networks.

Bridoux, Florian and Castillo-Ramirez, Alonso and Gadouleau, Maximilien (2020) 'Complete simulation of automata networks.', Journal of computer and system sciences., 109 . pp. 1-21.

Abstract

Consider a finite set A and . We study complete simulation of transformations of , also known as automata networks. For , a transformation of is n-complete of size m if it may simulate every transformation of by updating one register at a time. Using tools from memoryless computation, we establish that there is no n-complete transformation of size n, but there is one of size . By studying various constructions, we conjecture that the maximal time of simulation of any n-complete transformation is at least 2n. We also investigate the time and size of sequentially n-complete transformations, which may simulate every finite sequence of transformations of . Finally, we show that there is no n-complete transformation updating all registers in parallel, but there exists one updating all but one register in parallel. This illustrates the strengths and weaknesses of sequential and parallel models of computation.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
(605Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1016/j.jcss.2019.12.001
Publisher statement:© 2019 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:01 December 2019
Date deposited:10 December 2019
Date of first online publication:06 December 2019
Date first made open access:06 December 2020

Save or Share this output

Export:
Export
Look up in GoogleScholar