Combinatorics of Block-Parallel Automata Networks

Automata networks are finite collections of entities (the automata), each automaton having its own set of possible states, which interact with each other over discrete time, interactions being defined as local functions allowing the automata to change their state according to the states of their neighbourhoods. Inspired by natural phenomena, the studies on this very abstract and expressive model of computation have underlined the very importance of the way (i.e. the schedule) according to which the automata update their states, namely the update modes which can be deterministic, periodic, fair, or not. Indeed, a given network may admit numerous underlying dynamics, these latter depending highly on the update modes under which we let the former evolve. In this paper, we focus on a new kind of deterministic, periodic and fair update mode family introduced recently in a modelling framework, called the block-parallel update modes by duality with the well-known and studied block-sequential update modes. We compare block-parallel to block-sequential update modes, then count them: (1) in absolute terms, (2) by keeping only representatives leading to distinct dynamics, and (3) by keeping only representatives giving rise to non-isomorphic limit dynamics. Put together, this paper constitutes a first theoretical analysis of these update modes and their impact on automata networks dynamics.