Limit sets of stable cellular automata

DOI10.1017/ETDS.2013.72zbMATH Open1355.37025arXiv1301.3790OpenAlexW3101493161MaRDI QIDQ5262237FDOQ5262237

Authors: Alexis Ballier 

Publication date: 13 July 2015

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

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.

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

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

zbMATH Keywords

cellular automatasofic shiftsymbolic dynamicssteady maps

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

• An atlas of limit set dynamics for asynchronous elementary cellular automata
• Title not available (Why is that?)
• Limit behaviour of \(\mu\)-equicontinuous cellular automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• \(\mu\)-limit sets of cellular automata from a computational complexity perspective
• Limit sets of stable and unstable cellular automata
• On the sofic limit sets of cellular automata
• Title not available (Why is that?)
• On semi-open codes and bi-continuing almost everywhere codes
• Inferring the Limit Behavior of Some Elementary Cellular Automata
• Suberesolving codes

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)