ν-CA are cellular automata which can have different local rules at each site of their lattice. Indeed, the spatial distribution of local rules completely characterizes ν-CA. In this paper, sets of distributions sharing some interesting properties are associated with languages of bi-infinite words. The complexity classes of these languages are investigated providing an initial rough classification of ν-CA. © 2012 Springer-Verlag.

Dennunzio, A., Formenti, E., Provillard, J. (2012). Computational Complexity of Rule Distributions of Non-uniform Cellular Automata. In Language and Automata Theory and Applications (pp.204-215) [10.1007/978-3-642-28332-1_18].

Computational Complexity of Rule Distributions of Non-uniform Cellular Automata

DENNUNZIO, ALBERTO;
2012

Abstract

ν-CA are cellular automata which can have different local rules at each site of their lattice. Indeed, the spatial distribution of local rules completely characterizes ν-CA. In this paper, sets of distributions sharing some interesting properties are associated with languages of bi-infinite words. The complexity classes of these languages are investigated providing an initial rough classification of ν-CA. © 2012 Springer-Verlag.
paper
Non uniform Cellular Automata, bi-infinite words
English
Language and Automata Theory and Applications - 6th International Conference, LATA 2012
2012
Language and Automata Theory and Applications
978-3-642-28332-1
2012
7183
204
215
none
Dennunzio, A., Formenti, E., Provillard, J. (2012). Computational Complexity of Rule Distributions of Non-uniform Cellular Automata. In Language and Automata Theory and Applications (pp.204-215) [10.1007/978-3-642-28332-1_18].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/10281/43533
Citazioni
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
Social impact