On the flora of asynchronous locally non-monotonic Boolean automata networks

Abstract. Studies on the dynamics of Boolean automata networks (ab-breviated by 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 analo-gous 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 characterization of the asynchronous transition graphs for most of the cactus ⊕-BANs and strongly connected ⊕-BANs. As an illustration of the results, we provide a complete descrip-tion of the asynchronous dynamics of two particular classes of ⊕-BAN, namely ⊕-Flowers and ⊕-Cycle Chains. This work also leads to new bisimulation equivalences specific to ⊕-BANs