Idempotent cellular automata and their natural order
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914840566562816 |
|---|---|
| author | Castillo-Ramirez, Alonso Magaña-Chavez, Maria G. Veliz-Quintero, Eduardo |
| author_facet | Castillo-Ramirez, Alonso Magaña-Chavez, Maria G. Veliz-Quintero, Eduardo |
| contents | Motivated by the search for idempotent cellular automata (CA), we study CA that act almost as the identity unless they read a fixed pattern $p$. We show that constant and symmetrical patterns always produce idempotent CA, and we characterize the quasi-constant patterns that produce idempotent CA. Our results are valid for CA over an arbitrary group $G$. Moreover, we study the semigroup theoretic natural partial order defined on idempotent CA. If $G$ is infinite, we prove that there is an infinite independent set of idempotent CA, and if $G$ has an element of infinite order, we prove that there is an infinite increasing chain of idempotent CA. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_09593 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Idempotent cellular automata and their natural order Castillo-Ramirez, Alonso Magaña-Chavez, Maria G. Veliz-Quintero, Eduardo Group Theory Formal Languages and Automata Theory Cellular Automata and Lattice Gases Motivated by the search for idempotent cellular automata (CA), we study CA that act almost as the identity unless they read a fixed pattern $p$. We show that constant and symmetrical patterns always produce idempotent CA, and we characterize the quasi-constant patterns that produce idempotent CA. Our results are valid for CA over an arbitrary group $G$. Moreover, we study the semigroup theoretic natural partial order defined on idempotent CA. If $G$ is infinite, we prove that there is an infinite independent set of idempotent CA, and if $G$ has an element of infinite order, we prove that there is an infinite increasing chain of idempotent CA. |
| title | Idempotent cellular automata and their natural order |
| topic | Group Theory Formal Languages and Automata Theory Cellular Automata and Lattice Gases |
| url | https://arxiv.org/abs/2401.09593 |