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

DOI10.1016/J.JCSS.2023.01.002MaRDI QIDQ2689368zbMATH OpenOpenAlexFDO

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

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

arithmetical complexityattractorscellular automatageneric limit setssubshiftstopological dynamical systems

Mathematics Subject Classification ID

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

Recommendations

• The generic limit set of cellular automata
• Complexity of limit language of the elementary cellular automaton of Rule 22
• The complexity of limit languages of cellular automata: An example
• On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures
• \(\mu\)-limit sets of cellular automata from a computational complexity perspective

Cites work

• \(\mu\)-limit sets of cellular automata from a computational complexity perspective
• An Introduction to Symbolic Dynamics and Coding
• Cellular automata reversible over limit set
• Characterization of sets of limit measures of a cellular automaton iterated on a random configuration
• Completing codes in a sofic shift
• Complexity of generic limit sets of cellular automata
• Directional dynamics along arbitrary curves in cellular automata
• scientific article; zbMATH DE number 412251 (Why is no real title available?)
• scientific article; zbMATH DE number 4070371 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• Limit sets of cellular automata associated to probability measures
• Limit sets of stable and unstable cellular automata
• On the concept of attractor
• On the Limit Sets of Cellular Automata
• Rice's theorem for the limit sets of cellular automata
• Some properties of cellular automata with equicontinuity points
• The chain relation in sofic subshifts
• The generic limit set of cellular automata
• The Nilpotency Problem of One-Dimensional Cellular Automata
• Uniqueness Theorems for Periodic Functions

Cited in

(9)

• Complexity of generic limit sets of cellular automata
• scientific article; zbMATH DE number 4070371 (Why is no real title available?)
• The generic limit set of cellular automata
• The complexity of limit languages of cellular automata: An example
• Arithmetical Complexity of the Language of Generic Limit Sets of Cellular Automata
• Extensions on the analysis of elementary cellular automata with process graphs
• Strong stochastic stability of cellular automata
• On the algorithmic descriptive complexity of attractors in topological dynamics
• Characterisation of the set of ground states of uniformly chaotic finite-range lattice models

This page was built for publication: Arithmetical complexity of the language of generic limit sets of cellular automata

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