{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:51:12Z","timestamp":1758268272274,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":50,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"EPSRC","award":["POETS EP\/N031768\/1"],"award-info":[{"award-number":["POETS EP\/N031768\/1"]}]},{"name":"ERC","award":["716562"],"award-info":[{"award-number":["716562"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188912","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"878-889","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["On the complexity of hazard-free circuits"],"prefix":"10.1145","author":[{"given":"Christian","family":"Ikenmeyer","sequence":"first","affiliation":[{"name":"Max Planck Institute for Informatics, Germany"}]},{"given":"Balagopal","family":"Komarath","sequence":"additional","affiliation":[{"name":"Saarland University, Germany"}]},{"given":"Christoph","family":"Lenzen","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Germany"}]},{"given":"Vladimir","family":"Lysikov","sequence":"additional","affiliation":[{"name":"Saarland University, Germany \/ M2CI, Germany"}]},{"given":"Andrey","family":"Mokhov","sequence":"additional","affiliation":[{"name":"Newcastle University, UK"}]},{"given":"Karteek","family":"Sreenivasaiah","sequence":"additional","affiliation":[{"name":"IIT Hyderabad, India"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579196"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018353700639"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/31846.31852"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/876894.880877"},{"key":"e_1_3_2_2_5_1","volume-title":"Theoretical Computer Science, 36(Supplement C):59 \u2013 69","author":"Blum Norbert","year":"1985","unstructured":"{Blu85} Norbert Blum . An \u03c9 (n 4 \/3 ) lower bound on the monotone network complexity of the nth degree convolution. Theoretical Computer Science, 36(Supplement C):59 \u2013 69 , 1985 . {Blu85} Norbert Blum. An \u03c9 (n 4 \/3 ) lower bound on the monotone network complexity of the nth degree convolution. Theoretical Computer Science, 36(Supplement C):59 \u2013 69, 1985."},{"key":"e_1_3_2_2_6_1","volume-title":"Some applications of ternary algebras. Publicationes Mathematicae (Debrecen), 54(Supplement):583\u2013599","author":"Brzozowski J. A.","year":"1999","unstructured":"{Brz99} J. A. Brzozowski . Some applications of ternary algebras. Publicationes Mathematicae (Debrecen), 54(Supplement):583\u2013599 , 1999 . {Brz99} J. A. Brzozowski. Some applications of ternary algebras. Publicationes Mathematicae (Debrecen), 54(Supplement):583\u2013599, 1999."},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4210-9"},{"key":"e_1_3_2_2_8_1","volume-title":"Switching Circuits and Logical Design","author":"Caldwell Samuel H.","year":"1958","unstructured":"{Cal58} Samuel H. Caldwell . Switching Circuits and Logical Design . John Wiley & amp; Sons Inc, 1958 . {Cal58} Samuel H. Caldwell. Switching Circuits and Logical Design. John Wiley & Sons Inc, 1958."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90168-1"},{"key":"e_1_3_2_2_10_1","volume-title":"Discrete and switching functions","author":"Davio Marc","year":"1978","unstructured":"{DDT78} Marc Davio , Jean-Pierre Deschamps , and Andr\u00e9 Thays\u00e9 . Discrete and switching functions . McGraw-Hill International Book Co. , 1978 . {DDT78} Marc Davio, Jean-Pierre Deschamps, and Andr\u00e9 Thays\u00e9. Discrete and switching functions. McGraw-Hill International Book Co., 1978."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2011.10.013"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.92.0090"},{"key":"e_1_3_2_2_13_1","volume-title":"A Mathematical Introduction to Logic","author":"Enderton Herbert B.","year":"2001","unstructured":"{End01} Herbert B. Enderton . A Mathematical Introduction to Logic . Academic Press , 2 nd edition, 2001 . {End01} Herbert B. Enderton. A Mathematical Introduction to Logic. Academic Press, 2nd edition, 2001.","edition":"2"},{"key":"e_1_3_2_2_14_1","author":"Friedrichs Stephan","year":"2018","unstructured":"{FFL18} Stephan Friedrichs , Matthias F\u00fcgger , and Christoph Lenzen . Metastability-Containing Circuits . IEEE Transactions on Computers , 2018 . {FFL18} Stephan Friedrichs, Matthias F\u00fcgger, and Christoph Lenzen. Metastability-Containing Circuits. IEEE Transactions on Computers, 2018.","journal-title":"IEEE Transactions on Computers"},{"key":"e_1_3_2_2_16_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey Michael R.","year":"1979","unstructured":"{GJ79} Michael R. Garey and David S. Johnson . Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman & amp; Co., New York, NY, USA, 1979 . {GJ79} Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979."},{"key":"e_1_3_2_2_17_1","volume-title":"Valiant\u2019s polynomial-size monotone formula for Majority. online available: http:\/\/www.wisdom.weizmann.ac.il\/~oded\/PDF\/ monomaj.pdf","author":"Goldreich Oded","year":"2011","unstructured":"{Gol11} Oded Goldreich . Valiant\u2019s polynomial-size monotone formula for Majority. online available: http:\/\/www.wisdom.weizmann.ac.il\/~oded\/PDF\/ monomaj.pdf , 2011 . {Gol11} Oded Goldreich. Valiant\u2019s polynomial-size monotone formula for Majority. online available: http:\/\/www.wisdom.weizmann.ac.il\/~oded\/PDF\/ monomaj.pdf, 2011."},{"key":"e_1_3_2_2_18_1","first-page":"32","volume-title":"Proc. Joint Meeting IEE, IECE, and I. of Illum E. of Japan, \u96fb\u6c17\u4e09 \u5b66\u4f1a\u6771\u4eac\u652f\u90e8\u9023\u5408\u5927\u4f1a\u8b1b\u6f14\u8981\u65e8. \u662d\u548c22\u30fb23\u5e74","author":"Goto M.","year":"1948","unstructured":"{Got48} M. Goto . Application of Three-Valued Logic to Construct the Theory of Relay Networks (in Japanese) \u4e09\u5024\u8ad6\u7406\u5b66 \u306e\u7d99\u96fb\u5668\u56de\u8def\u7db2\u7406\u8ad6\u3078\u306e \u61c9\u7528 . Proc. Joint Meeting IEE, IECE, and I. of Illum E. of Japan, \u96fb\u6c17\u4e09 \u5b66\u4f1a\u6771\u4eac\u652f\u90e8\u9023\u5408\u5927\u4f1a\u8b1b\u6f14\u8981\u65e8. \u662d\u548c22\u30fb23\u5e74 , pages 31\u2013 32 , 1948 . {Got48} M. Goto. Application of Three-Valued Logic to Construct the Theory of Relay Networks (in Japanese) \u4e09\u5024\u8ad6\u7406\u5b66 \u306e\u7d99\u96fb\u5668\u56de\u8def\u7db2\u7406\u8ad6\u3078\u306e \u61c9\u7528. Proc. Joint Meeting IEE, IECE, and I. of Illum E. of Japan, \u96fb\u6c17\u4e09 \u5b66\u4f1a\u6771\u4eac\u652f\u90e8\u9023\u5408\u5927\u4f1a\u8b1b\u6f14\u8981\u65e8. \u662d\u548c22\u30fb23\u5e74, pages 31\u201332, 1948."},{"issue":"726","key":"e_1_3_2_2_19_1","first-page":"125","article-title":"Application of logical mathematics to the theory of relay networks (in Japanese)","volume":"64","author":"Goto M.","year":"1949","unstructured":"{Got49} M. Goto . Application of logical mathematics to the theory of relay networks (in Japanese) . J. Inst. Elec. Eng. of Japan , 64 ( 726 ): 125 \u2013 130 , 1949 . {Got49} M. Goto. Application of logical mathematics to the theory of relay networks (in Japanese). J. Inst. Elec. Eng. of Japan, 64(726):125\u2013130, 1949.","journal-title":"J. Inst. Elec. Eng. of Japan"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511526633.006"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2012.2189105"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/320856.320866"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.2307\/2267778"},{"key":"e_1_3_2_2_24_1","volume-title":"North Holland","author":"Kleene Stephen Cole","year":"1952","unstructured":"{Kle52} Stephen Cole Kleene . Introduction to Metamathematics . North Holland , 1952 . {Kle52} Stephen Cole Kleene. Introduction to Metamathematics. North Holland, 1952."},{"key":"e_1_3_2_2_25_1","volume-title":"International library of philosophy and scientific method","author":"K\u00f6rner Stephan","year":"1966","unstructured":"{K\u00f6r66} Stephan K\u00f6rner . Experience and theory : an essay in the philosophy of science . International library of philosophy and scientific method . Routledge & amp; Kegan Paul, London, 1966 . {K\u00f6r66} Stephan K\u00f6rner. Experience and theory : an essay in the philosophy of science. International library of philosophy and scientific method. Routledge & Kegan Paul, London, 1966."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_2_2_27_1","volume-title":"Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS, (105):41\u201371","author":"Lokshtanov Daniel","year":"2011","unstructured":"{LMS11} Daniel Lokshtanov , D\u00e1niel Marx , and Saket Saurabh . Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS, (105):41\u201371 , 2011 . {LMS11} Daniel Lokshtanov, D\u00e1niel Marx, and Saket Saurabh. Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS, (105):41\u201371, 2011."},{"issue":"1","key":"e_1_3_2_2_28_1","first-page":"42","article-title":"Kleene logic and inference","volume":"43","author":"Malinowski Grzegorz","year":"2014","unstructured":"{Mal14} Grzegorz Malinowski . Kleene logic and inference . Bulletin of the Section of Logic , 43 ( 1\/2 ): 42 \u2013 52 , 2014 . {Mal14} Grzegorz Malinowski. Kleene logic and inference. Bulletin of the Section of Logic, 43(1\/2):42\u201352, 2014.","journal-title":"Bulletin of the Section of Logic"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1963635.1963638"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02241983"},{"issue":"3","key":"e_1_3_2_2_31_1","first-page":"27","article-title":"On the b-ternary logical function - a ternary logic considering ambiguity. Systems, Computers","volume":"3","author":"Mukaidono M.","year":"1972","unstructured":"{Muk72} M. Mukaidono . On the b-ternary logical function - a ternary logic considering ambiguity. Systems, Computers , Controls , 3 ( 3 ): 27 \u2013 36 , 1972 . {Muk72} M. Mukaidono. On the b-ternary logical function - a ternary logic considering ambiguity. Systems, Computers, Controls, 3(3):27\u201336, 1972.","journal-title":"Controls"},{"key":"e_1_3_2_2_32_1","first-page":"349","volume-title":"Advances in Fuzzy Sets, Possibility Theory and Applications","author":"Mukaidono M.","unstructured":"{Muk83a} M. Mukaidono . Advanced results on application of fuzzy switching functions to hazard detection . In P.P. Wong, editor, Advances in Fuzzy Sets, Possibility Theory and Applications , pages 335\u2013 349 . Plenum Publishing Corporation, 1983. {Muk83a} M. Mukaidono. Advanced results on application of fuzzy switching functions to hazard detection. In P.P. Wong, editor, Advances in Fuzzy Sets, Possibility Theory and Applications, pages 335\u2013349. Plenum Publishing Corporation, 1983."},{"key":"e_1_3_2_2_33_1","first-page":"291","volume-title":"Proc. 13th International Symposium on Multiple-Valued Logic","author":"Mukaidono M.","unstructured":"{Muk83b} M. Mukaidono . Regular ternary logic functions \u2013 ternary logic functions suitable for treating ambiguity . In Proc. 13th International Symposium on Multiple-Valued Logic , pages 286\u2013 291 . IEEE Computer Society Press, 1983. {Muk83b} M. Mukaidono. Regular ternary logic functions \u2013 ternary logic functions suitable for treating ambiguity. In Proc. 13th International Symposium on Multiple-Valued Logic, pages 286\u2013291. IEEE Computer Society Press, 1983."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/110316.110388"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294256"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(75)90009-2"},{"key":"e_1_3_2_2_37_1","volume-title":"Ram\u00edrez-Figueroa. Intelligent Control Systems with LabVIEW","author":"Ponce-Cruz Pedro","year":"1979","unstructured":"{PCRF79} Pedro Ponce-Cruz and Fernando D . Ram\u00edrez-Figueroa. Intelligent Control Systems with LabVIEW . Springer-Verlag London , 1979 . {PCRF79} Pedro Ponce-Cruz and Fernando D. Ram\u00edrez-Figueroa. Intelligent Control Systems with LabVIEW. Springer-Verlag London, 1979."},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803887"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01157687"},{"key":"e_1_3_2_2_40_1","volume-title":"Neural Networks - A Systematic Introduction","author":"Rojas Raul","year":"1996","unstructured":"{Roj96} Raul Rojas . Neural Networks - A Systematic Introduction . Springer-Verlag , Berlin , New-York, 1996 . {Roj96} Raul Rojas. Neural Networks - A Systematic Introduction. Springer-Verlag, Berlin, New-York, 1996."},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146684"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165411"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122563"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1508284.1508258"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICECS.2012.6463557"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2013.2243177"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.391185"},{"key":"e_1_3_2_2_48_1","volume-title":"Boolean functions whose monotone complexity is of size n 2 \/ log n. 21:213\u2013224, 11","author":"Wegener Ingo","year":"1982","unstructured":"{Weg82} Ingo Wegener . Boolean functions whose monotone complexity is of size n 2 \/ log n. 21:213\u2013224, 11 1982 . {Weg82} Ingo Wegener. Boolean functions whose monotone complexity is of size n 2 \/ log n. 21:213\u2013224, 11 1982."},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73025"},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/321203.321214"},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675222"}],"event":{"name":"STOC '18: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Los Angeles CA USA","acronym":"STOC '18"},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188912","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188912","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:10Z","timestamp":1750212430000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188912"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":50,"alternative-id":["10.1145\/3188745.3188912","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188912","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}