Preprint 2022-08
Julio Aracena, Adrien Richard, Lilian Salinas:
Synchronizing Boolean networks asynchronously
Abstract:
The asynchronous automaton associated with 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 ith component if fi(x) 6= xi or doing nothing otherwise. These actions are extended to words in the natural way. A word is then synchronizing if the result of its action is the same for every state. In this paper, we ask for the existence of synchronizing words, and their minimal length, for a basic class of Boolean networks called and-or-nets: given an arc-signed digraph G on [n], we say that f is an and-or-net on G if, for every i ∈ [n], there is a such that, for all state x, fi(x) = a if and only if xj = a (xj 6= a) for every positive (negative) arc from j to i; so if a = 1 (a = 0) then fi is a conjunction (disjunction) of positive or negative literals. Our main result is that if G is strongly connected and has no positive cycles, then either every and-or-net on G has a synchronizing word of length at most 10(√5+1)n, much smaller than the bound (2n − 1)2 given by the well known ˇCern y’s conjecture, or G is a cycle and no and-or-net on G has a synchronizing word. This contrasts with the following complexity result: it is coNP-hard to decide if every and-or-net on G has a synchronizing word, even if G is strongly connected or has no positive cycles.
This preprint gave rise to the following definitive publication(s):
Julio ARACENA, Adrien RICHARD, Lilian SALINAS: Synchronizing Boolean networks asynchronously. Journal of Computer and System Sciences, vol. 136, 249-279 (2023).