We study the subshift behavior of one dimensional cellular automata and we show how to associate to any subshift of finite type a cellular automaton which contains it. The relationships between some topological properties of subshifts and the behavior of the related languages are investigated. In particular we focus our attention to the notion of full transitivity. We characterize the language related to a full transitive subshift extending the notion of irreducibility.

Cattaneo, G., Dennunzio, A. (2005). Subshift Behavior of Cellular Automata. Topological Properties and Related Languages. In Machines, Computations, and Universality (pp.140-152). Springer [10.1007/b106980].

Subshift Behavior of Cellular Automata. Topological Properties and Related Languages

CATTANEO, GIANPIERO;DENNUNZIO, ALBERTO
2005

Abstract

We study the subshift behavior of one dimensional cellular automata and we show how to associate to any subshift of finite type a cellular automaton which contains it. The relationships between some topological properties of subshifts and the behavior of the related languages are investigated. In particular we focus our attention to the notion of full transitivity. We characterize the language related to a full transitive subshift extending the notion of irreducibility.
paper
cellular automata, formal languages, subshifts
English
International Conference on Machines, Computations and Universality (MCU 2004)
2004
Machines, Computations, and Universality
978-3-540-31834-7
2005
3354
140
152
none
Cattaneo, G., Dennunzio, A. (2005). Subshift Behavior of Cellular Automata. Topological Properties and Related Languages. In Machines, Computations, and Universality (pp.140-152). Springer [10.1007/b106980].
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/14990
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
Social impact