Skip to main content

Research Repository

Advanced Search

Complete Simulation of Automata Networks

Bridoux, Florian; Castillo-Ramirez, Alonso; Gadouleau, Maximilien

Complete Simulation of Automata Networks Thumbnail


Florian Bridoux

Alonso Castillo-Ramirez


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.


Bridoux, F., Castillo-Ramirez, A., & Gadouleau, M. (2020). Complete Simulation of Automata Networks. Journal of Computer and System Sciences, 109, 1-21.

Journal Article Type Article
Acceptance Date Dec 1, 2019
Online Publication Date Dec 6, 2019
Publication Date May 31, 2020
Deposit Date Dec 10, 2019
Publicly Available Date Dec 6, 2020
Journal Journal of Computer and System Sciences
Print ISSN 0022-0000
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 109
Pages 1-21


You might also like

Downloadable Citations