{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:36:17Z","timestamp":1725474977400},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540496946"},{"type":"electronic","value":"9783540496960"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11940128_24","type":"book-chapter","created":{"date-parts":[[2006,11,29]],"date-time":"2006-11-29T05:57:35Z","timestamp":1164779855000},"page":"223-232","source":"Crossref","is-referenced-by-count":2,"title":["Negation-Limited Complexity of Parity and Inverters"],"prefix":"10.1007","author":[{"given":"Kazuo","family":"Iwama","sequence":"first","affiliation":[]},{"given":"Hiroki","family":"Morizumi","sequence":"additional","affiliation":[]},{"given":"Jun","family":"Tarui","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"24_CR1","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1137\/S0097539701396959","volume":"35","author":"K. Amano","year":"2005","unstructured":"Amano, K., Maruoka, A.: A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1\/6)loglogn Negation Gates. SIAM J. Comput.\u00a035(1), 201\u2013216 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"24_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(02)00215-9","volume":"126","author":"K. Amano","year":"2003","unstructured":"Amano, K., Maruoka, A., Tarui, J.: On the Negation-Limited Circuit Complexity of Merging. Discrete Applied Mathematics\u00a0126(1), 3\u20138 (2003)","journal-title":"Discrete Applied Mathematics"},{"issue":"5","key":"24_CR3","doi-asserted-by":"publisher","first-page":"1334","DOI":"10.1137\/S0097539794275136","volume":"27","author":"R. Beals","year":"1998","unstructured":"Beals, R., Nishino, T., Tanaka, K.: On the Complexity of Negation-Limited Boolean Networks. SIAM J. Comput.\u00a027(5), 1334\u20131347 (1998)","journal-title":"SIAM J. Comput."},{"key":"24_CR4","doi-asserted-by":"crossref","unstructured":"Boppana, R., Sipser, M.: The Complexity of Finite Functions. In: Leeuwen, J.v. (ed.) Handbook of Theoretical Computer Science, vol. A: Algorithms and Complexity, pp. 757\u2013804. Elsevier\/MIT Press (1990)","DOI":"10.1016\/B978-0-444-88071-0.50019-9"},{"key":"24_CR5","unstructured":"Fischer, M.: Lectures on Network Complexity, Technical Report 1104, CS Department, Yale University 1974, (revised, 1996), http:\/\/cs-www.cs.yale.edu\/homes\/fischer"},{"key":"24_CR6","doi-asserted-by":"crossref","unstructured":"Harnik, D., Raz, R.: Higher Lower Bounds on Monotone Size. In: Proc.\u00a0of 32nd STOC, pp. 378\u2013387 (2000)","DOI":"10.1145\/335305.335349"},{"key":"24_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/3-540-45687-2_29","volume-title":"Mathematical Foundations of Computer Science 2002","author":"K. Iwama","year":"2002","unstructured":"Iwama, K., Morizumi, H.: An Explicit Lower Bound of 5n\u2009\u2212\u2009o(n) for Boolean Circuits. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 353\u2013364. Springer, Heidelberg (2002)"},{"key":"24_CR8","unstructured":"Long, D.: The Monotone Circuit Complexity of Threshold Functions, Unpublished manuscript, University of Oxford (1986)"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"Lachish, O., Raz, R.: Explicit Lower Bound of 4.5n\u2009\u2212\u2009o(n) for Boolean Circuits. In: Proc.\u00a0of 33rd STOC, pp. 399\u2013408 (2001)","DOI":"10.1145\/380752.380832"},{"issue":"4","key":"24_CR10","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1145\/320941.320945","volume":"5","author":"A.A. Markov","year":"1958","unstructured":"Markov, A.A.: On the Inversion Complexity of a System of Functions. J. ACM\u00a05(4), 331\u2013334 (1958)","journal-title":"J. ACM"},{"key":"24_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/11809678_13","volume-title":"Computing and Combinatorics","author":"T. Sato","year":"2006","unstructured":"Sato, T., Amano, K., Maruoka, A.: On the Negation-Limited Circuit Complexity of Sorting and Inverting k-tonic Sequences. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol.\u00a04112, pp. 104\u2013115. Springer, Heidelberg (2006)"},{"key":"24_CR12","unstructured":"Sung, S.: On Negation-Limited Circuit Complexity, Ph.D. thesis, Japan Advanced Institute of Science and Technology (1998)"},{"key":"24_CR13","unstructured":"Sung, S., Tanaka, K.: Lower Bounds on Negation-Limited Inverters. In: Proc. of 2nd DMTCS: Discrete Mathematics and Theoretical Computer Science Conference, pp. 360\u2013368 (1999)"},{"issue":"5","key":"24_CR14","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0020-0190(96)00115-9","volume":"59","author":"K. Tanaka","year":"1996","unstructured":"Tanaka, K., Nishino, T., Beals, R.: Negation-Limited Circuit Complexity of Symmetric Functions. Inf. Process. Lett.\u00a059(5), 273\u2013279 (1996)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11940128_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:49:48Z","timestamp":1619509788000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11940128_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540496946","9783540496960"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/11940128_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}