The complexity of generating minimum test sets for PLA's and monotone combinational circuits
- 1 June 1989
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 38 (6) , 865-869
- https://doi.org/10.1109/12.24296
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
This publication has 14 references indexed in Scilit:
- A New Approach to the Design of Testable PLA'sIEEE Transactions on Computers, 1987
- On the Complexity of Estimating the Size of a Test SetIEEE Transactions on Computers, 1984
- STAFAN: An Alternative to Fault SimulationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1984
- The Complexity of Fault Detection Problems for Combinational Logic CircuitsIEEE Transactions on Computers, 1982
- Fault Analysis and Test Generation for Programmable Logic Arrays (PLA's)IEEE Transactions on Computers, 1979
- A Testing Strategy for PLAsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- Diagnosis & Reliable Design of Digital SystemsPublished by Springer Nature ,1976
- Polynomially Complete Fault Detection ProblemsIEEE Transactions on Computers, 1975
- Derivation of Minimal Test Sets for Monotonic Logic CircuitsIEEE Transactions on Computers, 1973
- Derivation of Minimum Test Sets for Unate Logical CircuitsIEEE Transactions on Computers, 1971