Article ID Journal Published Year Pages File Type
420253 Discrete Applied Mathematics 2011 9 Pages PDF
Abstract

Given a Boolean function F:{0,1}n→{0,1}nF:{0,1}n→{0,1}n, and a point xx in {0,1}n{0,1}n, we represent the discrete Jacobian matrix of FF at point xx by a signed directed graph GF(x)GF(x). We then focus on the following open problem: Is the absence of a negative circuit in GF(x)GF(x) for every xx in {0,1}n{0,1}n a sufficient condition for FF to have at least one fixed point? As result, we give a positive answer to this question under the additional condition that FF is non-expansive with respect to the Hamming distance.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,