{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:31:39Z","timestamp":1725543099881},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540369257"},{"type":"electronic","value":"9783540369264"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11809678_13","type":"book-chapter","created":{"date-parts":[[2006,8,15]],"date-time":"2006-08-15T13:41:33Z","timestamp":1155649293000},"page":"104-115","source":"Crossref","is-referenced-by-count":5,"title":["On the Negation-Limited Circuit Complexity of Sorting and Inverting k-tonic Sequences"],"prefix":"10.1007","author":[{"given":"Takayuki","family":"Sato","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuyuki","family":"Amano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Akira","family":"Maruoka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Kom\u00f3s, J., Szemer\u00e9di, E.: An O(n logn) Sorting Network. In: Proc. 15th STOC, pp. 1\u20139 (1983)","DOI":"10.1145\/800061.808726"},{"issue":"1","key":"13_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579196","volume":"7","author":"N. Alon","year":"1987","unstructured":"Alon, N., Boppana, R.B.: The Monotone Circuit Complexity of Boolean Functions. Combinatorica\u00a07(1), 1\u201322 (1987)","journal-title":"Combinatorica"},{"issue":"1","key":"13_CR3","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) \\log\\ \\log n$ Negation Gates. SIAM J. Comput.\u00a035(1), 201\u2013216 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"13_CR4","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":"3","key":"13_CR5","first-page":"530","volume":"31","author":"A.E. Andreev","year":"1985","unstructured":"Andreev, A.E.: On a Method for Obtaining Lower Bounds for the Complexity of Individual Monotone Functions. Sov. Math. Dokl.\u00a031(3), 530\u2013534 (1985)","journal-title":"Sov. Math. Dokl."},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"Beals, R., Nishino, T., Tanaka, K.: More on the Complexity of Negation-Limited Circuits. In: Proc. 27th STOC, pp. 585\u2013595 (1995)","DOI":"10.1145\/225058.225276"},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","first-page":"71","volume-title":"The Complexity of Negation-Limited Network\u2013A Brief Survey","author":"M.J. Fischer","year":"1974","unstructured":"Fischer, M.J.: The Complexity of Negation-Limited Network\u2013A Brief Survey, LNCS, vol.\u00a033, pp. 71\u201382. Springer, Heidelberg (1974)"},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Harnik, D., Raz, R.: Higher Lower Bounds on Monotone Size. In: Proc. 32nd STOC, pp. 378\u2013387 (2000)","DOI":"10.1145\/335305.335349"},{"issue":"2","key":"13_CR9","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.ipl.2003.10.003","volume":"89","author":"S. Jukna","year":"2004","unstructured":"Jukna, S.: On the Minimum Number of Negations Leading to Super-Polynomial Savings. Inf. Process. Lett.\u00a089(2), 71\u201374 (2004)","journal-title":"Inf. Process. Lett."},{"issue":"10","key":"13_CR10","doi-asserted-by":"publisher","first-page":"773","DOI":"10.1109\/TC.1979.1675245","volume":"28","author":"E.A. Lamagna","year":"1979","unstructured":"Lamagna, E.A.: The Complexity of Monotone Networks for Certain Bilinear Forms, Routing Problems, Sorting and Merging. IEEE Trans. of Comput.\u00a028(10), 773\u2013782 (1979)","journal-title":"IEEE Trans. of Comput."},{"key":"13_CR11","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, 331\u2013334 (1958)","journal-title":"J. ACM"},{"key":"13_CR12","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1145\/321879.321882","volume":"22","author":"D.E. Muller","year":"1975","unstructured":"Muller, D.E., Preparata, F.P.: Bounds to Complexities of Networks for Sorting and Switching. J. ACM\u00a022, 195\u2013201 (1975)","journal-title":"J. ACM"},{"key":"13_CR13","first-page":"798","volume":"281","author":"A.A. Razborov","year":"1985","unstructured":"Razborov, A.A.: Lower Bounds on the Monotone Complexity of Some Boolean Functions. Soviet Math. Dokl.\u00a0281, 798\u2013801 (1985)","journal-title":"Soviet Math. Dokl."},{"issue":"3","key":"13_CR14","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0020-0190(01)00264-2","volume":"82","author":"S.C. Sung","year":"2002","unstructured":"Sung, S.C., Tanaka, K.: An Exponential Gap with the Removal of One Negation Gates. Inf. Process. Let.\u00a082(3), 155\u2013157 (2002)","journal-title":"Inf. Process. Let."},{"issue":"5","key":"13_CR15","doi-asserted-by":"publisher","first-page":"1334","DOI":"10.1137\/S0097539794275136","volume":"27","author":"K. Tanaka","year":"1998","unstructured":"Tanaka, K., Nishino, T.: On the Complexity of Negation-Limited Boolean Networks. SIAM J. Comput.\u00a027(5), 1334\u20131347 (1998)","journal-title":"SIAM J. Comput."},{"key":"13_CR16","volume-title":"The Complexity of Boolean Functions","author":"I. Wegener","year":"1987","unstructured":"Wegener, I.: The Complexity of Boolean Functions. Wiley-Teubner, Chichester (1987)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11809678_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,8]],"date-time":"2023-05-08T14:38:27Z","timestamp":1683556707000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11809678_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540369257","9783540369264"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/11809678_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}