The size of arrays for a prime implicant generating algorithm
Yasunobu Igarashi · The Computer Journal · 1980
A number of interesting combinatorial problems have arisen by investigating a computer implementation of a prime implicant generator called the star-algorithm. These problems have been motivated by the necessity of estimating suitable sizes of arrays to store intermediate results when the algorithm is written in a computer language such as ALGOL 60. Bn(r) denotes the set of r-cubes of the n-variable Boolean algebra and ⊛ denotes the star-product. P(Bn(r))=#({b|b ϵBn(r) and a ⊛b≠&}), where #(S) is the number of elements of set S, a is an arbitrary element of Bn(r), and a ⊛b ≠& means that the star-product of a and b is a cube. The main combinatorial result in this paper is that for all 0<ϵ, K1(n33/4)n≤ max{P(Bn(r))|0≤r≤n}≤k2(33/4 +ϵ)n. where k1 and k2 are constants independent of n.