Descriptive Complexity of Sensitivity of Cellular Automata
: Favereau, Tom; Salo, Ville
: Riva, Sara; Richard, Adrien
: International Workshop on Cellular Automata and Discrete Complex Systems
Publisher: Springer Science and Business Media Deutschland GmbH
: 2025
Lecture Notes in Computer Science
: Cellular Automata and Discrete Complex Systems: 31st IFIP WG 1.5 International Workshop, AUTOMATA 2025, Lille, France, June 30 – July 2, 2025, Proceedings
: 15831
: 123
: 138
: 978-3-032-01569-3
: 978-3-032-01570-9
: 0302-9743
: 1611-3349
DOI: https://doi.org/10.1007/978-3-032-01570-9_9
: https://doi.org/10.1007/978-3-032-01570-9_9
We study the computational complexity of determining whether a cellular automaton is sensitive to initial conditions. We show that this problem is Π20-complete in dimension 1 and Σ30-complete in dimension 2 and higher. This solves a question posed by Sablik and Theyssier.
