Skip to Main content Skip to Navigation
Conference papers

On Dynamical Complexity of Surjective Ultimately Right-Expansive Cellular Automata

Abstract : 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.
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-01824870
Contributor : Hal Ifip <>
Submitted on : Wednesday, June 27, 2018 - 4:37:33 PM
Last modification on : Wednesday, August 29, 2018 - 11:02:02 AM
Document(s) archivé(s) le : Thursday, September 27, 2018 - 2:52:08 AM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2021-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Joonatan Jalonen, Jarkko Kari. On Dynamical Complexity of Surjective Ultimately Right-Expansive Cellular Automata. 24th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2018, Ghent, Belgium. pp.57-71, ⟨10.1007/978-3-319-92675-9_5⟩. ⟨hal-01824870⟩

Share

Metrics

Record views

312