{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T05:50:46Z","timestamp":1750830646890,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,12,9]],"date-time":"2015-12-09T00:00:00Z","timestamp":1449619200000},"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":["J. Emerg. Technol. Comput. Syst."],"published-print":{"date-parts":[[2016,7,26]]},"abstract":"<jats:p>Reversible logic represents the basis for many emerging technologies and has recently been intensively studied. However, most of the Boolean functions of practical interest are irreversible and must be embedded into a reversible function before they can be synthesized. Thus far, an optimal embedding is guaranteed only for small functions, whereas a significant overhead results when large functions are considered. We study this issue in this article. We prove that determining an optimal embedding is coNP-hard already for restricted cases. Then, we propose heuristic and exact methods for determining both the number of additional lines and a corresponding embedding. For the approaches, we considered sum of products and binary decision diagrams as function representations. Experimental evaluations show the applicability of the approaches for large functions. Consequently, the reversible embedding of large functions is enabled as a precursor to subsequent synthesis.<\/jats:p>","DOI":"10.1145\/2786982","type":"journal-article","created":{"date-parts":[[2015,12,14]],"date-time":"2015-12-14T14:19:41Z","timestamp":1450102781000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["Embedding of Large Boolean Functions for Reversible Logic"],"prefix":"10.1145","volume":"12","author":[{"given":"Mathias","family":"Soeken","sequence":"first","affiliation":[{"name":"Faculty of Mathematics and Computer Science, University of Bremen, Germany, Cyber-Physical Systems, DFKI GmbH, Germany"}]},{"given":"Robert","family":"Wille","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics and Computer Science, University of Bremen, Germany, Cyber-Physical Systems, DFKI GmbH, Germany"}]},{"given":"Oliver","family":"Keszocze","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics and Computer Science, University of Bremen, Germany, Cyber-Physical Systems, DFKI GmbH, Germany"}]},{"given":"D. Michael","family":"Miller","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Victoria, BC, Canada"}]},{"given":"Rolf","family":"Drechsler","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics and Computer Science, University of Bremen, Germany, Cyber-Physical Systems, DFKI GmbH, Germany"}]}],"member":"320","published-online":{"date-parts":[[2015,12,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.176.0525"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9447-2"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676819"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.3934\/amc.2008.2.183"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2009.2017215"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/367651.367661"},{"key":"e_1_2_1_7_1","unstructured":"Donald E. Knuth. 2011. The Art of Computer Programming. Vol. 4A. Addison-Wesley Upper Saddle River NJ.  Donald E. Knuth. 2011. The Art of Computer Programming. Vol. 4A. Addison-Wesley Upper Saddle River NJ."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2564923"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/775832.775915"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2006.35"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSD.2009.186"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00368-6"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the European Safety and Reliability Association Conference. 1459--1465","author":"Nikolskaia Macha","year":"1998","unstructured":"Macha Nikolskaia and Antoine Rauzy . 1998 . Heuristics for BDD handling of sum-of-products formulae . In Proceedings of the European Safety and Reliability Association Conference. 1459--1465 . Macha Nikolskaia and Antoine Rauzy. 1998. Heuristics for BDD handling of sum-of-products formulae. In Proceedings of the European Safety and Reliability Association Conference. 1459--1465."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the International Workshop on Logic Synthesis.","author":"Padmanabhan Balasubramanian","year":"2010","unstructured":"Balasubramanian Padmanabhan and Doug Edwards . 2010 . Self-timed realization of combinational logic . In Proceedings of the International Workshop on Logic Synthesis. Balasubramanian Padmanabhan and Doug Edwards. 2010. Self-timed realization of combinational logic. In Proceedings of the International Workshop on Logic Synthesis."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-AIEE.1938.5057767"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2003.811448"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29517-1_6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2015.03.002"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2012.6165069"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629911.1629984"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/DATE.2011.5763314"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837274.1837439"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.vlsi.2013.08.002"}],"container-title":["ACM Journal on Emerging Technologies in Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2786982","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2786982","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:26Z","timestamp":1750223246000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2786982"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,9]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,7,26]]}},"alternative-id":["10.1145\/2786982"],"URL":"https:\/\/doi.org\/10.1145\/2786982","relation":{},"ISSN":["1550-4832","1550-4840"],"issn-type":[{"type":"print","value":"1550-4832"},{"type":"electronic","value":"1550-4840"}],"subject":[],"published":{"date-parts":[[2015,12,9]]},"assertion":[{"value":"2014-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}