Vertaisarvioitu artikkeli konferenssijulkaisussa (A4)

On dynamical complexity of surjective ultimately right-expansive cellular automata




Julkaisun tekijät: Joonatan Jalonen, Jarkko Kari

Konferenssin vakiintunut nimi: International Workshop on Cellular Automata and Discrete Complex Systems

Kustantaja: Springer Verlag

Julkaisuvuosi: 2018

Journal: Lecture Notes in Computer Science

Kirjan nimi *: Cellular Automata and Discrete Complex Systems

Tietokannassa oleva lehden nimi: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Volyymi: 10875

Sivujen määrä: 15

ISBN: 978-3-319-92674-2

eISBN: 978-3-319-92675-9

ISSN: 0302-9743

DOI: http://dx.doi.org/10.1007/978-3-319-92675-9_5

Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/35726676


Tiivistelmä

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.


Ladattava julkaisu

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.




Last updated on 2022-07-04 at 17:00