Title :
The complexity of generating minimum test sets for PLA´s and monotone combinational circuits
Author :
Chakravarty, S. ; Hunt, H.B. ; Ravi, S.S. ; Rosenkrantz, D.J.
Author_Institution :
Dept. of Comput. Sci., State Univ. of New York, Buffalo, NY, USA
fDate :
6/1/1989 12:00:00 AM
Abstract :
The authors show that the problem of obtaining a minimum complete test set is NP-complete for monotone PLAs even when each product term of the PLA contains at most two literals. Using the ideas developed in the proof of this result, they resolve an open question due to B. Krishnamurthy and S.B. Akers (1984). The authors also show that given a complete test set T, the problem of obtaining a minimum test set contained in T is NP-complete even for two-level monotone circuits
Keywords :
combinatorial circuits; computational complexity; logic arrays; logic testing; NP-complete; complexity; literals; minimum complete test set; minimum test sets; monotone PLAs; monotone combinational circuits; Circuit faults; Circuit testing; Combinational circuits; Computer science; Fault detection; Logic functions; NP-hard problem; Polynomials; Programmable logic arrays; Very large scale integration;
Journal_Title :
Computers, IEEE Transactions on
