Non-trivial automata networks do exist that solve the global majority problem with the local majority rule
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910060639158272 |
|---|---|
| author | Balbi, Pedro Paulo Perrot, Kévin Rolland, Marius Ruivo, Eurico |
| author_facet | Balbi, Pedro Paulo Perrot, Kévin Rolland, Marius Ruivo, Eurico |
| contents | The global majority problem, often referred to as the Density Classification Task, is a classical benchmark in the context of probing the computational capabilities of automata networks. It poses the simple yet challenging problem of determining, by totally local means, whether an arbitrary initial configuration of binary states can evolve to a final, homogeneous global configuration that reflects the initial global majority. Although it is known that in the specific case of cellular automata with periodic boundaries no rule is able to solve the problem, in other formulations solutions are known and, in others, the problem is still open. Aligned with the latter, here we explore the possibility of solving the problem with automata networks, operating only with the local majority rule, with a focus on identifying non-trivial cases where it can be solved and explaining why they do so. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_19472 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Non-trivial automata networks do exist that solve the global majority problem with the local majority rule Balbi, Pedro Paulo Perrot, Kévin Rolland, Marius Ruivo, Eurico Discrete Mathematics Distributed, Parallel, and Cluster Computing The global majority problem, often referred to as the Density Classification Task, is a classical benchmark in the context of probing the computational capabilities of automata networks. It poses the simple yet challenging problem of determining, by totally local means, whether an arbitrary initial configuration of binary states can evolve to a final, homogeneous global configuration that reflects the initial global majority. Although it is known that in the specific case of cellular automata with periodic boundaries no rule is able to solve the problem, in other formulations solutions are known and, in others, the problem is still open. Aligned with the latter, here we explore the possibility of solving the problem with automata networks, operating only with the local majority rule, with a focus on identifying non-trivial cases where it can be solved and explaining why they do so. |
| title | Non-trivial automata networks do exist that solve the global majority problem with the local majority rule |
| topic | Discrete Mathematics Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2603.19472 |