Hard Asymptotic Sets for One-Dimensional Cellular Automata

2013/07/18 by Ville Salo, Salo, Ville
Computer Science · Mathematics · #Computational Complexity (cs.CC) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #cs.CC #cs.FL #math.DS

paper · pdf · doi:10.48550/arxiv.1307.4910

arxiv created 2013/07/18 · arxiv updated 2013/07/19

Abstract

We prove that the (language of the) asymptotic set (and the nonwandering set) of a one-dimensional cellular automaton can be \SIGMA¹₁-hard. We do not go into much detail, since the constructions are relatively standard.

Related

• μ-Limit Sets of Cellular Automata from a Computational Complexity Perspective
• Arithmetical Complexity of the Language of Generic Limit Sets of Cellular Automata
• Mathematical Physics of Cellular Automata
• Descriptive Complexity of Sensitivity of Cellular Automata
• Generically Nilpotent Cellular Automata