Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2020

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: pseudo-orbit tracing property

Sortuj według:

Ogranicz wyniki do:

On Expansivity and Pseudo-Orbit Tracing Property for Cellular Automata

Jalonen Joonatan, Kari Jarkko

Fundamenta Informaticae

2020

Vol. 171, nr 1-4

239--259

Ultimate expansivity extends concepts of expansivity and positive expansivity. We consider one-sided variants of ultimate expansivity and pseudo-orbit tracing property (also known as the shadowing property) for surjective one-dimensional cellular automata. We show that ultimately right (or left) expansive surjective cellular automata are chain-transitive; this improves a result by Boyle that expansive reversible cellular automata are chain-transitive. We then use this to show that left-sided pseudo-orbit tracing property and right-sided ultimate expansivity together imply pseudo-orbit tracing property for surjective cellular automata. This reproves some known results, most notably some of Nasu’s. Our result improves Nasu’s result by dropping an assumption of chain-recurrence, however, we remark that this improvement can also be achieved using the Poincaré recurrence theorem. The pseudo-orbit tracing property implies that the trace subshifts of the cellular automaton are sofic shifts. We end by mentioning that among reversible cellular automata over full shifts we have examples of right expansive cellular automata with non-sofic traces, as well as examples of cellular automata with left pseudo-orbit tracing property but non-sofic traces, illustrating that neither assumption can be dropped from the theorem mentioned above. This paper is a generalized and improved version of a conference paper presented in AUTOMATA 2018.