OBF: Optimized Blist Form |

Let F be a positive-form Boolean expression with n literals. Assume that the values of the literals are made available one at a time in any desired order, but only once. Let s(n) be the number of steps (operations) and b(n) of bits of working memory (footprint) needed to evaluate F. The Optimized Blist Form (OBF) evaluates F using only s(n)=n steps and b(n)=log

A Boolean expression F may be converted to its positive form and represented by a binary tree with only union and intersection nodes and leaves each representing a literal. Such a tree may be converted ("wired") into its Blist form, which can be represented as a digital circuit and evaluated by accessing the leaves values one by one from left to right. The working memory (footprint) needed for the evaluation of E corresponds symbolically to the maximum number of wires crossing any vertical line that would split the circuit. Hence, the expression below needs 3 bits because 3 wires are running through a vertical that would separate the two last gates.

The Optimized Blist Form (OBF) is the Blist form of an equivalent version of the Boolean expression F obtained through a linear cost "Flipper" algorithm that pivots (swaps) the left and right children of some of the operators in the tree. The pivoting reduces b(n). In the example below, it reduces the footprint b(n) from 5 to 2 bits.

...

We investigate three applications: