%0 Conference Proceedings
%T On Dynamical Complexity of Surjective Ultimately Right-Expansive Cellular Automata
%+ University of Turku
%A Jalonen, Joonatan
%A Kari, Jarkko
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 24th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA)
%C Ghent, Belgium
%Y Jan M. Baetens
%Y Martin Kutrib
%I Springer International Publishing
%3 Cellular Automata and Discrete Complex Systems
%V LNCS-10875
%P 57-71
%8 2018-06-20
%D 2018
%R 10.1007/978-3-319-92675-9_5
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.5
%2 https://inria.hal.science/hal-01824870/document
%2 https://inria.hal.science/hal-01824870/file/469010_1_En_5_Chapter.pdf
%L hal-01824870
%U https://inria.hal.science/hal-01824870
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG1-5
%~ IFIP-AUTOMATA
%~ IFIP-LNCS-10875