{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:03:24Z","timestamp":1725487404241},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540662006"},{"type":"electronic","value":"9783540486862"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48686-0_20","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T11:54:12Z","timestamp":1184586852000},"page":"204-209","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Negation-Limited Circuit Complexity of Merging"],"prefix":"10.1007","author":[{"given":"Kazuyuki","family":"Amano","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Akira","family":"Maruoka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Tarui","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1999,6,25]]},"reference":[{"issue":"3","key":"20_CR1","first-page":"530","volume":"31","author":"A.E. Andreev","year":"1985","unstructured":"A.E. Andreev, \u201cOn a Method for Obtaining Lower Bounds for the Complexity of Individual Monotone Functions\u201c, Soviet Math. Dokl., Vol. 31,No. 3, pp. 530\u2013534, 1985.","journal-title":"Soviet Math. Dokl."},{"issue":"1","key":"20_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579338","volume":"3","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai, J. Koml\u00f3s and E. Szmer\u00e9di, \u201cAn O(n log n) Sorting Network\u201d, Combinatorica, Vol. 3,No. 1, pp. 1\u201319, 1983.","journal-title":"Combinatorica"},{"issue":"1","key":"20_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579196","volume":"7","author":"N. Alon","year":"1987","unstructured":"N. Alon and R.B. Boppana, \u201cThe Monotone Circuit Complexity of Boolean Functions\u201d, Combinatorica, Vol. 7,No. 1, pp. 1\u201322, 1987.","journal-title":"Combinatorica"},{"key":"20_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/BFb0055789","volume-title":"Proc. 23rd MFCS","author":"K. Amano","year":"1998","unstructured":"K. Amano and A. Maruoka, \u201cA Superpolynomial Lower Bound for a Circuit Computing the Clique Function with (1\/6) log log n Negation Gates\u201d, Proc. 23rd MFCS, LNCS, No. 1450, pp. 399\u2013408, 1998."},{"key":"20_CR5","unstructured":"S.J. Berkowitz, \u201cOn Some Relationships between Monotone and Non-monotone Circuit Complexity\u201d, Tech. Rep. Univ. of Tronto, 1982."},{"key":"20_CR6","doi-asserted-by":"crossref","unstructured":"R. Beals, T. Nishino and K. Tanaka, \u201cMore on the Complexity of Negation-Limited Circuits\u201d, Proc. 27th STOC, pp. 585\u2013595, 1995.","DOI":"10.1145\/225058.225276"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"R.B. Boppana and M. Sipser, \u201cThe Complexity of Finite Functions\u201d, Handbook of Theoretical Computer Science, pp. 757\u2013804, Elsevier Science, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50019-9"},{"key":"20_CR8","series-title":"Lect Notes Comput Sci","first-page":"71","volume-title":"The Complexity of Negation-Limited Networks\u2014A Brief Survey","author":"M.J. Fischer","year":"1974","unstructured":"M.J. Fischer, \u201cThe Complexity of Negation-Limited Networks\u2014A Brief Survey\u201d, LNCS, No. 33, pp. 71\u201382, 1974."},{"key":"20_CR9","unstructured":"D.E. Knuth, \u201cThe Art of Computer Programming Vol. 3: Sorting and Searching (Second Edition)\u201d, Addison Wesley, 1998."},{"key":"20_CR10","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1145\/320941.320945","volume":"5","author":"A.A. Markov","year":"1958","unstructured":"A.A. Markov, \u201cOn the Inversion Complexity of a System of Functions\u201d, J. ACM, Vol. 5, pp. 331\u2013334, 1958.","journal-title":"J. ACM"},{"issue":"4","key":"20_CR11","first-page":"141","volume":"7","author":"Tardos","year":"1987","unstructured":"\u00c9. Tardos, \u201cThe Gap Between Monotone and Non-Monotone Circuit Complexity is Exponential\u201d, Combinatorica, Vol. 7,No. 4, pp. 141\u2013142, 1987.","journal-title":"Combinatorica"},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"K. Tanaka and T. Nishino, \u201cOn the Complexity of Negation-Limited Boolean Networks\u201d, Proc. 26th STOC, pp. 38\u201347, 1994.","DOI":"10.1145\/195058.195099"},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"A.A. Razborov, \u201cOn the Method of Approximations\u201d, Proc. 21st STOC, pp. 167\u2013176, 1989.","DOI":"10.1145\/73007.73023"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48686-0_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T19:46:40Z","timestamp":1558468000000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48686-0_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662006","9783540486862"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-48686-0_20","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"25 June 1999","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}