A study on the composition of elementary cellular automata
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915438370226176 |
|---|---|
| author | Castillo-Ramirez, Alonso Magaña-Chavez, Maria G. |
| author_facet | Castillo-Ramirez, Alonso Magaña-Chavez, Maria G. |
| contents | Elementary cellular automata (ECA) are one-dimensional discrete models of computation with a small memory set that have gained significant interest since the pioneer work of Stephen Wolfram, who studied them as time-discrete dynamical systems. Each of the 256 ECA is labeled as rule $X$, where $X$ is an integer between $0$ and $255$. An important property, that is usually overlooked in computational studies, is that the composition of any two one-dimensional cellular automata is again a one-dimensional cellular automaton. In this chapter, we begin a systematic study of the composition of ECA. Intuitively speaking, we shall consider that rule $X$ has low complexity if the compositions $X \circ Y$ and $Y \circ X$ have small minimal memory sets, for many rules $Y$. Hence, we propose a new classification of ECA based on the compositions among them. We also describe all semigroups of ECA (i.e., composition-closed sets of ECA) and analyze their basic structure from the perspective of semigroup theory. In particular, we determine that the largest semigroups of ECA have $9$ elements, and have a subsemigroup of order $8$ that is $\mathcal{R}$-trivial, property which has been recently used to define random walks and Markov chains over semigroups. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_02947 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A study on the composition of elementary cellular automata Castillo-Ramirez, Alonso Magaña-Chavez, Maria G. Cellular Automata and Lattice Gases Formal Languages and Automata Theory Elementary cellular automata (ECA) are one-dimensional discrete models of computation with a small memory set that have gained significant interest since the pioneer work of Stephen Wolfram, who studied them as time-discrete dynamical systems. Each of the 256 ECA is labeled as rule $X$, where $X$ is an integer between $0$ and $255$. An important property, that is usually overlooked in computational studies, is that the composition of any two one-dimensional cellular automata is again a one-dimensional cellular automaton. In this chapter, we begin a systematic study of the composition of ECA. Intuitively speaking, we shall consider that rule $X$ has low complexity if the compositions $X \circ Y$ and $Y \circ X$ have small minimal memory sets, for many rules $Y$. Hence, we propose a new classification of ECA based on the compositions among them. We also describe all semigroups of ECA (i.e., composition-closed sets of ECA) and analyze their basic structure from the perspective of semigroup theory. In particular, we determine that the largest semigroups of ECA have $9$ elements, and have a subsemigroup of order $8$ that is $\mathcal{R}$-trivial, property which has been recently used to define random walks and Markov chains over semigroups. |
| title | A study on the composition of elementary cellular automata |
| topic | Cellular Automata and Lattice Gases Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2305.02947 |