Logic circuits from zero forcing

Details Logic circuits from zero forcing Logic circuits from zero forcing

2011-06-22

arxiv.org/abs/1106.4403v4

Computer Science

Discrete Mathematics

5 pages, 10 EPS figures

Scientific paper

We design logic circuits based on the notion of zero forcing on graphs; each gate of the circuits is a gadget in which zero forcing is performed. We show that such circuits can evaluate every monotone Boolean function. By using two vertices to encode each logical bit, we obtain universal computation. We also highlight a phenomenon of "back forcing" as a property of each function. Such a phenomenon occurs in a circuit when the input of gates which have been already used at a given time step is further modified by a computation actually performed at a later stage. Finally, we point out that zero forcing can be also used to implement reversible computation. The model introduced here provides a potentially new tool in the analysis of Boolean functions, with particular attention to monotonicity.

Affiliated with

Also associated with

No associations

Rating

Logic circuits from zero forcing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Logic circuits from zero forcing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Logic circuits from zero forcing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-205673