On Dynamical Complexity of Surjective Ultimately Right-Expansive Cellular Automata - Archive ouverte HAL Access content directly
Conference Papers Year : 2018

On Dynamical Complexity of Surjective Ultimately Right-Expansive Cellular Automata

(1) , (1)
1
Joonatan Jalonen
  • Function : Author
  • PersonId : 1033837
Jarkko Kari

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.
Fichier principal
Vignette du fichier
469010_1_En_5_Chapter.pdf (2.89 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01824870 , version 1 (27-06-2018)

Licence

Attribution - CC BY 4.0

Identifiers

Cite

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⟩
83 View
40 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More