Limit sets of stable cellular automata

DOI10.1017/ETDS.2013.72MaRDI QIDQ5262237zbMATHOpenAlexFDO

Authors Alexis Ballier

Publication date 13 July 2015

Published in Ergodic Theory and Dynamical Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.3790

zbMATH Keywords

cellular automatasofic shiftsymbolic dynamicssteady maps

Mathematics Subject Classification ID

Symbolic dynamics (37B10) Dynamical aspects of cellular automata (37B15)

Abstract: We study limit sets of stable cellular automata standing from a symbolic dynamics point of view where they are a special case of sofic shifts admitting a steady epimorphism. We prove that there exists a right-closing almost-everywhere steady factor map from one irreducible sofic shift onto another one if and only if there exists such a map from the domain onto the minimal right-resolving cover of the image. We define right-continuing almost-everywhere steady maps and prove that there exists such a steady map between two sofic shifts if and only if there exists a factor map from the domain onto the minimal right-resolving cover of the image. In terms of cellular automata, this translates into: A sofic shift can be the limit set of a stable cellular automaton with a right-closing almost-everywhere dynamics onto its limit set if and only if it is the factor of a fullshift and there exists a right- closing almost-everywhere factor map from the sofic shift onto its minimal right- resolving cover. A sofic shift can be the limit set of a stable cellular automaton reaching its limit set with a right-continuing almost-everywhere factor map if and only if it is the factor of a fullshift and there exists a factor map from the sofic shift onto its minimal right-resolving cover. Finally, as a consequence of the previous results, we provide a characterization of the Almost of Finite Type shifts (AFT) in terms of a property of steady maps that have them as range.

Recommendations

• Limit sets of stable and unstable cellular automata
• On the sofic limit sets of cellular automata
• Publication:4890470
• Limit sets of cellular automata associated to probability measures
• On stable and unstable limit sets of finite families of cellular automata

Cites work

• An Introduction to Symbolic Dynamics and Coding
• Core dimension group constraints for factors of sofic shifts
• Decompositions of finite-to-one factor maps
• Endomorphisms and automorphisms of the shift dynamical system
• Lifting covers of sofic shifts
• On the existence of open and bi-continuing codes
• On the sofic limit sets of cellular automata
• Putnam's resolving maps in dimension zero
• Resolving factor maps for shifts of finite type with equal entropy
• Shift equivalence and the Jordan form away from zero
• Sofic systems and encoding data
• Sofic systems and graphs
• Weak equivalence for shifts of finite type

Cited in

(12)

• Inferring the Limit Behavior of Some Elementary Cellular Automata
• An atlas of limit set dynamics for asynchronous elementary cellular automata
• Suberesolving codes
• scientific article; zbMATH DE number 2041501 (Why is no real title available?)
• scientific article; zbMATH DE number 919618 (Why is no real title available?)
• Limit sets of stable and unstable cellular automata
• On the sofic limit sets of cellular automata
• scientific article; zbMATH DE number 270137 (Why is no real title available?)
• \(\mu\)-limit sets of cellular automata from a computational complexity perspective
• On semi-open codes and bi-continuing almost everywhere codes
• scientific article; zbMATH DE number 4070371 (Why is no real title available?)
• Limit behaviour of \(\mu\)-equicontinuous cellular automata

This page was built for publication: Limit sets of stable cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5262237)