https://hal.inria.fr/hal-01824870Jalonen, JoonatanJoonatanJalonenUniversity of TurkuKari, JarkkoJarkkoKariUniversity of TurkuOn Dynamical Complexity of Surjective Ultimately Right-Expansive Cellular AutomataHAL CCSD2018[INFO] Computer Science [cs]Ifip, HalJan M. BaetensMartin Kutrib2018-06-27 16:37:332018-08-29 11:02:022018-06-27 16:40:14enConference papershttps://hal.inria.fr/hal-01824870/document10.1007/978-3-319-92675-9_5application/pdf1We 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.