کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437837 | 690194 | 2015 | 26 صفحه PDF | دانلود رایگان |

We are interested in fixed points in Boolean networks, i.e. functions f from {0,1}n{0,1}n to itself. We define the subnetworks of f as the restrictions of f to the subcubes of {0,1}n{0,1}n, and we characterize a class FF of Boolean networks satisfying the following property: Every subnetwork of f has a unique fixed point if and only if f has no subnetwork in FF. This characterization generalizes the fixed point theorem of Shih and Dong, which asserts that if for every x in {0,1}n{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. Then, denoting by C+C+ (resp. C−C−) the networks whose interaction graph is a positive (resp. negative) cycle, we show that the non-expansive networks of FF are exactly the networks of C+∪C−C+∪C−; and for the class of non-expansive networks we get a “dichotomization” of the previous forbidden subnetwork theorem: Every subnetwork of f has at most (resp. at least) one fixed point if and only if f has no subnetworks in C+C+ (resp. C−C−) subnetwork. Finally, we prove that if f is a conjunctive network then every subnetwork of f has at most one fixed point if and only if f has no subnetworks in C+C+.
Journal: Theoretical Computer Science - Volume 583, 7 June 2015, Pages 1–26