{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T07:20:03Z","timestamp":1790752803605,"version":"4.1.0"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["JU 3105\/1-2"],"award-info":[{"award-number":["JU 3105\/1-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>The problem of constructing hazard-free Boolean circuits (those avoiding electronic glitches) dates back to the 1940s and is an important problem in circuit design and even in cybersecurity. We show that a DeMorgan circuit, that is, a Boolean AND, OR, NOT circuit with negations applied to only input variables, is hazard-free iff the circuit produces (purely syntactically) all prime implicants as well as all prime implicates of the Boolean function it computes. This extends to arbitrary DeMorgan circuits a classical result of Eichelberger [ IBM J. Res. Develop., 9 (1965), pp. 90--99] showing this property for circuits producing no terms containing a variable together with its negation. Via an amazingly simple proof, we also strengthen a recent result of Ikenmeyer et al. [ J. ACM, 66 (2019), 25]: not only do the complexities of hazard-free and monotone circuits for monotone Boolean functions coincide, but every minimal hazard-free circuit for a monotone Boolean function must be monotone. We also observe that hazard-free implementations of already very simple Boolean functions require a superpolynomial increase of circuit size and depth, such as, for example, the Boolean function which accepts a Boolean square matrix iff every row and every column has exactly one $1$. Finally, we show that the order of growth of the Shannon function of hazard-free circuits is the same as that of unrestricted circuits.<\/jats:p>","DOI":"10.1137\/20m1355240","type":"journal-article","created":{"date-parts":[[2021,4,13]],"date-time":"2021-04-13T10:27:46Z","timestamp":1618309666000},"page":"770-787","source":"Crossref","is-referenced-by-count":7,"title":["Notes on Hazard-Free Circuits"],"prefix":"10.1137","volume":"35","author":[{"given":"Stasys","family":"Jukna","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,4,13]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579196"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90110-X"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90018-8"},{"key":"atypb4","unstructured":"A. Blake,\n                      Canonical Expressions in Boolean Algebras\n                      , Ph.D. thesis, Department of Mathematics, University of Chicago, 1937."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(72)90299-9"},{"key":"atypb6","unstructured":"S. H. Cadwell,\n                      Switching Circuits and Logical Design\n                      , John Wiley $\\&$ Sons, New York, 1958."},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"Y. Crama and P. L. Hammer, eds.\n                      Boolean Functions: Theory, Algorithms, and Applications\n                      , Encyclopedia Math. Appl. 142, Cambridge University Press, Cambridge, UK, 2011.","DOI":"10.1017\/CBO9780511852008"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1147\/rd.92.0090"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2012.2189105"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/320856.320866"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1145\/3320123"},{"key":"atypb14","unstructured":"S. C. Kleene,\n                      Introduction to Metamathematics\n                      , North-Holland, Amsterdam, 1952."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2020.105980"},{"key":"atypb16","unstructured":"S. K\u00f6rner,\n                      Experience and Theory: An Essay in the Philosophy of Science\n                      , Routledge & Kegan Paul, London, 1966."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"atypb18","first-page":"42","volume":"43","author":"Malinowski G.","year":"2014","journal-title":"Bull. Section Logic"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(74)80004-5"},{"key":"atypb20","unstructured":"M. Mukaidono,\n                      The B-ternary logic and its applications to the detection of hazards in combinational switching circuits\n                      , in Proceedings of the 8th International Symposium on Multiple-Valued Logic, 1978, pp. 269-275."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1956.5219786"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1955.11988710"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146684"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/BF01157687"},{"key":"atypb25","unstructured":"E. W. Samson and B. E. Mills,\n                      Circuit Minimization: Algebra and Algorithms for New Boolean Canonical Expressions\n                      , Tech. report TR 54-21, Air Force Cambridge Research Center, 1954."},{"key":"atypb26","unstructured":"N. Saurabh,\n                      private communication\n                      , 2020."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1949.tb03624.x"},{"key":"atypb28","first-page":"141","volume":"7","author":"Tardos E.","year":"1987","journal-title":"Combinatorica"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1145\/2528521.1508258"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"I. Wegener,\n                      The Complexity of Boolean Functions\n                      , Wiley-Teubner, New York, 1987.","DOI":"10.1007\/3-540-18170-9_185"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1145\/321203.321214"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1355240","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:43:54Z","timestamp":1787319834000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1355240"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1355240"],"URL":"https:\/\/doi.org\/10.1137\/20m1355240","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}