{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T14:22:21Z","timestamp":1766067741989,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2023,9,9]],"date-time":"2023-09-09T00:00:00Z","timestamp":1694217600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science and Technology Council","award":["MOST 109-2221-E-007-082-MY2, MOST 109-2221-E-155-047-MY2, MOST 110-2224-E-007-007, MOST 111-2218-E-007-010, MOST 111-2221-E-007-121, MOST 111-2221-E-011-137-MY3, NSTC 112-2218-E-007-014, and NSTC 112-2425-H-007-002"],"award-info":[{"award-number":["MOST 109-2221-E-007-082-MY2, MOST 109-2221-E-155-047-MY2, MOST 110-2224-E-007-007, MOST 111-2218-E-007-010, MOST 111-2221-E-007-121, MOST 111-2221-E-011-137-MY3, NSTC 112-2218-E-007-014, and NSTC 112-2425-H-007-002"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2023,9,30]]},"abstract":"<jats:p>Threshold Function (TF) is a subset of Boolean function that can be represented with a single linear threshold gate (LTG). In the research about threshold logic, the identification of TF is an important task that determines whether a given function is a TF or not. In this article, we propose a sufficient and necessary condition for a function being a TF. With the proposed sufficient and necessary condition, we devise a TF identification algorithm. The experimental results show that the proposed approach saves 80% CPU time for identifying all the 8-input NP-class TFs as compared with the state-of-the-art. Furthermore, the LTGs corresponding to the identified TFs obtained by the proposed approach have smaller weights and threshold values than the state-of-the-art.<\/jats:p>","DOI":"10.1145\/3606371","type":"journal-article","created":{"date-parts":[[2023,6,30]],"date-time":"2023-06-30T11:56:38Z","timestamp":1688126198000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A Constructive Approach for Threshold Function Identification"],"prefix":"10.1145","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-1283-1310","authenticated-orcid":false,"given":"Meng-Jing","family":"Li","sequence":"first","affiliation":[{"name":"National Tsing Hua University, Taiwan"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-4867-9758","authenticated-orcid":false,"given":"Yu-Chuan","family":"Yen","sequence":"additional","affiliation":[{"name":"National Tsing Hua University, Taiwan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5297-9420","authenticated-orcid":false,"given":"Yi-Ting","family":"Li","sequence":"additional","affiliation":[{"name":"National Tsing Hua University, Taiwan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3934-800X","authenticated-orcid":false,"given":"Yung-Chih","family":"Chen","sequence":"additional","affiliation":[{"name":"National Taiwan University of Science and Technology, Taiwan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4536-214X","authenticated-orcid":false,"given":"Chun-Yao","family":"Wang","sequence":"additional","affiliation":[{"name":"National Tsing Hua University, Taiwan"}]}],"member":"320","published-online":{"date-parts":[[2023,9,9]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"Gurobi. https:\/\/www.gurobi.com\/."},{"issue":"21","key":"e_1_3_1_3_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1049\/el:20030989","article-title":"Multi-threshold threshold logic circuit design using resonant tunnelling devices","volume":"39","author":"Avedillo M. J.","year":"2003","unstructured":"M. J. Avedillo, J. M. Quintana, H. Pettenghi, P. M. Kelly, and C. J. Thompson. 2003. Multi-threshold threshold logic circuit design using resonant tunnelling devices. Electron. Lett. 39, 21 (2003), 1.","journal-title":"Electron. Lett."},{"key":"e_1_3_1_4_2","first-page":"1","volume-title":"57th ACM\/IEEE Design Automation Conference (DAC\u201920)","author":"Chen Yung-Chih","year":"2020","unstructured":"Yung-Chih Chen, Hao-Ju Chang, and Li-Cheng Zheng. 2020. Don\u2019t-care-based node minimization for threshold logic networks. In 57th ACM\/IEEE Design Automation Conference (DAC\u201920). IEEE, 1\u20136."},{"key":"e_1_3_1_5_2","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1109\/FOCS.1961.39","volume-title":"2nd Annual Symposium on Switching Circuit Theory and Logical Design (SWCT\u201961)","author":"Elgot Calvin C.","year":"1961","unstructured":"Calvin C. Elgot. 1961. Truth functions realizable by single threshold organs. In 2nd Annual Symposium on Switching Circuit Theory and Logical Design (SWCT\u201961). IEEE, 225\u2013245."},{"issue":"5","key":"e_1_3_1_6_2","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1109\/T-C.1972.223551","article-title":"Simple methods for the testing of 2-summability of Boolean functions and isobaricity of threshold functions","volume":"100","author":"Ghosh Sukumar","year":"1972","unstructured":"Sukumar Ghosh, Subir Bandyopadhyay, Sanjit Kumar Mitra, and Arun Kumar Choudhury. 1972. Simple methods for the testing of 2-summability of Boolean functions and isobaricity of threshold functions. IEEE Trans. Comput. 100, 5 (1972), 503\u2013507.","journal-title":"IEEE Trans. Comput."},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/5.573739"},{"key":"e_1_3_1_8_2","first-page":"146","volume-title":"IEEE 34th International System-on-Chip Conference (SOCC\u201921)","author":"Hsu Wen-Chih","year":"2021","unstructured":"Wen-Chih Hsu, Chia-Chun Lin, Yi-Ting Li, Yung-Chih Chen, and Chun-Yao Wang. 2021. On reduction of computations for threshold function identification. In IEEE 34th International System-on-Chip Conference (SOCC\u201921). IEEE, 146\u2013151."},{"key":"e_1_3_1_9_2","first-page":"396","volume-title":"IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201911)","author":"Kuo Pin-Yi","year":"2011","unstructured":"Pin-Yi Kuo, Chun-Yao Wang, and Ching-Yi Huang. 2011. On rewiring and simplification for canonicity in threshold logic circuits. In IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201911). IEEE, 396\u2013403."},{"key":"e_1_3_1_10_2","first-page":"1","volume-title":"IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201918)","author":"Lee Siang-Yun","year":"2018","unstructured":"Siang-Yun Lee, Nian-Ze Lee, and Jie-Hong R. Jiang. 2018. Canonicalization of threshold logic representation and its applications. In IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201918). IEEE, 1\u20138."},{"key":"e_1_3_1_11_2","first-page":"1","volume-title":"IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201919)","author":"Lee Siang-Yun","year":"2019","unstructured":"Siang-Yun Lee, Nian-Ze Lee, and Jie-Hong R. Jiang. 2019. Searching parallel separating hyperplanes for effective compression of threshold logic networks. In IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201919). IEEE, 1\u20138."},{"key":"e_1_3_1_12_2","first-page":"413","volume-title":"18th International Symposium on Quality Electronic Design (ISQED\u201917)","author":"Lin Chia-Chun","year":"2017","unstructured":"Chia-Chun Lin, Chiao-Wei Huang, Chun-Yao Wang, and Yung-Chih Chen. 2017. In&Out: Restructuring for threshold logic network optimization. In 18th International Symposium on Quality Electronic Design (ISQED\u201917). IEEE, 413\u2013418."},{"issue":"5","key":"e_1_3_1_13_2","first-page":"1412","article-title":"Don\u2019t care computation and De Morgan transformation for threshold logic network optimization","volume":"41","author":"Lin Chia-Chun","year":"2021","unstructured":"Chia-Chun Lin, Ciao-Syun Lin, You-Hsuen Tsai, Yung-Chih Chen, and Chun-Yao Wang. 2021. Don\u2019t care computation and De Morgan transformation for threshold logic network optimization. IEEE Trans. Comput.-Aid. Des. Integ. Circ. Syst. 41, 5 (2021), 1412\u20131422.","journal-title":"IEEE Trans. Comput.-Aid. Des. Integ. Circ. Syst."},{"issue":"12","key":"e_1_3_1_14_2","doi-asserted-by":"crossref","first-page":"5304","DOI":"10.1109\/TCAD.2020.2964768","article-title":"A new necessary condition for threshold function identification","volume":"39","author":"Lin Chia-Chun","year":"2020","unstructured":"Chia-Chun Lin, Chin-Heng Liu, Yung-Chih Chen, and Chun-Yao Wang. 2020. A new necessary condition for threshold function identification. IEEE Trans. Comput.-Aid. Des. Integ. Circ. Syst. 39, 12 (2020), 5304\u20135308.","journal-title":"IEEE Trans. Comput.-Aid. Des. Integ. Circ. Syst."},{"key":"e_1_3_1_15_2","first-page":"1","volume-title":"Design, Automation & Test in Europe Conference & Exhibition (DATE\u201914)","author":"Lin Chia-Chun","year":"2014","unstructured":"Chia-Chun Lin, Chun-Yao Wang, Yung-Chih Chen, and Ching-Yi Huang. 2014. Rewiring for threshold logic circuit minimization. In Design, Automation & Test in Europe Conference & Exhibition (DATE\u201914). IEEE, 1\u20136."},{"issue":"12","key":"e_1_3_1_16_2","first-page":"2284","article-title":"Threshold function identification by redundancy removal and comprehensive weight assignments","volume":"38","author":"Liu Chin-Heng","year":"2018","unstructured":"Chin-Heng Liu, Chia-Chun Lin, Yung-Chih Chen, Chia-Cheng Wu, Chun-Yao Wang, and Shigeru Yamashita. 2018. Threshold function identification by redundancy removal and comprehensive weight assignments. IEEE Trans. Comput.-Aid. Des. Integ. Circ. Syst. 38, 12 (2018), 2284\u20132297.","journal-title":"IEEE Trans. Comput.-Aid. Des. Integ. Circ. Syst."},{"issue":"9","key":"e_1_3_1_17_2","doi-asserted-by":"crossref","first-page":"2476","DOI":"10.1109\/TC.2014.2366745","article-title":"Automated design architecture for 1-D cellular automata using quantum cellular automata","volume":"64","author":"Mardiris Vassilios A.","year":"2014","unstructured":"Vassilios A. Mardiris, Georgios Ch. Sirakoulis, and Ioannis G. Karafyllidis. 2014. Automated design architecture for 1-D cellular automata using quantum cellular automata. IEEE Trans. Comput. 64, 9 (2014), 2476\u20132489.","journal-title":"IEEE Trans. Comput."},{"key":"e_1_3_1_18_2","volume-title":"Threshold Logic and Its Applications","author":"Muroga Saburo","year":"1971","unstructured":"Saburo Muroga. 1971. Threshold Logic and Its Applications. Wiley, New York, NY."},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-62-99195-0"},{"issue":"9","key":"e_1_3_1_20_2","doi-asserted-by":"crossref","first-page":"818","DOI":"10.1109\/T-C.1970.223046","article-title":"Enumeration of threshold functions of eight variables","volume":"100","author":"Muroga Saburo","year":"1970","unstructured":"Saburo Muroga, Teiichi Tsuboi, and Charles Richmond Baugh. 1970. Enumeration of threshold functions of eight variables. IEEE Trans. Comput. 100, 9 (1970), 818\u2013825.","journal-title":"IEEE Trans. Comput."},{"issue":"5","key":"e_1_3_1_21_2","first-page":"1023","article-title":"A simple and effective heuristic method for threshold logic identification","volume":"37","author":"Neutzling Augusto","year":"2017","unstructured":"Augusto Neutzling, Mayler G. A. Martins, Vinicius Callegaro, Andre I. Reis, and Renato P. Ribas. 2017. A simple and effective heuristic method for threshold logic identification. IEEE Trans. Comput.-Aid. Des. Integ. Circ. Syst. 37, 5 (2017), 1023\u20131036.","journal-title":"IEEE Trans. Comput.-Aid. Des. Integ. Circ. Syst."},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCSI.2019.2902475"},{"issue":"3","key":"e_1_3_1_23_2","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1166\/jolpe.2010.1089","article-title":"Energy-delay performance of nanoscale transistors exhibiting single electron behavior and associated logic circuits","volume":"6","author":"Saripalli Vinay","year":"2010","unstructured":"Vinay Saripalli, Lu Liu, Suman Datta, and Vijaykrishnan Narayanan. 2010. Energy-delay performance of nanoscale transistors exhibiting single electron behavior and associated logic circuits. J. Low Power Electron. 6, 3 (2010), 415\u2013428.","journal-title":"J. Low Power Electron."},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675250"},{"key":"e_1_3_1_25_2","first-page":"226","volume-title":"IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201913)","author":"Tsai Chen-Kuan","year":"2013","unstructured":"Chen-Kuan Tsai, Chun-Yao Wang, Ching-Yi Huang, and Yung-Chih Chen. 2013. Sensitization criterion for threshold logic circuits and its application. In IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201913). IEEE, 226\u2013233."},{"key":"e_1_3_1_26_2","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1109\/FOCS.1961.29","volume-title":"2nd Annual Symposium on Switching Circuit Theory and Logical Design (SWCT\u201961)","author":"Winder Robert O.","year":"1961","unstructured":"Robert O. Winder. 1961. Single stage threshold logic. In 2nd Annual Symposium on Switching Circuit Theory and Logical Design (SWCT\u201961). IEEE, 321\u2013332."},{"issue":"1","key":"e_1_3_1_27_2","first-page":"107","article-title":"Threshold network synthesis and optimization and its application to nanotechnologies","volume":"24","author":"Zhang Rui","year":"2004","unstructured":"Rui Zhang, Pallav Gupta, Lin Zhong, and Niraj K. Jha. 2004. Threshold network synthesis and optimization and its application to nanotechnologies. IEEE Trans. Comput.-Aid. Des. Integ. Circ. Syst. 24, 1 (2004), 107\u2013118.","journal-title":"IEEE Trans. Comput.-Aid. Des. Integ. Circ. Syst."}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3606371","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3606371","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:09Z","timestamp":1750178829000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3606371"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,9]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1145\/3606371"],"URL":"https:\/\/doi.org\/10.1145\/3606371","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2023,9,9]]},"assertion":[{"value":"2022-11-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-08","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}