Sequence of states taken by one particular cell. In this paper, we resume our study of traces of cellular automata, that is to say the This dependency is given by a local rule which Of a fixed finite number of neighboring cells. Each cell updates its state depending on the states Lattice (or more generally, on any graph). Their ability to capture many features of natural phenomena increase their popularity in theĬomputer sciencists, mathematicians and physicians communities.Ī cellular automaton consists in finite state automata (cells) distributed on a regular Plex ones like transitivity, mixing or expansivity. Namical behaviors, from the most simple like nilpotency or equicontinuity to the more com. We give sufficient conditions for a set of infinite words to be the trace of some CA and prove the undecidability of all properties over traces that are stable by ultimate coincidence.Ĭellular automata are a formal computing model known to display many different dy. The ultimate trace is the trace observed after a long time run of the CA. In this paper we study the ultimate trace of CA and partial CA (a CA restricted to a particular subshift). Its trace is the set of infinite words representing the sequence of states taken by some particular cell. A cellular automaton (CA) is a parallel synchronous computing model, which consists in a juxtaposition of finite automata (cells) whose state evolves according to that of their neighbors. Blanco Encalada 2120, 8370459 Santiago, ChileĪbstract. Euclide B - BP 121, 06903 Sophia Antipolis Cedex, Franceģ DIM - CMM, UMI CNRS 2807, Universidad de Chile, Av. JULIEN CERVELLE 1 AND ENRICO FORMENTI 2 AND PIERRE GUILLON 3ġ Université Paris-Est, LACL, EA 4219, 61 Av du Général de Gaulle, 94010 Créteil Cedex, France E-mail address: Ģ Laboratoire I3S, Université de Nice-Sophia Antipolis, 2000, Rte des Lucioles - Les Algorithmes - bât. 155-166 ULTIMATE TRACES OF CELLULAR AUTOMATA Symposium on Theoretical Aspects of Computer Science 2010 (Nancy, France), pp.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |