This paper investigates a variant of cellular automata, namely νν-CA. Indeed, νν-CA are cellular automata which can have different local rules at each site of their lattice. The assignment of local rules to sites of the lattice completely characterizes νν-CA. In this paper, sets of assignments 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.

Dennunzio, A., Formenti, E., Provillard, J. (2013). Local rule distributions, language complexity and non-uniform cellular automata. THEORETICAL COMPUTER SCIENCE, 504, 38-51 [10.1016/j.tcs.2012.05.013].

Local rule distributions, language complexity and non-uniform cellular automata

DENNUNZIO, ALBERTO;
2013

Abstract

This paper investigates a variant of cellular automata, namely νν-CA. Indeed, νν-CA are cellular automata which can have different local rules at each site of their lattice. The assignment of local rules to sites of the lattice completely characterizes νν-CA. In this paper, sets of assignments 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.
Articolo in rivista - Articolo scientifico
Non uniform cellular automata; Bi-infinite words; ζ-rational languages
English
2013
504
38
51
none
Dennunzio, A., Formenti, E., Provillard, J. (2013). Local rule distributions, language complexity and non-uniform cellular automata. THEORETICAL COMPUTER SCIENCE, 504, 38-51 [10.1016/j.tcs.2012.05.013].
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/43524
Citazioni
  • Scopus 31
  • ???jsp.display-item.citation.isi??? 25
Social impact