CI²MA - Publications | Preprints

Preprint 2013-02

Julio Aracena, Adrien Richard, Lilian Salinas:

Maximum number of fixed points in AND-OR Boolean network

Abstract:

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.

Descargar en formato PDF PDF

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).

 

 

  CI²MA, CENTER FOR RESEARCH IN MATHEMATICAL ENGINEERING, UNIVERSIDAD DE CONCEPCIÓN - MAILBOX 160-C, CONCEPCIÓN, CHILE, PHONE: +56-41-2661324