{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,18]],"date-time":"2025-01-18T21:10:02Z","timestamp":1737234602721,"version":"3.33.0"},"reference-count":10,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"vor","delay-in-days":4097,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp; Computers in Japan"],"published-print":{"date-parts":[[1996,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Among all AND\u2010EXOR expressions that represent a logic function<jats:italic>f<\/jats:italic>, those with a minimum number of products are called minimum AND\u2010EXOR expressions of<jats:italic>f<\/jats:italic>. The number of products in the minimum AND\u2010EXOR expressions of<jats:italic>f<\/jats:italic>is denoted by \u03c4(<jats:italic>f<\/jats:italic>). The minimization algorithms of AND\u2010EXOR expressions take a great deal of time for computing (time complexity<jats:italic>O<\/jats:italic>(2<jats:sup>2<jats:italic>n<\/jats:italic><\/jats:sup>)), where<jats:italic>n<\/jats:italic>is the number of variables. Thus it is necessary to develop a simplification algorithm that does not always find the exact minimum AND\u2010EXOR expressions but runs fast. This paper presents a simplification algorithm of AND\u2010EXOR expressions, which partially guarantees minimality and has the following properties: (1) it computes a minimum AND\u2010EXOR expression for a logic function<jats:italic>f<\/jats:italic>with \u03c4(<jats:italic>f<\/jats:italic>) &lt; 3(<jats:italic>k<\/jats:italic>+ 1), where<jats:italic>k<\/jats:italic>is a nonnegative integer; (2) if an AND\u2010EXOR expression obtained by this algorithm takes less than or equal to 3(<jats:italic>k<\/jats:italic>+ 1) of products, then it is minimum; and (3) its time complexity is<jats:italic>O<\/jats:italic>(\u03c4<jats:sup><jats:italic>kn<\/jats:italic>2+(<jats:italic>k<\/jats:italic>+<jats:italic>C)n<\/jats:italic><\/jats:sup>). From the experimental results for<jats:italic>k<\/jats:italic>= 0, 1, 2, we can conclude that its computational time is practical for<jats:italic>n<\/jats:italic>= 20, 7, 6, respectively. Modifying this algorithm, we present an exact minimization algorithm for 5\u2010variable functions, which is faster than previously known ones.<\/jats:p>","DOI":"10.1002\/scj.4690270302","type":"journal-article","created":{"date-parts":[[2007,7,8]],"date-time":"2007-07-08T10:26:02Z","timestamp":1183890362000},"page":"18-25","source":"Crossref","is-referenced-by-count":0,"title":["A simplification algorithm of and\u2010exor expressions guaranteeing minimality for some class of logic functions"],"prefix":"10.1002","volume":"27","author":[{"given":"Takashi","family":"Hirayama","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yasuaki","family":"Nishitani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"issue":"11","key":"e_1_2_1_2_2","first-page":"765","article-title":"Four variable AND\u2010EXOR minimum expressions and their properties","volume":"74","author":"Koda N.","year":"1991","journal-title":"Trans. I.E.I.C.E."},{"issue":"3","key":"e_1_2_1_3_2","first-page":"135","article-title":"An upper bound on the number of product terms in AND\u2010EXOR minimum expressions","volume":"75","author":"Koda N.","year":"1992","journal-title":"Trans. I.E.I.C.E."},{"issue":"1","key":"e_1_2_1_4_2","first-page":"1","article-title":"A minimization method for AND\u2010EXOR expressions using the lower bound theorem","volume":"76","author":"Koda N.","year":"1993","journal-title":"Trans. I.E.I.C.E."},{"issue":"6","key":"e_1_2_1_5_2","first-page":"260","article-title":"LP characteristic vector of logic functions and its application","volume":"76","author":"Koda N.","year":"1993","journal-title":"Trans. I.E.I.C.E."},{"issue":"3","key":"e_1_2_1_6_2","first-page":"475","article-title":"Lower bounds on size of periodic functions in Exclusive\u2010OR sum\u2010of\u2010products expressions","volume":"77","author":"Nishitani Y.","year":"1994","journal-title":"I.E.I.C.E. Trans. Fundamentals"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"M.PerkowskiandM.Chrzanowska\u2010Jeske.An exact algorithm to minimize mixed\u2010radix exclusive sums of products for incompletely specified Boolean functions.Proc. Int. Symposium on Circuits and Systems'90 pp.1652\u20131655(1990).","DOI":"10.1109\/ISCAS.1990.112455"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.45212"},{"key":"e_1_2_1_9_2","doi-asserted-by":"crossref","unstructured":"T.Sasao.EXMIN: A simplification algorithm for exclusive\u2010OR\u2010sum\u2010of\u2010products expressions for multiple\u2010valued input two\u2010valued output functions. Int. Symposium on Multiple\u2010Valued Logic '90 pp.128\u2013135(1990).","DOI":"10.1109\/ISMVL.1990.122597"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/43.277608"},{"key":"e_1_2_1_11_2","unstructured":"T.SasaoandM.Matsuura.A method for deriving exact minimum AND\u2010EXOR expressions using binary decision diagrams.Technical Report of I.E.I.C.E. VLD93\u201058 pp.55\u201360(Oct.1993)."}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690270302","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690270302","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,18]],"date-time":"2025-01-18T20:29:45Z","timestamp":1737232185000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690270302"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,1]]},"references-count":10,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1996,1]]}},"alternative-id":["10.1002\/scj.4690270302"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690270302","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"type":"print","value":"0882-1666"},{"type":"electronic","value":"1520-684X"}],"subject":[],"published":{"date-parts":[[1996,1]]}}}