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

Research output: Contribution to journal › Article › 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.

Original language	English
Pages (from-to)	147-164
Number of pages	18
Journal	Theoretical Computer Science
Volume	233
Issue number	1-2
DOIs	https://doi.org/10.1016/S0304-3975(98)00005-X
Publication status	Published - 28 Feb 2000
Externally published	Yes

Keywords

Cellular automata
Discrete time dynamical systems
Ergodicity
Topological transitivity

Access to Document

10.1016/S0304-3975(98)00005-X

Cite this

@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

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this