Towards a Rice Theorem on Traces of Cellular Automata

Julien Cervelle; Pierre Guillon

Towards a Rice Theorem on Traces of Cellular Automata

Julien Cervelle ¹ Pierre Guillon ¹

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

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.

Document type :

Conference papers

Domain :

Computer Science [cs] / Data Structures and Algorithms [cs.DS]

Complete list of metadatas

Cited literature [12 references] Display Hide Download

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 : Friday, May 10, 2019 - 1:44:06 PM
Long-term archiving on : Tuesday, November 13, 2012 - 3:00:40 PM

hal.pdf

Files produced by the author(s)

Towards a Rice Theorem on Traces of Cellular Automata

File

Identifiers

Collections

Citation

Export

Metrics

185

127

Contact

Towards a Rice Theorem on Traces of Cellular Automata

File

Identifiers

Collections

Citation

Export

Share

Metrics

185

127

Contact