A4 Article in conference proceedings
On dynamical complexity of surjective ultimately right-expansive cellular automata

List of Authors: Joonatan Jalonen, Jarkko Kari
Publisher: Springer Verlag
Publication year: 2018
Journal: Lecture Notes in Computer Science
Book title *: Cellular Automata and Discrete Complex Systems
Journal name in source: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume number: 10875
ISBN: 978-3-319-92674-2
eISBN: 978-3-319-92675-9
ISSN: 0302-9743


We prove that surjective ultimately right-expansive cellular automata over full shifts are chain-transitive. This immediately implies Boyle’s result that expansive cellular automata are chain-transitive. This means that the chain-recurrence assumption can be dropped from Nasu’s result that surjective ultimately right-expansive cellular automata with right-sided neighborhoods have the pseudo-orbit tracing property, which also implies that the (canonical) trace subshift is sofic. We also provide a theorem with a simple proof that comprises many known results including aforementioned result by Nasu. Lastly we show that there exists a right-expansive reversible cellular automaton that has a non-sofic trace and thus does not have the pseudo-orbit tracing property. In this paper we only consider cellular automata over full shifts, while both Nasu and Boyle obtain their results over more general shift spaces.

Downloadable publication

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.

Last updated on 2019-29-01 at 10:44