A new transitive closure algorithm with application to redundancyidentification

摘要

A new transitive closure algorithm is presented for implicationgraphs that contain partial implications. In the presence of partialimplications, a vertex can assume the true state when all vertices thatpartially imply it become true. Such graphs provide a more completerepresentation of a logic circuit than is possible with the conventionalpair-wise implications. An application of the new transitive closurealgorithm to redundancy identification shows significantly improvedresults. Empirically, we find the computational complexity of transitiveclosure to be linear for the implication graphs of the ISCAS benchmarkcircuits