Foundations of block-parallel 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_ | 1866910873617956864 |
|---|---|
| author | Perrot, Kévin Sené, Sylvain Tapin, Léah |
| author_facet | Perrot, Kévin Sené, Sylvain Tapin, Léah |
| contents | We settle the theoretical ground for the study of automata networks under block-parallel update schedules, which are somehow dual to the block-sequential ones, but allow for repetitions of automaton updates. This gain in expressivity brings new challenges, and we analyse natural equivalence classes of update schedules: those leading to the same dynamics, and to the same limit dynamics, for any automata network. Countings and enumeration algorithms are provided, for their numerical study. We also prove computational complexity bounds for many classical problems, involving fixed points, limit cycles, the recognition of subdynamics, reachability, etc. The PSPACE-completeness of computing the image of a single configuration lifts the complexity of most problems, but the landscape keeps some relief, in particular for reversible computations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_04591 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Foundations of block-parallel automata networks Perrot, Kévin Sené, Sylvain Tapin, Léah Discrete Mathematics 68R01, 68R05 F.1.1; F.1.3 We settle the theoretical ground for the study of automata networks under block-parallel update schedules, which are somehow dual to the block-sequential ones, but allow for repetitions of automaton updates. This gain in expressivity brings new challenges, and we analyse natural equivalence classes of update schedules: those leading to the same dynamics, and to the same limit dynamics, for any automata network. Countings and enumeration algorithms are provided, for their numerical study. We also prove computational complexity bounds for many classical problems, involving fixed points, limit cycles, the recognition of subdynamics, reachability, etc. The PSPACE-completeness of computing the image of a single configuration lifts the complexity of most problems, but the landscape keeps some relief, in particular for reversible computations. |
| title | Foundations of block-parallel automata networks |
| topic | Discrete Mathematics 68R01, 68R05 F.1.1; F.1.3 |
| url | https://arxiv.org/abs/2503.04591 |