Ergodicity, transitivity, and regularity for linear cellular automata over Zm

Gianpiero Cattaneo; Enrico Formenti; Giovanni Manzini; Luciano Margara

doi:10.1016/S0304-3975(98)00005-X

Ergodicity, transitivity, and regularity for linear cellular automata over Z_m

Gianpiero Cattaneo, Enrico Formenti, Giovanni Manzini, Luciano Margara

Risultato della ricerca: Contributo su rivista › Articolo in rivista › peer review

Abstract

We study the dynamical behavior of D-dimensional linear cellular automata over Z_m. We provide an easy-to-check necessary and sufficient condition for a D-dimensional linear cellular automata over Z_m to be ergodic and topologically transitive. As a byproduct, we get that for linear cellular automata ergodicity is equivalent to topological transitivity. Finally, we prove that for 1-dimensional linear cellular automata over Z_m, regularity (denseness of periodic orbits) is equivalent to surjectivity.

Lingua originale	Inglese
pagine (da-a)	147-164
Numero di pagine	18
Rivista	Theoretical Computer Science
Volume	233
Numero di pubblicazione	1-2
DOI	https://doi.org/10.1016/S0304-3975(98)00005-X
Stato di pubblicazione	Pubblicato - 28 feb 2000
Pubblicato esternamente	Sì

Accesso al documento

10.1016/S0304-3975(98)00005-X

Altri file e collegamenti

Link to publication in Scopus

Cita questo

@article{04762d10c5a64f9d9603fe9647371513,

title = "Ergodicity, transitivity, and regularity for linear cellular automata over Zm",

abstract = "We study the dynamical behavior of D-dimensional linear cellular automata over Zm. We provide an easy-to-check necessary and sufficient condition for a D-dimensional linear cellular automata over Zm to be ergodic and topologically transitive. As a byproduct, we get that for linear cellular automata ergodicity is equivalent to topological transitivity. Finally, we prove that for 1-dimensional linear cellular automata over Zm, regularity (denseness of periodic orbits) is equivalent to surjectivity.",

keywords = "Cellular automata, Discrete time dynamical systems, Ergodicity, Topological transitivity",

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

year = "2000",

month = feb,

day = "28",

doi = "10.1016/S0304-3975(98)00005-X",

language = "English",

volume = "233",

pages = "147--164",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1-2",

}

TY - JOUR

T1 - Ergodicity, transitivity, and regularity for linear cellular automata over Zm

AU - Cattaneo, Gianpiero

AU - Formenti, Enrico

AU - Manzini, Giovanni

AU - Margara, Luciano

PY - 2000/2/28

Y1 - 2000/2/28

N2 - We study the dynamical behavior of D-dimensional linear cellular automata over Zm. We provide an easy-to-check necessary and sufficient condition for a D-dimensional linear cellular automata over Zm to be ergodic and topologically transitive. As a byproduct, we get that for linear cellular automata ergodicity is equivalent to topological transitivity. Finally, we prove that for 1-dimensional linear cellular automata over Zm, regularity (denseness of periodic orbits) is equivalent to surjectivity.

AB - We study the dynamical behavior of D-dimensional linear cellular automata over Zm. We provide an easy-to-check necessary and sufficient condition for a D-dimensional linear cellular automata over Zm to be ergodic and topologically transitive. As a byproduct, we get that for linear cellular automata ergodicity is equivalent to topological transitivity. Finally, we prove that for 1-dimensional linear cellular automata over Zm, regularity (denseness of periodic orbits) is equivalent to surjectivity.

KW - Cellular automata

KW - Discrete time dynamical systems

KW - Ergodicity

KW - Topological transitivity

UR - https://www.scopus.com/pages/publications/0346737903

U2 - 10.1016/S0304-3975(98)00005-X

DO - 10.1016/S0304-3975(98)00005-X

M3 - Article

SN - 0304-3975

VL - 233

SP - 147

EP - 164

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2