• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Cellular Automata Reversible over Limit Set

Siamak Taati, Cellular Automata Reversible over Limit Set. Special Issue, Automata 2005, 11th Workshop on Cellular AutomataJournal of Cellular Automata 2(2), 167-177, 2007.

Abstract:

Reversibility of dynamics is a fundamental feature of nature, as it is
currently believed that all physical processes are reversible in the
ultimate microscopic scale. In this paper, we consider cellular automata
(CA) whose dynamics are reversible when restricted to the limit set; i.e.,
those that obey reversibility in equilibrium.

We exploit standard topological and combinatorial arguments to show that the limit set, in this case, is a mixing subshift of finite type (SFT), and
is reached in finite time. In one dimensional case, any mixing SFT which
contains at least one homogeneous configuration, may arise this way.
We also discuss the decidability of two related algorithmic questions.

Files:

Full publication in PDF-format

BibTeX entry:

@ARTICLE{jTaati06a,
  title = {Cellular Automata Reversible over Limit Set},
  author = {Taati, Siamak},
  journal = {Special Issue, Automata 2005, 11th Workshop on Cellular AutomataJournal of Cellular Automata},
  volume = {2},
  number = {2},
  pages = {167-177},
  year = {2007},
  keywords = {Cellular Automata, Reversibility, Limit Set, Subshifts of Finite Type, Conservation Laws, Undecidability},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication