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.
Document type :
Conference papers
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
Long-term archiving on: 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

289