Ultimate Traces of Cellular Automata - Computer Science > Formal Languages and Automata TheoryReport as inadecuate




Ultimate Traces of Cellular Automata - Computer Science > Formal Languages and Automata Theory - Download this document for free, or read online. Document in PDF available to download.

Abstract: A cellular automaton CA is a parallel synchronous computing model, whichconsists in a juxtaposition of finite automata cells whose state evolvesaccording to that of their neighbors. Its trace is the set of infinite wordsrepresenting the sequence of states taken by some particular cell. In thispaper we study the ultimate trace of CA and partial CA a CA restricted to aparticular subshift. The ultimate trace is the trace observed after a longtime run of the CA. We give sufficient conditions for a set of infinite wordsto be the trace of some CA and prove the undecidability of all properties overtraces that are stable by ultimate coincidence.



Author: Julien Cervelle, Enrico Formenti, Pierre Guillon

Source: https://arxiv.org/







Related documents