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

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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2017, DMTCS Proceedings, DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems, pp.1-16


https://hal.inria.fr/hal-01196145
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 9 septembre 2015 - 11:15:06
Dernière modification le : mardi 31 janvier 2017 - 10:21:36
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

Collections

Citation

Adrien Richard. A fixed point theorem for Boolean networks expressed in terms of forbidden subnetworks. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2017, DMTCS Proceedings, DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems, pp.1-16. <hal-01196145>

Partager

Métriques

Consultations de
la notice

187

Téléchargements du document

420