{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T22:12:59Z","timestamp":1768687979765,"version":"3.49.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2001,12,1]],"date-time":"2001-12-01T00:00:00Z","timestamp":1007164800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2001,12,1]],"date-time":"2001-12-01T00:00:00Z","timestamp":1007164800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Electronic Testing"],"published-print":{"date-parts":[[2001,12]]},"DOI":"10.1023\/a:1012820722053","type":"journal-article","created":{"date-parts":[[2002,12,23]],"date-time":"2002-12-23T15:09:07Z","timestamp":1040656147000},"page":"509-527","source":"Crossref","is-referenced-by-count":5,"title":["Why is Combinational ATPG Efficiently Solvable for Practical VLSI Circuits?"],"prefix":"10.1007","volume":"17","author":[{"given":"Mukul R.","family":"Prasad","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philip","family":"Chong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kurt","family":"Keutzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"382036_CR1","volume-title":"Digital Systems Testing and Testable Design","author":"M. Abramovici","year":"1990","unstructured":"M. Abramovici, M.A. Breuer, and A.D. Friedman, Digital Systems Testing and Testable Design, Computer Science Press, New York, 1990."},{"key":"382036_CR2","unstructured":"D. Brand, \u201cVerification of Large Synthesized Designs,\u201d in Proc. IEEE International Conference on Computer Aided Design, 1993, pp. 534-537."},{"key":"382036_CR3","doi-asserted-by":"crossref","unstructured":"R.K. Brayton, R. Rudell, A. Sangiovanni-Vincentelli, and A. Wang, \u201cMIS: A Multiple-Level Logic Optimization System,\u201d IEEE Transactions on CAD\/ICAS, Vol. CAD-6, pp. 1062-1082, Nov. 1987.","DOI":"10.1109\/TCAD.1987.1270347"},{"key":"382036_CR4","doi-asserted-by":"crossref","unstructured":"C.L. Berman, \u201cCircuit Width, Register Allocation and Ordered Binary Decision Diagrams,\u201d IEEE Transactions on Computer-Aided Design, Vol. 10, pp. 1059-1066, Aug. 1991.","DOI":"10.1109\/43.85742"},{"key":"382036_CR5","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/BF01531068","volume":"1","author":"E. Boros","year":"1990","unstructured":"E. Boros, Y. Crama, and P.L. Hammer, \u201cPolynomial-Time Inference of All Valid Implications for Horn and Related Formulae,\u201d Ann. Math Art. Intell., Vol. 1, pp. 21-32, 1990.","journal-title":"Ann. Math Art. Intell."},{"key":"382036_CR6","doi-asserted-by":"crossref","unstructured":"E. Boros, Y. Crama, P.L. Hammer, and M. Saks, \u201cA Complexity Index for Satisfiability Problems,\u201d SIAM Journal of Computing, Vol. 23, pp. 45-49, Feb. 1994.","DOI":"10.1137\/S0097539792228629"},{"key":"382036_CR7","unstructured":"F. Brglez and H. Fujiwara, \u201cA Neural Netlist of 10 Combinational Benchmark Circuits and a Target Translator in Fortran,\u201d in Proc. International Symposium on Circuits and Systems, June 1985."},{"key":"382036_CR8","doi-asserted-by":"crossref","first-page":"909","DOI":"10.1109\/43.391740","volume":"14","author":"K.-T. Cheng","year":"1995","unstructured":"K.-T. Cheng and L.A. Entrena, \u201cCombinational and Sequential Logic Optimization by Redundancy Addition and Removal,\u201d IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 14, pp. 909-916, July 1995.","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"382036_CR9","series-title":"Technical Report","volume-title":"Why is ATPG Easy?","author":"P. Chong","year":"1998","unstructured":"P. Chong, M.R. Prasad, K. Keutzer, and R.K. Brayton, \u201cWhy is ATPG Easy?,\u201d Technical Report, ERL, University of California, Berkeley, 1998."},{"key":"382036_CR10","doi-asserted-by":"crossref","unstructured":"O. Coudert, \u201cExact Coloring of Real-Life Graphs is Easy,\u201d in Proceedings of the 34th DAC, June 1997, pp. 121-126.","DOI":"10.1145\/266021.266047"},{"key":"382036_CR11","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/978-94-009-1417-9_8","volume-title":"Testing and Diagnosis of VLSI and ULSI","author":"S. Devadas","year":"1988","unstructured":"S. Devadas, H.-K.T. Ma, and A. Sangiovanni-Vincentelli, \u201cLogic Verification, Testing and Their Relationship to Logic Synthesis,\u201d Testing and Diagnosis of VLSI and ULSI, Kluwer Academic Publishers, Dordrecht, 1988, pp. 181-246."},{"key":"382036_CR12","doi-asserted-by":"crossref","unstructured":"H. Fujiwara, \u201cComputational Complexity of Controllability\/Observability Problems for Combinaitonal Circuits,\u201d in Proc. International Symposium on Fault-Tolerant Computing, June 1988, pp. 64-69.","DOI":"10.1109\/FTCS.1988.5298"},{"key":"382036_CR13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, New York: W.H. Freeman and Company, 1979."},{"key":"382036_CR14","doi-asserted-by":"crossref","unstructured":"D. Ghosh and F. Brglez, \u201cEquivalence Classes of Circuit Mutants for Experimental Design,\u201d in Proceedings of the 1999 IEEE International Symposium on Circuits and Systems VLSI, 1999, pp. 432-435.","DOI":"10.1109\/ISCAS.1999.780187"},{"key":"382036_CR15","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1090\/dimacs\/035\/02","volume":"35","author":"J. Gu","year":"1997","unstructured":"J. Gu, P.W. Purdom, J. Franco, and B.W. Wah, \u201cAlgorithms for the Satisfiability (SAT) Problem: A Survery,\u201d DIMACS Series in Discrete Mathematics and Computer Science, Vol. 35, pp. 19-151, 1997.","journal-title":"DIMACS Series in Discrete Mathematics and Computer Science"},{"key":"382036_CR16","volume-title":"Approximation Algorithms for NP-Hard Problems","year":"1997","unstructured":"D.S. Hochbaum (ed.), Approximation Algorithms for NP-Hard Problems, Boston, MA: PWS Publishing Company, 1997."},{"key":"382036_CR17","doi-asserted-by":"crossref","first-page":"985","DOI":"10.1109\/43.728919","volume":"17","author":"M. Hutton","year":"1998","unstructured":"M. Hutton, J.P. Grossman, J. Rose, and D. Corneil, \u201cCharacterization and Paramterized Generation of Synthetic Combinational Benchmark Circuits,\u201d IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 17, pp. 985-996, Oct. 1998.","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"issue":"3","key":"382036_CR18","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1109\/T-C.1975.224205","volume":"C-24","author":"O.H. Ibarra","year":"1975","unstructured":"O.H. Ibarra and S.K. Sahni, \u201cPolynomially Complete Fault Detection Problems,\u201d IEEE Transactions on Computers, Vol. C-24,No. 3, pp. 242-249, March 1975.","journal-title":"IEEE Transactions on Computers"},{"key":"382036_CR19","doi-asserted-by":"crossref","unstructured":"G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, \u201cMultilevel Hypergraph Partitioning: Applications in VLSI Domain,\u201d IEEE Transactions on VLSI Systems, Vol. 7, pp. 69-79, March 1999.","DOI":"10.1109\/92.748202"},{"key":"382036_CR20","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1147\/rd.391.0149","volume":"39","author":"A. Kuehlmann","year":"1995","unstructured":"A. Kuehlmann, A. Srinivasan, and D.P. LaPotin, \u201cVerity\u2014A Formal Verification Program for Custom CMOS Circuits,\u201d IBM Journal of Research and Development, Vol. 39, pp. 149-165, 1995.","journal-title":"IBM Journal of Research and Development"},{"key":"382036_CR21","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1109\/43.108614","volume":"11","author":"T. Larrabee","year":"1992","unstructured":"T. Larrabee, \u201cTest Pattern Generation Using Boolean Satisfiability,\u201d IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 11, pp. 4-15, Jan. 1992.","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"382036_CR22","unstructured":"K.L. McMillan, Symbolic Model Checking: An Approach to the State Explosion Problem, Ph.D. Thesis, School of Computer Science, Carnegie Mellon University, 1992."},{"key":"382036_CR23","unstructured":"S.L. Meyer, Data Analysis For Scientists and Engineers, Wiley and Sons, 1975."},{"key":"382036_CR24","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0020-0255(87)90003-X","volume":"41","author":"P.W. Purdom","year":"1987","unstructured":"P.W. Purdom and C.A. Brown, \u201cPolynomial-Average-Time Satisfiability Problems,\u201d Information Sciences, Vol. 41, pp. 23-42, 1987.","journal-title":"Information Sciences"},{"key":"382036_CR25","volume-title":"Mathematical Statistics and Data Analysis","author":"J.A. Rice","year":"1995","unstructured":"J.A. Rice, Mathematical Statistics and Data Analysis, 2nd edn; Belmont, CA: International Thompson Publishing, 1995.","edition":"2nd edn"},{"key":"382036_CR26","series-title":"Technical Report UCB\/ERL","volume-title":"SIS: A System for Sequential Circuit Synthesis","author":"E. M. Sentovich","year":"1998","unstructured":"Ellen M. Sentovich, Kanwar Jit Singh, Luciano Lavagno, Cho Moon, Rajeev Murgai, Alexander Saldanha, Hamid Savoj, Paul R. Stephan, Robert K. Brayton, and Alberto Sangiovanni-Vincentell, \u201cSIS: A System for Sequential Circuit Synthesis,\u201d Technical Report UCB\/ERL M92\/41, ERL, College of Engineering, University of California, Berkeley, May 1998."},{"key":"382036_CR27","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1109\/12.769433","volume":"48","author":"J.P.M. -Silva","year":"1999","unstructured":"J.P.M.-Silva and K. Sakallah, \u201cGRASP: A Search Algorithm for Propositional Satisfiability,\u201d IEEE Transactions on Computers, Vol. 48, pp. 506-521, May 1999.","journal-title":"IEEE Transactions on Computers"},{"key":"382036_CR28","doi-asserted-by":"crossref","first-page":"1167","DOI":"10.1109\/43.536723","volume":"15","author":"P. Stephan","year":"1996","unstructured":"P. Stephan, R.K. Brayton, and A.L. Sangiovanni-Vincentelli, \u201cCombinational Test Generation Using Satisfiability,\u201d IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 15, pp. 1167-1176, Sept. 1996.","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"382036_CR29","doi-asserted-by":"crossref","unstructured":"T.W. Williams and K. Parker, \u201cTesting Logic Networks and Designing for Testability,\u201d Computer, pp. 9-21, Oct. 1979.","DOI":"10.1109\/MC.1979.1658490"},{"key":"382036_CR30","unstructured":"S. Yang, \u201cLogic Synthesis and Optimization Benchmarks User Guide, Version 3.0,\u201d Technical Report, Microelectronics Center of North Carolina, 1991."}],"container-title":["Journal of Electronic Testing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1012820722053.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1012820722053\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1012820722053.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T10:13:16Z","timestamp":1749204796000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1012820722053"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,12]]},"references-count":30,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2001,12]]}},"alternative-id":["382036"],"URL":"https:\/\/doi.org\/10.1023\/a:1012820722053","relation":{},"ISSN":["0923-8174","1573-0727"],"issn-type":[{"value":"0923-8174","type":"print"},{"value":"1573-0727","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,12]]}}}