کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430212 687929 2014 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Maximum number of fixed points in AND–OR–NOT networks
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Maximum number of fixed points in AND–OR–NOT networks
چکیده انگلیسی


• We determine the maximum number of fixed points (MNFP) in AND–OR–NOT-networks.
• MNFP differs strongly when loops are allowed or not.
• MNFP is bounded above by the maximum number of independent sets of a graph.
• We also characterize the AND–OR–NOT-networks reaching these bounds.

We are interested in the number of fixed points in AND–OR–NOT networks, i.e. Boolean networks in which the update function of each component is either a conjunction or a disjunction of positive or negative literals. As the main result, we prove that the maximum number of fixed points in a loop-less connected AND–OR–NOT network with n components is at most the maximum number of maximal independent sets in a loop-less connected graph with n vertices, a quantity already known.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 80, Issue 7, November 2014, Pages 1175–1190
نویسندگان
, , ,