A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Descriptive Complexity of Sensitivity of Cellular Automata
Tekijät: Favereau, Tom; Salo, Ville
Toimittaja: Riva, Sara; Richard, Adrien
Konferenssin vakiintunut nimi: International Workshop on Cellular Automata and Discrete Complex Systems
Kustantaja: Springer Science and Business Media Deutschland GmbH
Julkaisuvuosi: 2025
Lehti: Lecture Notes in Computer Science
Kokoomateoksen nimi: Cellular Automata and Discrete Complex Systems: 31st IFIP WG 1.5 International Workshop, AUTOMATA 2025, Lille, France, June 30 – July 2, 2025, Proceedings
Vuosikerta: 15831
Aloitussivu: 123
Lopetussivu: 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
Julkaisun avoimuus kirjaamishetkellä: Ei avoimesti saatavilla
Julkaisukanavan avoimuus : Ei avoin julkaisukanava
Verkko-osoite: 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.
