{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:40:22Z","timestamp":1787388022391,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540074076","type":"print"},{"value":"9783540379232","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1975]]},"DOI":"10.1007\/3-540-07407-4_9","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T15:58:24Z","timestamp":1330185504000},"page":"71-82","source":"Crossref","is-referenced-by-count":24,"title":["The complexity of negation-limited networks \u2014 A brief survey"],"prefix":"10.1007","author":[{"given":"Michael J.","family":"Fischer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,5,25]]},"reference":[{"key":"9_CR1","first-page":"296","volume-title":"Sorting networks and their applications, Proc. AFIPS Spring Joint Computer Conference, Vol. 32","author":"K. E. Batcher","year":"1968","unstructured":"Batcher, K.E., Sorting networks and their applications, Proc. AFIPS Spring Joint Computer Conference, Vol. 32, AFIPS Press, Montvale, N.J., (1968), 296\u2013291."},{"key":"9_CR2","volume-title":"Practical decidability, Report CU-CS-008-72","author":"A. Ehrenfeucht","year":"1972","unstructured":"Ehrenfeucht, A., Practical decidability, Report CU-CS-008-72, Dept. of Computer Science, Univ. of Colorado, Boulder, Colo., (1972), 14 pp."},{"key":"9_CR3","volume-title":"Lectures on network complexity","author":"M. J. Fischer","year":"1974","unstructured":"Fischer, M.J., Lectures on network complexity, University of Frankfurt, Germany, June 1974, 25 pp."},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Fischer M.J., and A.R. Meyer, Boolean matrix multiplication and transitive closure, Proc. 12th IEEE Symp. on Switching and Automata Theory (1971), 129\u2013131.","DOI":"10.1109\/SWAT.1971.4"},{"key":"9_CR5","first-page":"27","volume":"7","author":"M. J. Fischer","year":"1974","unstructured":"Fischer, M.J. and M.O. Rabin, Super-exponential complexity of Presburger arithmetic. In Complexity of Computation, SIAM-AMS Proceedings, Vol. 7 (1974), 27\u201341.","journal-title":"Complexity of Computation"},{"key":"9_CR6","series-title":"MAC Technical Memorandum","volume-title":"A class of Boolean functions with linear combinational complexity","author":"W. N. Hsieh","year":"1974","unstructured":"Hsieh, W.N., L.H. Harper and J.E. Savage, A class of Boolean functions with linear combinational complexity, MAC Technical Memorandum 55, M.I.T. Project MAC, Cambridge, Mass. (1974), 38 pp."},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"Lamagna, E.A. and J.E. Savage, Combinational complexity of some monotone functions, Proc. 15th IEEE Symp. on Switching and Automata Theory (1974), 140\u2013144.","DOI":"10.1109\/SWAT.1974.9"},{"key":"9_CR8","unstructured":"Lupanov, O.B., A method of circuit synthesis, Izvestia v.u.z. Radiafizike, No. 1 (1958), 120\u2013140."},{"issue":"4","key":"9_CR9","doi-asserted-by":"crossref","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 5, 4 (1958), 331\u2013334.","journal-title":"J. ACM"},{"key":"9_CR10","series-title":"Technical report","volume-title":"On the complexity of monotone realizations of matrix multiplication","author":"K. Mehlhorn","year":"1974","unstructured":"Mehlhorn, K., On the complexity of monotone realizations of matrix multiplication, Technical report A74-11, Fachbereich Angewandte Mathematik und Informatik, Universit\u00e4t des Saarlandes, Saarbrucken, Germany (1974), 17 pp."},{"key":"9_CR11","unstructured":"Meyer, A.R., Private communication."},{"issue":"2","key":"9_CR12","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1145\/321879.321882","volume":"22","author":"D. E. Muller","year":"1975","unstructured":"Muller, D.E. and F.P. Preparata, Bounds to complexities of networks for sorting and for switching, J. ACM 22 2 (1975), 195\u2013201.","journal-title":"J. ACM"},{"issue":"1","key":"9_CR13","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1109\/T-C.1972.223425","volume":"C-21","author":"K. Nakamura","year":"1972","unstructured":"Nakamura, K., N. Tokura, and T. Kasami, Minimal negative gate networks, IEEE Trans. Comp., Vol. C-21, No. 1 (1972), 5\u201311.","journal-title":"IEEE Trans. Comp."},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Paterson, M.S., Complexity of monotone networks for Boolean matrix product, Theoretical Computer Science 1, 1 (1975), to appear.","DOI":"10.1016\/0304-3975(75)90009-2"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Paul, W.J., A 2.5 N-lower bound on the combinational complexity of Boolean functions, Proc. 7th ACM Symp. on Theory of Computing (1975), 27\u201336.","DOI":"10.1145\/800116.803750"},{"key":"9_CR16","unstructured":"Pippenger, N., Private communication."},{"key":"9_CR17","unstructured":"Pippenger, N., and M.J. Fischer, Relationships among complexity measures, in preparation."},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"Pratt, V.R., The power of negative thinking in multiplying Boolean matrices, Proc. 6th ACM Symp. on Theory of Computing (1974), 80\u201383.","DOI":"10.1145\/800119.803887"},{"key":"9_CR19","unstructured":"Presburger, M., \u00dcber die Vollst\u00e4ndigkeit eines gewissen Systems der Arithmetic ganzer Zahlen in welchem die Addition als einzige Operation hervortritt. Comptes-rendus du I Congr\u00e8s des Math\u00e9maticiens des Pays Slaves, Warsaw (1930), 92\u2013101, 395."},{"issue":"4","key":"9_CR20","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1145\/321724.321731","volume":"19","author":"J. E. Savage","year":"1972","unstructured":"Savage, J.E., Computational work and time on finite machines, J. ACM 19, 4 (1972), 660\u2013674.","journal-title":"J. ACM"},{"key":"9_CR21","unstructured":"Savage, J.E., The Complexity of Computing, manuscript, 1974."},{"key":"9_CR22","volume-title":"The network complexity and the Turing machine complexity of finite functions","author":"C. P. Schnorr","year":"1975","unstructured":"Schnorr, C.P., The network complexity and the Turing machine complexity of finite functions, manuscript, University of Frankfurt, Germany (1975), 18 pp."},{"key":"9_CR23","doi-asserted-by":"crossref","unstructured":"Schnorr, C.P., The combinational complexity of equivalence, Theoretical Computer Science, to appear.","DOI":"10.1016\/0304-3975(76)90073-6"},{"key":"9_CR24","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF02246615","volume":"13","author":"C. P. Schnorr","year":"1974","unstructured":"Schnorr, C.P., Zwei lineare untere Schranken fur die Komplexit\u00e4t Boolescher Funktionen, Computing 13 (1974), 155\u2013171.","journal-title":"Computing"},{"key":"9_CR25","series-title":"Project MAC Technical Report","volume-title":"The complexity of decision problems in automata theory and logic","author":"L. J. Stockmeyer","year":"1974","unstructured":"Stockmeyer, L.J., The complexity of decision problems in automata theory and logic, Project MAC Technical Report 133, M.I.T., Cambridge, Mass. (1974), 224 pp."},{"key":"9_CR26","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF02252909","volume":"11","author":"V. Strassen","year":"1973","unstructured":"Strassen, V., Berechnungen in partiellen Algebren endlichen Typs, Computing 11 (1973), 181\u2013196.","journal-title":"Computing"},{"key":"9_CR27","doi-asserted-by":"crossref","unstructured":"Valiant, L.G., On non-linear lower bounds in computational complexity, Proc. 7th ACM Symposium on Theory of Computing (1975), 45\u201352.","DOI":"10.1145\/800116.803752"}],"container-title":["Lecture Notes in Computer Science","Automata Theory and Formal Languages 2nd GI Conference Kaiserslautern, May 20\u201323, 1975"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-07407-4_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T20:46:28Z","timestamp":1619556388000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-07407-4_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1975]]},"ISBN":["9783540074076","9783540379232"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-07407-4_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1975]]}}}