DMTCS Proceedings, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems

Font Size:  Small  Medium  Large

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

Adrien Richard

Abstract


We are interested in fixed points in Boolean networks, 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 F of Boolean networks, called even or odd self-dual networks, satisfying the following property: if a network f has no subnetwork in 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 F contains the class F' of networks whose the interaction graph is a directed cycle, but that the absence of subnetwork in F' does not imply the existence and the uniqueness of a fixed point.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional