2015/04/01 by Bridoux, Florian, Castillo-Ramirez, Alonso, Gadouleau, Maximilien
#Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Group Theory (math.GR)
paper · doi:10.48550/arxiv.1504.00169
Consider a finite set A and an integer n ≥ 1. This paper studies the concept of complete simulation in the context of semigroups of transformations of An, also known as finite state-homogeneous 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 coordinate (or register) at a time. Using tools from memoryless computation, it is established that there is no n-complete transformation of size n, but there is such a transformation of size n+1. By studying the the time of simulation of various n-complete transformations, it is conjectured that the maximal time of simulation of any n-complete transformation is at least 2n. A transformation of Am is sequentially n-complete of size m if it may sequentially simulate every finite sequence of transformations of An; in this case, minimal examples and bounds for the size and time of simulation are determined. It is also shown that there is no n-complete transformation that updates all the registers in parallel, but that there exists a sequentally n-complete transformation that updates all but one register in parallel. This illustrates the strengths and weaknesses of parallel models of computation, such as cellular automata.