Efficient Algorithms for Injectivity and Bounded Surjectivity of One-dimensional Nonlinear Cellular Automata
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913446141886464 |
|---|---|
| author | Wang, Chen Ma, Junchi Lin, Defu Chen, Weilin Wang, Chao |
| author_facet | Wang, Chen Ma, Junchi Lin, Defu Chen, Weilin Wang, Chao |
| contents | Nonlinear cellular automata are extensively used in simulations, image processing, cryptography, and so on. The determination of their fundamental properties, injectivity and surjectivity, related to information loss during the evolution, is necessary in various applications. Currently, people still use Amoroso's algorithms for injectivity and surjectivity determinations, but this incurs significant computational costs when applied to complex nonlinear cellular automata. We have optimized Amoroso's surjectivity algorithm, improving its operational efficiency greatly and extended its applicability to various boundaries. Furthermore, we have introduced new theorems and algorithms for determining injectivity, which offer substantial improvements over Amoroso's algorithm in both time and space. With these new algorithms, we are equipped to determine the properties of larger and more complex cellular automata, thereby employing more advanced cellular automata to achieve increasingly complex functionalities. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_03073 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Efficient Algorithms for Injectivity and Bounded Surjectivity of One-dimensional Nonlinear Cellular Automata Wang, Chen Ma, Junchi Lin, Defu Chen, Weilin Wang, Chao Data Structures and Algorithms 05C05, 68Q25, 68Q80 Nonlinear cellular automata are extensively used in simulations, image processing, cryptography, and so on. The determination of their fundamental properties, injectivity and surjectivity, related to information loss during the evolution, is necessary in various applications. Currently, people still use Amoroso's algorithms for injectivity and surjectivity determinations, but this incurs significant computational costs when applied to complex nonlinear cellular automata. We have optimized Amoroso's surjectivity algorithm, improving its operational efficiency greatly and extended its applicability to various boundaries. Furthermore, we have introduced new theorems and algorithms for determining injectivity, which offer substantial improvements over Amoroso's algorithm in both time and space. With these new algorithms, we are equipped to determine the properties of larger and more complex cellular automata, thereby employing more advanced cellular automata to achieve increasingly complex functionalities. |
| title | Efficient Algorithms for Injectivity and Bounded Surjectivity of One-dimensional Nonlinear Cellular Automata |
| topic | Data Structures and Algorithms 05C05, 68Q25, 68Q80 |
| url | https://arxiv.org/abs/2309.03073 |