2007/03/08 by Cervelle, Julien, Formenti, Enrico, Guillon, Pierre · 1 citation
#37B15 #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.math/0703241
The trace subshift of a cellular automaton is the subshift of all possible columns that may appear in a space-time diagram, ie the infinite sequence of states of a particular cell of a configuration; in the language of symbolic dynamics one says that it is a factor system. In this paper we study conditions for a sofic subshift to be the trace of a cellular automaton.