Arithmetical complexity of the language of generic limit sets of cellular automata

DOI10.1016/j.jcss.2023.01.002OpenAlexW4317932702MaRDI QIDQ2689368

Solène J. Esnay, Ilkka Törmä, Alonso Núñez

Publication date: 10 March 2023

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

attractorscellular automatasubshiftsarithmetical complexitytopological dynamical systemsgeneric limit sets

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) Dynamical aspects of cellular automata (37B15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\mu\)-limit sets of cellular automata from a computational complexity perspective
• Directional dynamics along arbitrary curves in cellular automata
• Completing codes in a sofic shift
• On the concept of attractor
• Rice's theorem for the limit sets of cellular automata
• Some properties of cellular automata with equicontinuity points
• Complexity of generic limit sets of cellular automata
• On the Limit Sets of Cellular Automata
• Limit Sets of Stable and Unstable Cellular Automata
• The chain relation in sofic subshifts
• The Nilpotency Problem of One-Dimensional Cellular Automata
• Characterization of sets of limit measures of a cellular automaton iterated on a random configuration
• An Introduction to Symbolic Dynamics and Coding
• The generic limit set of cellular automata
• Uniqueness Theorems for Periodic Functions
• Limit sets of cellular automata associated to probability measures