On the Dynamics of Bounded-Degree Automata Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909902147944448 |
|---|---|
| author | Aracena, Julio Bridoux, Florian Gadouleau, Maximilien Guillon, Pierre Perrot, Kévin Richard, Adrien Theyssier, Guillaume |
| author_facet | Aracena, Julio Bridoux, Florian Gadouleau, Maximilien Guillon, Pierre Perrot, Kévin Richard, Adrien Theyssier, Guillaume |
| contents | Automata networks can be seen as bare finite dynamical systems, but their growing theory has shown the importance of the underlying communication graph of such networks. This paper tackles the question of what dynamics can be realized up to isomorphism if we suppose that the communication graph has bounded degree. We prove several negative results about parameters like the number of fixed points or the rank. We also show that we can realize with degree 2 a dynamics made of a single fixed point and a cycle gathering all other configurations. However, we leave open the embarrassingly simple question of whether a dynamics consisting of a single cycle can be realized with bounded degree, although we prove that it is impossible when the network become acyclic by suppressing one node, and that realizing precisely a Gray code map is impossible with bounded degree. Finally we give bounds on the complexity of the problem of recognizing such dynamics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_11174 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Dynamics of Bounded-Degree Automata Networks Aracena, Julio Bridoux, Florian Gadouleau, Maximilien Guillon, Pierre Perrot, Kévin Richard, Adrien Theyssier, Guillaume Computational Complexity Automata networks can be seen as bare finite dynamical systems, but their growing theory has shown the importance of the underlying communication graph of such networks. This paper tackles the question of what dynamics can be realized up to isomorphism if we suppose that the communication graph has bounded degree. We prove several negative results about parameters like the number of fixed points or the rank. We also show that we can realize with degree 2 a dynamics made of a single fixed point and a cycle gathering all other configurations. However, we leave open the embarrassingly simple question of whether a dynamics consisting of a single cycle can be realized with bounded degree, although we prove that it is impossible when the network become acyclic by suppressing one node, and that realizing precisely a Gray code map is impossible with bounded degree. Finally we give bounds on the complexity of the problem of recognizing such dynamics. |
| title | On the Dynamics of Bounded-Degree Automata Networks |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2511.11174 |