由網路觀點看布林函數在 Von Neumann 域之動態行為

Abstract

給定一個布林函數F由{0,1}^n送到{0,1}^n，我們可以得到F的迭代圖，更進一步的說，我們可以考慮F的影響矩陣B(F)以及F在x點的離散微分F'(x)，離散微分F'(x)是一個布林矩陣可以對應到一個n個點的有向圖Γ(F'(x))，也就是說，我們可以藉由F的迭代圖與有向圖Γ(F'(x))來觀察F的行為，在這篇文章裡面我們將由網路觀點來研究布林函數F在 Von Neumann 域之動態行為。Give a Boolean mapping F from {0,1}^n to {0,1}^n, we get a iteration graph for F. Furthermore, we may consider the incidence matrix B(F) and the discrete derivative F'(x) of F at x in {0,1}^n. In fact, B(F)=sup_{x in {0,1}^n}{F'(x)}. The discrete derivative F'(x), which is a Boolean matrix, can correspond to a direct graph Γ(F'(x)) with n nodes. That is to say, we can estimate the function F from the iteration graph of F and the direct graph Gamma(F'(x)). In this paper, we search for the dynamics of the Boolean mapping F in von Neumann neighborhood from network structure.