- Meeting ID: 867 6409 6440
- passcode: 149120
13h00 - 13h50 – Kevin Perrot (LIS, Marseille)
Automata network’s interaction graph and complexity
Boolean automata networks (BANs) are a very general model of entities in interaction: n nodes are each given a local function from {0,1}^n to {0,1} describing how its state evolves in discrete time steps (nodes apply their local function in parallel). It can give any deterministic dynamics on state space {0,1}^n. The interaction graph (IG) of a BAN captures the effective dependencies among its nodes. We will review the computational complexity of two problems: 1) given the local functions encoded as circuits, compute the IG; 2) given the IG with signed arcs, decide bounds on the max/min possible number of fixed points in the dynamics. We will underline important complexity drops when the degree of interactions is bounded, and open large perspectives on these subjects.
Dernière modification le 03/06/2022