A4 Refereed article in a conference publication
Descriptive Complexity of Sensitivity of Cellular Automata
Authors: Favereau, Tom; Salo, Ville
Editors: Riva, Sara; Richard, Adrien
Conference name: International Workshop on Cellular Automata and Discrete Complex Systems
Publisher: Springer Science and Business Media Deutschland GmbH
Publication year: 2025
Journal: Lecture Notes in Computer Science
Book title : Cellular Automata and Discrete Complex Systems: 31st IFIP WG 1.5 International Workshop, AUTOMATA 2025, Lille, France, June 30 – July 2, 2025, Proceedings
Volume: 15831
First page : 123
Last page: 138
ISBN: 978-3-032-01569-3
eISBN: 978-3-032-01570-9
ISSN: 0302-9743
eISSN: 1611-3349
DOI: https://doi.org/10.1007/978-3-032-01570-9_9
Publication's open availability at the time of reporting: No Open Access
Publication channel's open availability : No Open Access publication channel
Web address : 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.
