کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430212 | 687929 | 2014 | 16 صفحه PDF | دانلود رایگان |

• 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.
Journal: Journal of Computer and System Sciences - Volume 80, Issue 7, November 2014, Pages 1175–1190