CellularAutomatacanbeconsidereddiscretedynamicalsys- tems and at the same time a model of parallel computation. In this paper we investigate the connections between dynamical and computational properties of Cellular Automata. We propose a classification of Cellular Automata according to the language complexities which rise from the basins of attraction of subshift attractors and investigate the intersection classes between our classification and other three topological classifications of Cellular Automata. From the intersection classes we can derive necessary topological properties for a cellular automaton to be computationally universal.
Computational Complexity of Dynamical Systems: the case of Cellular Automata / P. Di Lena; L. Margara. - STAMPA. - (2007), pp. 211-222. (Intervento presentato al convegno International Conference on Language and Automata Theory and Applications tenutosi a Terragona, Spain nel March 29 - April 4 2007).
Computational Complexity of Dynamical Systems: the case of Cellular Automata
DI LENA, PIETRO;MARGARA, LUCIANO
2007
Abstract
CellularAutomatacanbeconsidereddiscretedynamicalsys- tems and at the same time a model of parallel computation. In this paper we investigate the connections between dynamical and computational properties of Cellular Automata. We propose a classification of Cellular Automata according to the language complexities which rise from the basins of attraction of subshift attractors and investigate the intersection classes between our classification and other three topological classifications of Cellular Automata. From the intersection classes we can derive necessary topological properties for a cellular automaton to be computationally universal.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
