|
Solving the parity problem in automata networks| title | Solving the parity problem in automata networks |
|---|
| start_date | 2024/04/02 |
|---|
| schedule | 14h |
|---|
| online | no |
|---|
| location_info | Salle 04.05, bât TPR2 |
|---|
| summary | The parity problem is a classical binary benchmark for addressing the computational ability and limitations of automata networks. It refers to conceiving a local rule to allow deciding whether the number of 1-states in the nodes of an arbitrary network is an odd or even number, without global access to the nodes. In its standard formulation, the automata network has an odd number of nodes whose states, arranged as a cyclic configuration, should converge to a fixed point of all 0s, if the initial configuration has an even number of 1s, or to a fixed point of all 1s, otherwise. It has been shown that a local rule alone is able to solve the problem in this formulation. In this talk I will review some solutions available for the problem, with a focus on recent solutions we provided on a non-circulant graph with synchronous update. |
|---|
| responsibles | NC |
|---|
Workflow history| from state (1) | to state | comment | date |
|---|
| submitted | published | | 2024/03/28 14:56 UTC |
| |
|