 |
HAL UPEC - UPEM Portal |  |
 |
Conference papers
Towards a Rice Theorem on Traces of Cellular Automata
Abstract : The trace subshift of a cellular automaton is the subshift of all possible columns that may appear in a space-time diagram. We prove the undecidability of a rather large class of problems over trace subshifts of cellular automata.
Cited literature [12 references]
https://hal-upec-upem.archives-ouvertes.fr/hal-00620284
Contributor : Pierre Guillon <>
Submitted on : Monday, October 3, 2011 - 2:01:59 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Long-term archiving on: : Tuesday, November 13, 2012 - 3:00:40 PM
Contributor : Pierre Guillon <>
Submitted on : Monday, October 3, 2011 - 2:01:59 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Long-term archiving on: : Tuesday, November 13, 2012 - 3:00:40 PM
File
hal.pdf
Files produced by the author(s)