Complete simulation of automata networks

摘要

Consider a finite set A and n≥1. We study complete simulation of transformations of An, also known as automata networks. For m≥n, a transformation of Am is n-complete of size m if it may simulate every transformation of An 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 n+1. 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 An. 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.