5 papers · 1 filter
Non-trivial automata networks do exist that solve the global majority problem with the local majority rule
Pedro Paulo Balbi, Kévin Perrot, Marius Rolland +1
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 net…
Creation of fixed points in block-parallel Boolean automata networks
Kévin Perrot, Sylvain Sené, Léah Tapin
In the context of discrete dynamical systems and their applications, fixed points often have a clear interpretation. This is indeed a central topic of gene regulatory mechanisms mo…
Foundations of block-parallel automata networks
Kévin Perrot, Sylvain Sené, Léah Tapin
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 repeti…
Rice-like complexity lower bounds for Boolean and uniform automata networks
Aliénor Goubault-Larrecq, Kévin Perrot
Automata networks are a versatile model of finite discrete dynamical systems composed of interacting entities (the automata), able to embed any directed graph as a dynamics on its…
Complexity of Boolean automata networks under block-parallel update modes
Kévin Perrot, Sylvain Sené, Léah Tapin
Boolean automata networks (aka Boolean networks) are space-time discrete dynamical systems, studied as a model of computation and as a representative model of natural phenomena. A…