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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › 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.

Original language	English
Title of host publication	STACS 1997 - 14th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
Editors	Rudiger Reischuk, Michel Morvan
Publisher	Springer Verlag
Pages	427-438
Number of pages	12
ISBN (Print)	9783540626169
DOIs	https://doi.org/10.1007/bfb0023478
Publication status	Published - 1997
Externally published	Yes
Event	14th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1997 - Lubeck, Germany Duration: 27 Feb 1997 → 1 Mar 1997

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1200
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1997
Country/Territory	Germany
City	Lubeck
Period	27/02/97 → 1/03/97

Access to Document

10.1007/bfb0023478

Cite this

Cattaneo, G., Formenti, E., Manzini, G., & Margara, L. (1997). On ergodic linear cellular automata over Z_m. In R. Reischuk, & M. Morvan (Eds.), STACS 1997 - 14th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings (pp. 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. editor / Rudiger Reischuk ; Michel Morvan. Springer Verlag, 1997. pp. 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 (eds), 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, pp. 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. ed. / Rudiger Reischuk; Michel Morvan. Springer Verlag, 1997. p. 427-438 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1200).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › 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 - https://www.scopus.com/pages/publications/84949660101

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, editors, STACS 1997 - 14th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Springer Verlag. 1997. p. 427-438. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/bfb0023478