Invertible Linear Cellular Automata over Zm: Algorithmic and Dynamical Aspects

Giovanni Manzini; Luciano Margara

doi:10.1006/jcss.1997.1535

Invertible Linear Cellular Automata over Z_m: Algorithmic and Dynamical Aspects

Giovanni Manzini
, Luciano Margara

Research output: Contribution to journal › Article › peer-review

Abstract

We give an explicit and efficiently computable formula for the inverse of D-dimensional linear cellular automata over Z_m (D≥ 1, m ≥ 2). We use this formula to get an easy-to-check necessary and sufficient condition for an invertible one-dimensional linear CA to be expansive, and we prove that this condition is equivalent to topological transitivity.

Original language	English
Pages (from-to)	60-67
Number of pages	8
Journal	Journal of Computer and System Sciences
Volume	56
Issue number	1
DOIs	https://doi.org/10.1006/jcss.1997.1535
Publication status	Published - Feb 1998
Externally published	Yes

Access to Document

10.1006/jcss.1997.1535

Cite this

@article{38272bc015ce48aeb3efa34765b1ffcf,

title = "Invertible Linear Cellular Automata over Zm: Algorithmic and Dynamical Aspects",

abstract = "We give an explicit and efficiently computable formula for the inverse of D-dimensional linear cellular automata over Zm (D≥ 1, m ≥ 2). We use this formula to get an easy-to-check necessary and sufficient condition for an invertible one-dimensional linear CA to be expansive, and we prove that this condition is equivalent to topological transitivity.",

author = "Giovanni Manzini and Luciano Margara",

year = "1998",

month = feb,

doi = "10.1006/jcss.1997.1535",

language = "English",

volume = "56",

pages = "60--67",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Invertible Linear Cellular Automata over Zm

T2 - Algorithmic and Dynamical Aspects

AU - Manzini, Giovanni

AU - Margara, Luciano

PY - 1998/2

Y1 - 1998/2

N2 - We give an explicit and efficiently computable formula for the inverse of D-dimensional linear cellular automata over Zm (D≥ 1, m ≥ 2). We use this formula to get an easy-to-check necessary and sufficient condition for an invertible one-dimensional linear CA to be expansive, and we prove that this condition is equivalent to topological transitivity.

AB - We give an explicit and efficiently computable formula for the inverse of D-dimensional linear cellular automata over Zm (D≥ 1, m ≥ 2). We use this formula to get an easy-to-check necessary and sufficient condition for an invertible one-dimensional linear CA to be expansive, and we prove that this condition is equivalent to topological transitivity.

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

U2 - 10.1006/jcss.1997.1535

DO - 10.1006/jcss.1997.1535

M3 - Article

SN - 0022-0000

VL - 56

SP - 60

EP - 67

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 1

ER -

Invertible Linear Cellular Automata over Z_m: Algorithmic and Dynamical Aspects

Abstract

Access to Document

Other files and links

Fingerprint

Cite this