A new Boolean function representation scheme, the Indexed Binary Decision Diagram (IBDD), is proposed to provide a compact representation for functions whose Ordered Binary Decision Diagram (OBDD) representation is intractably large. We explain properties of IBDDs and present algorithms for constructing IBDDs from a given circuit. Practical and effective algorithms for satisfiability testing and equivalence checking of IBDDs, as well as their implementation results, are also presented. The results show that many functions, such as multipliers and the hidden-weighted-bit function, whose analysis is intractable using OBDDs, can be efficiently accomplished using IBDDs. We report efficient verification of Booth multipliers, as well as a practical strategy for polynomial time verification of some classes of unsigned array multipliers.

Introduces some new methods for estimating the "importance" of a variable in a Boolean function, and uses them to compute variable orders for OBDD construction. These measures are based on information theoretic criteria, and require the computation of the entropy of a variable in a given function. These entropy measures prove quite effective in distinguishing the importance of variables. Experimental results show this to be a very encouraging approach to help in the solution of this well known problem.>

The authors present a novel method for verifying the equivalence of two Boolean functions. Each function is hashed to an integer code by assigning random integer values to the input variables and evaluating its integer-valued representation. The equivalence of two functions can be verified with a very low probability of error. The probability of error can be exponentially decreased by making multiple runs. Results indicate significant time and space advantages for this method over deterministic techniques. Some functions known to require space (and time) exponential in the number of input variables for deterministic verification require only polynomial resources using the proposed technique.>

We develop an algorithm for the Dutch National Flag problem that has an adjustable integer parameter $\operatorname{smax} \geqq 0$ allowing a time/space tradeoff. (Let n be the length of the input to be ordered.) The space required is proportional to smax (but independent of n), and the average number of swaps required is $((6\operatorname{smax} + 10) / (18\operatorname{smax} + 27))n + o(n)$. We show $\tfrac{1}{3}n + o(n)$ is a lower bound. Hence as ${\text{smax}} \to \infty $, the performance can be made arbitrarily close to the lower bound. This is a significant improvement over previous algorithms due to the use of a different invariant. We show that an algorithm using Dijkstra’s invariant must use at least $\tfrac{5}{9}n$ swaps. We also study the problem of more than three colors.

To study the relationship between key-comparison cost and utilization (space efficiency) of 2-3 trees, we define a class of 2-3 trees called kcu-optimal trees, which, out of all 2-3 trees with optimal key-comparison cost, have maximum utilization. A characterization theorem for this class is proved and the “average” utilization is found to be 64.7%, showing that these properties are not totally incompatible. Finally, a linear-time algorithm is given to create a kcu-optimal tree from a sorted array of keys.

We first consider heuristics that dynamically alter linked lists, causing more frequently accessed keys to move nearer the “top” of the list. We show that the move to front rule reduces the access time much more quickly than the transposition rule, then give a “hybrid” of these two rules which decreases the access time quickly and has low asymptotic cost. We also discuss rules that assume a counter is associated with each key. Second, we consider rules for binary search trees. The monotonic tree rule performs well only when the entropy of the probability distribution for key requests is low; otherwise, it does not reduce the access time. A final class of rules using rotations give nearly optimal performance.

In this paper, we consider the accessing of batched requests in a linear storage medium. The batch size is assumed fixed and the access probabilities of individual records known. For a given arrangement of records in the storage, we consider the problem of read/write head scheduling to minimize the expected access time for a batch measured in terms of the distance traveled by the head. In the first part of the paper, several simple algorithms are proposed, analyzed and compared. The effect of different record arrangements is also discussed. In the second part of the paper, a family of algorithms called B-optimal rules are described. When B is $\infty $, an $\infty $-optimal rule is indeed optimal in the sense of minimizing expected distance traveled by the head per batch when accessing an arbitrarily large number of batches. A procedure to calculate an $\infty $-optimal rule for any given record arrangement is described, which is based on the idea of “discrete dynamic programming”.