On the Flora of Asynchronous Locally Non-monotonic Boolean Automata Networks

Boolean automata networks (BANs) are a well established model for regulation systems such as neural networks or gene regulation networks. Studies on the asynchronous dynamics of BANs have mainly focused on monotonic networks, where fundamental questions on the links relating their static and dynamical properties have been raised and addressed. This paper explores analogous questions on non-monotonic networks, ⊕-BANs (xor-BANs), that are BANs where all the local transition functions are ⊕-functions. Using algorithmic tools, we give a general characterisation of the asynchronous transition graphs of most of the strongly connected ⊕-BANs and cactus ⊕-BANs. As an illustration of these results, we provide a complete description of the asynchronous dynamics of two particular structures of ⊕-BANs, namely ⊕-Flowers and ⊕-Cycle Chains. This work also draws new behavioural equivalences between BANs, using rewriting rules on their graph description.