A fixed point theorem for Boolean networks expressed in terms of forbidden subnetworks

1 Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe BIOINFO
Laboratoire I3S - MDSC - Modèles Discrets pour les Systèmes Complexes
Abstract : We are interested in fixed points in Boolean networks, $\textit{i.e.}$ functions $f$ from $\{0,1\}^n$ to itself. We define the subnetworks of $f$ as the restrictions of $f$ to the hypercubes contained in $\{0,1\}^n$, and we exhibit a class $\mathcal{F}$ of Boolean networks, called even or odd self-dual networks, satisfying the following property: if a network $f$ has no subnetwork in $\mathcal{F}$, then it has a unique fixed point. We then discuss this "forbidden subnetworks theorem''. We show that it generalizes the following fixed point theorem of Shih and Dong: if, for every $x$ in $\{0,1\}^n$, there is no directed cycle in the directed graph whose the adjacency matrix is the discrete Jacobian matrix of $f$ evaluated at point $x$, then $f$ has a unique fixed point. We also show that $\mathcal{F}$ contains the class $\mathcal{F'}$ of networks whose the interaction graph is a directed cycle, but that the absence of subnetwork in $\mathcal{F'}$ does not imply the existence and the uniqueness of a fixed point.
Keywords :
Type de document :
Communication dans un congrès
Fatès, Nazim and Goles, Eric and Maass, Alejandro and Rapaport, Iván. 17th International Workshop on Celular Automata and Discrete Complex Systems, 2011, Santiago, Chile. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems, pp.1-16, 2011, DMTCS Proceedings
Domaine :

Littérature citée [12 références]

https://hal.inria.fr/hal-01196145
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 9 septembre 2015 - 11:15:06
Dernière modification le : lundi 5 novembre 2018 - 15:48:02
Document(s) archivé(s) le : lundi 28 décembre 2015 - 23:02:22

Fichier

dmAP0101.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

• HAL Id : hal-01196145, version 1

Citation

Adrien Richard. A fixed point theorem for Boolean networks expressed in terms of forbidden subnetworks. Fatès, Nazim and Goles, Eric and Maass, Alejandro and Rapaport, Iván. 17th International Workshop on Celular Automata and Discrete Complex Systems, 2011, Santiago, Chile. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems, pp.1-16, 2011, DMTCS Proceedings. 〈hal-01196145〉

Métriques

Consultations de la notice

272

Téléchargements de fichiers