On ergodic linear cellular automata over Zm

Gianpiero Cattaneo; Enrico Formenti; Giovanni Manzini; Luciano Margara

doi:10.1007/bfb0023478

On ergodic linear cellular automata over Z_m

Gianpiero Cattaneo, Enrico Formenti, Giovanni Manzini, Luciano Margara

Risultato della ricerca: Capitolo in libro/report/atti di convegno › Contributo a conferenza › peer review

Abstract

We study the ergodic behavior of linear cellular automata over Z_m. The main contribution of this paper is an easy-to-check necessary and sufficient condition for a linear cellular automaton over Z_m to be ergodic. We prove that, for general cellular automata, ergodicity is equivalent to topological chaos (transitivity and sensitivity to initial conditions). Finally we prove that linear CA over Z_p with p prime have dense periodic orbits.

Lingua originale	Inglese
Titolo della pubblicazione ospite	STACS 1997 - 14th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
Editor	Rudiger Reischuk, Michel Morvan
Editore	Springer Verlag
Pagine	427-438
Numero di pagine	12
ISBN (stampa)	9783540626169
DOI	https://doi.org/10.1007/bfb0023478
Stato di pubblicazione	Pubblicato - 1997
Pubblicato esternamente	Sì
Evento	14th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1997 - Lubeck, Germany Durata: 27 feb 1997 → 1 mar 1997

Serie di pubblicazioni

Nome	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1200
ISSN (stampa)	0302-9743
ISSN (elettronico)	1611-3349

???event.eventtypes.event.conference???

???event.eventtypes.event.conference???	14th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1997
Paese/Territorio	Germany
Città	Lubeck
Periodo	27/02/97 → 1/03/97

Accesso al documento

10.1007/bfb0023478

Altri file e collegamenti

Link to publication in Scopus

Cita questo

Cattaneo, G., Formenti, E., Manzini, G., & Margara, L. (1997). On ergodic linear cellular automata over Z_m. In R. Reischuk, & M. Morvan (Edd.), STACS 1997 - 14th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings (pagg. 427-438). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1200). Springer Verlag. https://doi.org/10.1007/bfb0023478

Cattaneo, Gianpiero ; Formenti, Enrico ; Manzini, Giovanni et al. / On ergodic linear cellular automata over Z_m. STACS 1997 - 14th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. curatore / Rudiger Reischuk ; Michel Morvan. Springer Verlag, 1997. pagg. 427-438 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7f28bcfda14f438095a7cdf3fa0638f9,

title = "On ergodic linear cellular automata over Zm",

abstract = "We study the ergodic behavior of linear cellular automata over Zm. The main contribution of this paper is an easy-to-check necessary and sufficient condition for a linear cellular automaton over Zm to be ergodic. We prove that, for general cellular automata, ergodicity is equivalent to topological chaos (transitivity and sensitivity to initial conditions). Finally we prove that linear CA over Zp with p prime have dense periodic orbits.",

author = "Gianpiero Cattaneo and Enrico Formenti and Giovanni Manzini and Luciano Margara",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1997.; 14th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1997 ; Conference date: 27-02-1997 Through 01-03-1997",

year = "1997",

doi = "10.1007/bfb0023478",

language = "English",

isbn = "9783540626169",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "427--438",

editor = "Rudiger Reischuk and Michel Morvan",

booktitle = "STACS 1997 - 14th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings",

address = "Germany",

}

Cattaneo, G, Formenti, E, Manzini, G & Margara, L 1997, On ergodic linear cellular automata over Z_m. in R Reischuk & M Morvan (edd.), STACS 1997 - 14th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1200, Springer Verlag, pagg. 427-438, 14th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1997, Lubeck, Germany, 27/02/97. https://doi.org/10.1007/bfb0023478

On ergodic linear cellular automata over Z_m. / Cattaneo, Gianpiero; Formenti, Enrico; Manzini, Giovanni et al.
STACS 1997 - 14th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. a cura di / Rudiger Reischuk; Michel Morvan. Springer Verlag, 1997. pag. 427-438 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1200).

Risultato della ricerca: Capitolo in libro/report/atti di convegno › Contributo a conferenza › peer review

TY - GEN

T1 - On ergodic linear cellular automata over Zm

AU - Cattaneo, Gianpiero

AU - Formenti, Enrico

AU - Manzini, Giovanni

AU - Margara, Luciano

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1997.

PY - 1997

Y1 - 1997

N2 - We study the ergodic behavior of linear cellular automata over Zm. The main contribution of this paper is an easy-to-check necessary and sufficient condition for a linear cellular automaton over Zm to be ergodic. We prove that, for general cellular automata, ergodicity is equivalent to topological chaos (transitivity and sensitivity to initial conditions). Finally we prove that linear CA over Zp with p prime have dense periodic orbits.

AB - We study the ergodic behavior of linear cellular automata over Zm. The main contribution of this paper is an easy-to-check necessary and sufficient condition for a linear cellular automaton over Zm to be ergodic. We prove that, for general cellular automata, ergodicity is equivalent to topological chaos (transitivity and sensitivity to initial conditions). Finally we prove that linear CA over Zp with p prime have dense periodic orbits.

UR - http://www.scopus.com/inward/record.url?scp=84949660101&partnerID=8YFLogxK

U2 - 10.1007/bfb0023478

DO - 10.1007/bfb0023478

M3 - Conference contribution

AN - SCOPUS:84949660101

SN - 9783540626169

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 427

EP - 438

BT - STACS 1997 - 14th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings

A2 - Reischuk, Rudiger

A2 - Morvan, Michel

PB - Springer Verlag

T2 - 14th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1997

Y2 - 27 February 1997 through 1 March 1997

ER -

Cattaneo G, Formenti E, Manzini G, Margara L. On ergodic linear cellular automata over Z_m. In Reischuk R, Morvan M, editor, STACS 1997 - 14th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Springer Verlag. 1997. pag. 427-438. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/bfb0023478