Towards a Rice Theorem on Traces of Cellular Automata

Julien Cervelle 1 Pierre Guillon 1
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
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

File

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00620284, version 1

Collections

CNRS | UNIV-MLV | LIGM_ALGO | LIGM | ENPC | PARISTECH | UPEC-UPEM

Citation

Julien Cervelle, Pierre Guillon. Towards a Rice Theorem on Traces of Cellular Automata. 32th International Symposium on Mathematical Foundations of Computer Science (MFCS'07), Aug 2007, Český Krumlov, Czech Republic, Czech Republic. pp.310-319. ⟨hal-00620284⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

207

Files downloads

215

Contact

CCSD