Synchronizing Boolean networks asynchronously.

The asynchronous automaton of a Boolean network f : { 0 , 1 } n → { 0 , 1 } n , considered in many applications, is the finite deterministic automaton where the set of states is { 0 , 1 } n , the alphabet is [ n ] , and the action of letter i on a state x consists in either switching the i th component if f i (x) ≠ x i or doing nothing otherwise. In this paper, we ask for the existence of synchronizing words for this automaton, and their minimal length, when f is the and-net over an arc-signed digraph G on [ n ] : for every i ∈ [ n ] , f i (x) = 1 if and only if x j = 1 (x j ≠ 0) for every positive (negative) arc from j to i. Our main result is that if G is strongly connected and has no positive cycles, then either there exists a synchronizing word of length at most 10 (5 + 1) n or G is a cycle and there are no synchronizing words. We also give complexity results showing that the situation is much more complex if one of the two hypothesis made on G is removed. [ABSTRACT FROM AUTHOR]