{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:34:05Z","timestamp":1725514445173},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540725039"},{"type":"electronic","value":"9783540725046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72504-6_55","type":"book-chapter","created":{"date-parts":[[2007,7,22]],"date-time":"2007-07-22T11:36:39Z","timestamp":1185104199000},"page":"605-615","source":"Crossref","is-referenced-by-count":2,"title":["Linear-Size Log-Depth Negation-Limited Inverter for k-Tonic Binary Sequences"],"prefix":"10.1007","author":[{"given":"Hiroki","family":"Morizumi","sequence":"first","affiliation":[]},{"given":"Jun","family":"Tarui","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"55_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: An O(nlogn) Sorting Network. In: Proceedings of STOC83: the 15th Annual ACM Symposium on Theory of Computing, pp. 1\u20139 (1983)","DOI":"10.1145\/800061.808726"},{"issue":"1","key":"55_CR2","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 Journal on Computing\u00a035(1), 201\u2013216 (2005)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"55_CR3","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":"55_CR4","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 Journal on Computing\u00a027(5), 1334\u20131347 (1998), a preliminary version appears in: Proceedings of STOC95: the 27th Annual ACM Symposium on Theory of Computing, pp. 585\u2013595 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"55_CR5","first-page":"757","volume-title":"Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity","author":"R. Boppana","year":"1990","unstructured":"Boppana, R., Sipser, M.: The Complexity of Finite Functions. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, pp. 757\u2013804. Elsevier, Amsterdam (1990)"},{"key":"55_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/3-540-07407-4_9","volume-title":"Automata Theory and Formal Languages","author":"M. Fischer","year":"1975","unstructured":"Fischer, M.: The Complexity of Negation-Limited Networks - A Brief Survey. In: Brakhage, H. (ed.) GI-Fachtagung 1975. LNCS, vol.\u00a033, pp. 71\u201382. Springer, Heidelberg (1975)"},{"key":"55_CR7","unstructured":"Fischer, M.: Lectures on Network Complexity. Technical Report 1104, CS Department, Yale University (available on the web) (1974, revised 1996)"},{"key":"55_CR8","doi-asserted-by":"crossref","unstructured":"Harnik, D., Raz, R.: Higher Lower Bounds on Monotone Size. In: Proceedings of STOC00: the 32nd Annual ACM Symposium on Theory of Computing, pp. 378\u2013387 (2000)","DOI":"10.1145\/335305.335349"},{"key":"55_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/11940128_24","volume-title":"Stabilization, Safety, and Security of Distributed Systems","author":"K. Iwama","year":"2006","unstructured":"Iwama, K., Morizumi, H., Tarui, J.: Negation-Limited Complexity of Parity and Inverters. In: Datta, A.K., Gradinariu, M. (eds.) SSS 2006. LNCS, vol.\u00a04280, pp. 223\u2013232. Springer, Heidelberg (2006)"},{"key":"55_CR10","volume-title":"The Art of Computer Programming vol.\u00a03: Sorting and Searching","author":"D. Knuth","year":"1998","unstructured":"Knuth, D.: The Art of Computer Programming vol.\u00a03: Sorting and Searching, 2nd edn. Addison-Wesley, Reading (1998)","edition":"2"},{"issue":"4","key":"55_CR11","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1145\/320941.320945","volume":"5","author":"A. Markov","year":"1958","unstructured":"Markov, A.: On the Inversion Complexity of a System of Functions. Journal of the ACM\u00a05(4), 331\u2013334 (1958)","journal-title":"Journal of the ACM"},{"issue":"4","key":"55_CR12","first-page":"354","volume":"281","author":"A. Razborov","year":"1985","unstructured":"Razborov, A.: Lower Bounds on the Monotone Complexity of Some Boolean Functions (in Russian). Dokl. Akad. Nauk SSSR\u00a0281(4), 354\u2013357 (1985), English translation in: Soviet Math. Dokl. 31, 354\u2013357 (1985)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"55_CR13","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)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72504-6_55.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T09:38:26Z","timestamp":1619516306000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72504-6_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540725039","9783540725046"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72504-6_55","relation":{},"subject":[]}}