Back to Search
Start Over
Idempotent cellular automata and their natural order
- Source :
- Theoretical Computer Science, vol. 1009, 12 September 2024, 114698
- Publication Year :
- 2024
-
Abstract
- 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.<br />Comment: 14 pages
Details
- Database :
- arXiv
- Journal :
- Theoretical Computer Science, vol. 1009, 12 September 2024, 114698
- Publication Type :
- Report
- Accession number :
- edsarx.2401.09593
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1016/j.tcs.2024.114698