DocumentCode
968671
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
Volume
38
Issue
6
fYear
1989
fDate
6/1/1989 12:00:00 AM
Firstpage
865
Lastpage
869
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;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/12.24296
Filename
24296
Link To Document