Oberschelp, W. Fast parallel algorithms for finding all prime implicants for discrete functions. (English) Zbl 0576.94025 Logic and machines: decision problems and complexity, Proc. Symp., Münster/Ger. 1983, Lect. Notes Comput. Sci. 171, 408-420 (1984). Summary: [For the entire collection see Zbl 0538.00005.] We consider the problem of enumerating the prime implicants of a given discrete function as a basic task of circuit theory. First, we count PI’s for random Boolean functions. Then we use the well known lattice differentiation as a tool for finding implicants. The concept of a peak admits to characterize prime implicants, at least those with no improper domains. The improper case can be reduced to a lower dimensional problem. Since the peak test is local, a parallel algorithm is available. The time and space complexity turns out to be low measured in the input size. Cited in 1 Document MSC: 94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010) 68Q25 Analysis of algorithms and problem complexity Keywords:random Boolean functions; lattice differentiation; peak test Citations:Zbl 0538.00005 PDFBibTeX XML