7 papers
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…
On the Dynamics of Bounded-Degree Automata Networks
Julio Aracena, Florian Bridoux, Maximilien Gadouleau +4
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…
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…
Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs
Aliénor Goubault-Larrecq, Kévin Perrot
A new proof technique combining finite model theory and dynamical systems has recently been introduced to obtain general complexity lower bounds on any question one may formulate o…
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…