Comments on "Redundancy Testing in Combinational Networks"

In the above-mentioned paper¹, Lee and Davidson present an algorithm for detecting all single redundant lines in a tree-type NAND network. In order to test for a single redundancy in a nontree network, they suggest replicating portions of the network (those which fan out) to get an equivalent tree-type NAND network. The algorithm for detecting single redundancies can then be applied to the equivalent tree-type network. However, a problem may arise if a single redundant connection in the original network, when replicated, leads to a set of connections all of which are irredundant when considered individually, but which are redundant when considered as a group. Lee and Davidson state that it is not known whether such a situation can occur. However, after some discussion they resolve the problem to the following question which they leave open: Can a set of 4 or more connections in a tree network corresponding to a single connection in the nontree network be redundant while any proper subset of the 4 or more lines is irredundant? The answer to this question will indicate whether the extension of their algorithm to nontree networks will always work.