{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:35:44Z","timestamp":1750307744962,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,4,2]],"date-time":"2008-04-02T00:00:00Z","timestamp":1207094400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2008,4,2]]},"abstract":"<jats:p>\n            We propose a new algebraic four-level expression called k-EXOR-projected sum of products (kEP-SOP). The optimization of a kEP-SOP is\n            <jats:italic>NP<\/jats:italic>\n            <jats:sup>\n              <jats:italic>NP<\/jats:italic>\n            <\/jats:sup>\n            -hard, but can be approximated within a fixed performance guarantee in polynomial time. Moreover, fully testable circuits under the stuck-at-fault model can be derived from kEP-SOPs by adding at most a constant number of multiplexer gates. The experiments show that the computational time is very short and the results are most of the time optimal with respect to the number of products involved. kEP-SOPs also prove experimentally a good starting point for general multilevel logic synthesis.\n          <\/jats:p>","DOI":"10.1145\/1344418.1344431","type":"journal-article","created":{"date-parts":[[2008,4,29]],"date-time":"2008-04-29T13:01:12Z","timestamp":1209474072000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["The optimization of kEP-SOPs"],"prefix":"10.1145","volume":"13","author":[{"given":"Anna","family":"Bernasconi","sequence":"first","affiliation":[{"name":"University of Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valentina","family":"Ciriani","sequence":"additional","affiliation":[{"name":"University of Milano, Crema (CR), Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto","family":"Cordone","sequence":"additional","affiliation":[{"name":"University of Milano, Crema (CR), Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,4,23]]},"reference":[{"volume-title":"Proceedings of the 14th International Conference on Very Large Scale Integration.","author":"Bernasconi A.","key":"e_1_2_1_1_1","unstructured":"Bernasconi , A. , Ciriani , V. , and Cordone , R . 2006. EXOR projected sum of products . In Proceedings of the 14th International Conference on Very Large Scale Integration. Bernasconi, A., Ciriani, V., and Cordone, R. 2006. EXOR projected sum of products. In Proceedings of the 14th International Conference on Very Large Scale Integration."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1228784.1228883"},{"volume-title":"Proceedings of the Conference on Design Automation and Test in Europe (DATE).","author":"Bernasconi A.","key":"e_1_2_1_3_1","unstructured":"Bernasconi , A. , Ciriani , V. , Drechsler , R. , and Villa , T . 2006. Efficient minimization of fully testable 2-SPP networks . In Proceedings of the Conference on Design Automation and Test in Europe (DATE). Bernasconi, A., Ciriani, V., Drechsler, R., and Villa, T. 2006. Efficient minimization of fully testable 2-SPP networks. In Proceedings of the Conference on Design Automation and Test in Europe (DATE)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2003.814950"},{"volume-title":"Logic Minimization Algorithms for VLSI Synthesis","author":"Brayton R.","key":"e_1_2_1_5_1","unstructured":"Brayton , R. , Hachtel , G. , McMullen , C. , and Sangiovanni-Vincentelli , A. 1984. Logic Minimization Algorithms for VLSI Synthesis . Kluwer Academic . Brayton, R., Hachtel, G., McMullen, C., and Sangiovanni-Vincentelli, A. 1984. Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Breuer M. and Friedman A. 1976. Diagnosis and Reliable Design of Digital Systems. Computer Science Press.  Breuer M. and Friedman A. 1976. Diagnosis and Reliable Design of Digital Systems. Computer Science Press.","DOI":"10.1007\/978-3-642-95424-5"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.85744"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.862746"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.969431"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-9260(94)00007-7"},{"volume-title":"Proceedings of the IEEE International Symposium on Multiple-Valued Logic, 99--104","author":"Debnath D.","key":"e_1_2_1_11_1","unstructured":"Debnath , D. and Sasao , T . 1999. Multiple--valued minimization to optimize PLAs with output EXOR gates . In Proceedings of the IEEE International Symposium on Multiple-Valued Logic, 99--104 . Debnath, D. and Sasao, T. 1999. Multiple--valued minimization to optimize PLAs with output EXOR gates. In Proceedings of the IEEE International Symposium on Multiple-Valued Logic, 99--104."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2003.816216"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2004.823342"},{"volume-title":"Proceedings of the International Workshop on Logic Synthesis, 251--254","author":"Dubrova E.","key":"e_1_2_1_14_1","unstructured":"Dubrova , E. and Ellervee , P . 1999. A fast algorithm for three-level logic optimization . In Proceedings of the International Workshop on Logic Synthesis, 251--254 . Dubrova, E. and Ellervee, P. 1999. A fast algorithm for three-level logic optimization. In Proceedings of the International Workshop on Logic Synthesis, 251--254."},{"volume-title":"Proceedings of the 4th International Workshop on the Applications of the Reed Muller Expansion in Circuit Design, 37--54","author":"Dubrova E.","key":"e_1_2_1_15_1","unstructured":"Dubrova , E. , Miller , D. , and Muzio , J . 1999. AOXMIN-MV: A heuristic algorithm for AND-OR-XOR minimization . In Proceedings of the 4th International Workshop on the Applications of the Reed Muller Expansion in Circuit Design, 37--54 . Dubrova, E., Miller, D., and Muzio, J. 1999. AOXMIN-MV: A heuristic algorithm for AND-OR-XOR minimization. In Proceedings of the 4th International Workshop on the Applications of the Reed Muller Expansion in Circuit Design, 37--54."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Fujita M. Matsunaga Y. and Ciesielski M. 2002. Multi-level logic optimization. In Logic Synthesis and Verification S. Hassoun and T. Sasao eds. Kluwer Academic 29--63.   Fujita M. Matsunaga Y. and Ciesielski M. 2002. Multi-level logic optimization. In Logic Synthesis and Verification S. Hassoun and T. Sasao eds. Kluwer Academic 29--63.","DOI":"10.1007\/978-1-4615-0817-5_2"},{"key":"e_1_2_1_17_1","unstructured":"Garey M. and Johnson D. 1979. Computer and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman.   Garey M. and Johnson D. 1979. Computer and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman."},{"key":"e_1_2_1_18_1","first-page":"1214","article-title":"New three-level boolean expression based on EXOR gates","volume":"5","author":"Ishikawa R.","year":"2004","unstructured":"Ishikawa , R. , Hirayama , T. , Koda , G. , and Shimizu , K. 2004 . New three-level boolean expression based on EXOR gates . IEICE Trans. Inf. Syst. 5 , 1214 -- 1222 . Ishikawa, R., Hirayama, T., Koda, G., and Shimizu, K. 2004. New three-level boolean expression based on EXOR gates. IEICE Trans. Inf. Syst. 5, 1214--1222.","journal-title":"IEICE Trans. Inf. Syst."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the IEEE Asia-Pacific Conference on Circuits and Systems","volume":"2","author":"Ishikawa R.","unstructured":"Ishikawa , R. , Igarashi , T. , Hirayama , T. , and Shimizu , K . 2002. Pseudocube-Based expressions to enhance testability . In Proceedings of the IEEE Asia-Pacific Conference on Circuits and Systems , vol. 2 , 305--310. Ishikawa, R., Igarashi, T., Hirayama, T., and Shimizu, K. 2002. Pseudocube-Based expressions to enhance testability. In Proceedings of the IEEE Asia-Pacific Conference on Circuits and Systems, vol. 2, 305--310."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.754996"},{"volume-title":"Proceedings of the IEEE International Conference on Computer Design. 628--633","author":"Malik A.","key":"e_1_2_1_21_1","unstructured":"Malik , A. , Harrison , D. , and Brayton , R . 1991. Three-level decomposition with application to PLDs . In Proceedings of the IEEE International Conference on Computer Design. 628--633 . Malik, A., Harrison, D., and Brayton, R. 1991. Three-level decomposition with application to PLDs. In Proceedings of the IEEE International Conference on Computer Design. 628--633."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.250190"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1987.1270318"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the International Workshop on Logic Synthesis. 8, 11--8:20","author":"Sasao T.","year":"1995","unstructured":"Sasao , T. 1995 . A design method for AND-OR-EXOR three level networks . In Proceedings of the International Workshop on Logic Synthesis. 8, 11--8:20 . Sasao, T. 1995. A design method for AND-OR-EXOR three level networks. In Proceedings of the International Workshop on Logic Synthesis. 8, 11--8:20."},{"volume-title":"Switching Theory for Logic Synthesis","author":"Sasao T.","key":"e_1_2_1_25_1","unstructured":"Sasao , T. 1999. Switching Theory for Logic Synthesis . Kluwer Academic . Sasao, T. 1999. Switching Theory for Logic Synthesis. Kluwer Academic."},{"key":"e_1_2_1_26_1","volume-title":"SIS: A system for sequential circuit synthesis. Tech. Rep. UCB-ERL M92-41","author":"Sentovich E.","year":"1992","unstructured":"Sentovich , E. , Singh , K. , Lavagno , L. , Moon , C., R. Murgai , A. S. , Savoj , H. , Stephan , P. , Brayton , R. , and Sangiovanni-Vincentelli , A. 1992 . SIS: A system for sequential circuit synthesis. Tech. Rep. UCB-ERL M92-41 . University of California at California . Sentovich, E., Singh, K., Lavagno, L., Moon, C., R. Murgai, A. S., Savoj, H., Stephan, P., Brayton, R., and Sangiovanni-Vincentelli, A. 1992. SIS: A system for sequential circuit synthesis. Tech. Rep. UCB-ERL M92-41. University of California at California."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.855944"},{"volume-title":"Logic synthesis and optimization benchmarks user guide, version 3.0","author":"Yang S.","key":"e_1_2_1_29_1","unstructured":"Yang , S. 1991. Logic synthesis and optimization benchmarks user guide, version 3.0 . Microelectronic Center . Yang, S. 1991. Logic synthesis and optimization benchmarks user guide, version 3.0. Microelectronic Center."}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1344418.1344431","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1344418.1344431","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:39:04Z","timestamp":1750253944000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1344418.1344431"}},"subtitle":["Computational complexity, approximability and experiments"],"short-title":[],"issued":{"date-parts":[[2008,4,2]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,4,2]]}},"alternative-id":["10.1145\/1344418.1344431"],"URL":"https:\/\/doi.org\/10.1145\/1344418.1344431","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2008,4,2]]},"assertion":[{"value":"2007-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-04-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}