کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437837 690194 2015 26 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Fixed point theorems for Boolean networks expressed in terms of forbidden subnetworks
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Fixed point theorems for Boolean networks expressed in terms of forbidden subnetworks
چکیده انگلیسی

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

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 583, 7 June 2015, Pages 1–26
نویسندگان
,