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.

P. Di Lena, L. Margara (2007). Computational Complexity of Dynamical Systems: the case of Cellular Automata. s.l : s.n.

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.
2007
Pre-proceedings of the 1st International Conference on Languages and Automata Theory and Application
211
222
P. Di Lena, L. Margara (2007). Computational Complexity of Dynamical Systems: the case of Cellular Automata. s.l : s.n.
P. Di Lena; L. Margara
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/41739
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 18
social impact