Julio Aracena, Adrien Richard, Lilian Salinas:
Maximum number of fixed points in AND-OR Boolean network
We are interested in the number of fixed points in AND-OR Boolean networks, i.e. Boolean networks in which the update function of each component is either a conjunction or a disjunction of positive or negative literals. As main result, we prove that the maximum number of fixed points in a loop-less connected AND-OR Boolean network with n components is at most the maximum number of maximal independent sets in a loop-less connected graph with n components, a quantity already known.
This preprint gave rise to the following definitive publication(s):
Julio ARACENA, Adrien RICHARD, Lilian SALINAS: Maximum number of fixed points in AND-OR Boolean network. Journal of Computer and System Sciences, vol. 80, pp. 1175-1190, (2014).