Efficient exact and heuristic minimization of hazard-free logic

In this paper we consider the problem of finding minimum and minimal sum of product circuits (PLAs) that correctly implement a given set of transitions without any hazards. In earlier work we introduced an efficient divide and conquer algorithm, the threeway method, that is capable of finding a minimum PLA-implementation for single output functions. We showed that this method was 10 times faster than the exact method proposed by Dill/Nowick. In this paper we extend the threeway method such that it can deal with multiple output functions. We compare the enhanced threeway method again with Dill/Nowick´s method. We also propose an efficient heuristic method, derived from the threeway method, that is capable of finding minimal implementations of specifications that cannot be minimized by the exact methods