6 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…
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…
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…