{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T06:10:25Z","timestamp":1697868625917},"reference-count":4,"publisher":"Wiley","issue":"9","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"vor","delay-in-days":7749,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems & Computers in Japan"],"published-print":{"date-parts":[[1986,1]]},"abstract":"Abstract<\/jats:title>In CMOS circuits transistors in a p\u2010MOS circuit and n\u2010MOS circuit that have a common gate input are often placed next to each other. In such a case, if adjacent diffusion areas are of the same potential, it is possible to merge them to reduce the circuit area. Therefore an important problem is how to obtain efficiently a circuit layout with the minimum number of places (separation) where the merge is impossible. At present, it is known that the minimum separation is zero in a tree\u2010shape monotone decreasing logic circuit when the fan\u2010in number of each logic element is odd. However, the time complexity for obtaining the minimum separation for a given arbitrary circuit has not been reported yet. This paper shows that the following problems can be solved in a time linear to the sum of the number of the logical variables and the number of the logic elements where k<\/jats:italic> or h<\/jats:italic> is a constant when a tree\u2010shape monotone decreasing logic circuit C<\/jats:italic> and a nonnegative integer k<\/jats:italic> are given, determining whether or not there exists a layout of C<\/jats:italic> having separation k<\/jats:italic> or less. If one exists, obtain the minimum separation and a layout with the minimum; and obtain the minimum separation and a layout with the minimum when the fan\u2010in of each logic element of C<\/jats:italic> is h<\/jats:italic> or less.<\/jats:p>","DOI":"10.1002\/scj.4690170901","type":"journal-article","created":{"date-parts":[[2007,7,7]],"date-time":"2007-07-07T12:32:20Z","timestamp":1183811540000},"page":"1-10","source":"Crossref","is-referenced-by-count":0,"title":["Minimum separation layout for cmos circuits realizing tree\u2010shape monotone decreasing logic circuits"],"prefix":"10.1002","volume":"17","author":[{"given":"Yoshifumi","family":"Manabe","sequence":"first","affiliation":[]},{"given":"Ken'Ichi","family":"Hagihara","sequence":"additional","affiliation":[]},{"given":"Nobuki","family":"Tokura","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Mathematics for electronic communications II. Discrete structures","author":"Fujisawa T.","year":"1979"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.21236\/AD0705364"},{"key":"e_1_2_1_4_2","first-page":"103","article-title":"Compact layouts for CMOS Circuits of monotone decreasing functions","volume":"84","author":"Manabe Y.","year":"1984","journal-title":"Papers of Technical Group on Circuits and Systems"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675787"}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690170901","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690170901","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T17:15:40Z","timestamp":1697822140000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690170901"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,1]]},"references-count":4,"journal-issue":{"issue":"9","published-print":{"date-parts":[[1986,1]]}},"alternative-id":["10.1002\/scj.4690170901"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690170901","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,1]]}}}