{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:20:28Z","timestamp":1742617228537,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540620341"},{"type":"electronic","value":"9783540496311"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-62034-6_58","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T22:31:50Z","timestamp":1330295510000},"page":"298-309","source":"Crossref","is-referenced-by-count":0,"title":["Non-cancellative Boolean circuits: A generalization of monotone Boolean circuits"],"prefix":"10.1007","author":[{"given":"Rimli","family":"Sengupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H.","family":"Venkateswaran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579196","volume":"7","author":"N. Alon","year":"1987","unstructured":"N. Alon and R.B. Boppana, The monotone circuit complexity of Boolean functions, Combinatorica, 7 (1987), 1\u201322.","journal-title":"Combinatorica"},{"issue":"4","key":"26_CR2","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1145\/31846.31852","volume":"34","author":"M. Ajtai","year":"1987","unstructured":"M. Ajtai and Y. Gurevich, Monotone versus positive, J. Assoc. Comput. Mach., 34:4 (1987), 1004\u20131015.","journal-title":"J. Assoc. Comput. Mach."},{"key":"26_CR3","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1137\/0218038","volume":"18","author":"A. Borodin","year":"1989","unstructured":"A. Borodin, S. Cook, P. Dymond, W. Ruzzo, M. Tompa, Two applications of inductive counting for complementation problems, SLAM J. Comput., 18 (1989), 559\u2013578.","journal-title":"SLAM J. Comput."},{"key":"26_CR4","doi-asserted-by":"crossref","unstructured":"M. Grigni, Structure in monotone complexity, Ph.D. thesis, M.I.T., 1991.","DOI":"10.1017\/CBO9780511526633.006"},{"key":"26_CR5","doi-asserted-by":"crossref","unstructured":"M. Grigni and M. Sipser, Monotone separation of Logspace from NC1, Proc. 6th IEEE Structures (1991), 294\u2013298.","DOI":"10.1109\/SCT.1991.160272"},{"key":"26_CR6","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1 (1981), 169\u2013197.","journal-title":"Combinatorica"},{"key":"26_CR7","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"J.E. Hopcroft and R.M. Karp, A n 5\/2 algorithm for maximum matching in bipartite graphs, SIAM J. Comput. 2 (1973), 225\u2013231.","journal-title":"SIAM J. Comput."},{"key":"26_CR8","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N. Immerman, Nondeterministic space is closed under complement, SIAM J. Comput., 17 (1988), 935\u2013938.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"26_CR9","first-page":"694","volume":"4","author":"A. Markov","year":"1963","unstructured":"A. Markov, On the inversion complexity of systems of Boolean functions, Soviet Math. Doklady 4:3 (1963), 694\u2013696.","journal-title":"Soviet Math. Doklady"},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"N. Nisan, Lower bounds for non-commutative computation, Proc. 23nd annual ACM STOC (1991), 410\u2013418.","DOI":"10.1145\/103418.103462"},{"key":"26_CR11","first-page":"887","volume":"37","author":"A.A. Razborov","year":"1985","unstructured":"A.A. Razborov, A lower bound on the monotone network complexity of the logical permanent, Mathematischi Zametki 37 (1985), 887\u2013900.","journal-title":"Mathematischi Zametki"},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"R. Raz and A. Wigderson, Monotone circuits for matching require linear depth, Proc. 22nd annual ACM STOC (1990), 287\u2013292.","DOI":"10.1145\/100216.100253"},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"M. Santha and C. Wilson Polynomial size constant depth circuits with a limited number of negations, Proc. 8th STACS (1991), 228\u2013237.","DOI":"10.1007\/BFb0020801"},{"key":"26_CR14","volume-title":"The complexity of computing","author":"J. E. Savage","year":"1987","unstructured":"J. E. Savage, The complexity of computing, R. E. Kreiger Publishing Co., Malabar, Florida, 1987."},{"key":"26_CR15","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/BF02165411","volume":"13","author":"V. Strassen","year":"1969","unstructured":"V. Strassen, Gaussian elimination is not optimal, Numer. Math. 13 (1969) 354\u2013356.","journal-title":"Numer. Math."},{"key":"26_CR16","first-page":"141","volume":"7","author":"\u00e9. Tardos","year":"1987","unstructured":"\u00e9. Tardos, The gap between monotone and non-monotone circuit complexity is exponential, Combinatorica 7 (1987), 141\u2013142.","journal-title":"Combinatorica"},{"key":"26_CR17","doi-asserted-by":"crossref","unstructured":"K. Tanaka and T. Nishino, On the complexity of negation-limited Boolean networks, Proc. 26th ACM Symposium on Theory of Computing (1994), 38\u201347.","DOI":"10.1145\/195058.195099"},{"key":"26_CR18","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. Valiant","year":"1979","unstructured":"L. Valiant, The complexity of computing the permanent, Theoretical Computer Science 8 (1979), 189\u2013201.","journal-title":"Theoretical Computer Science"},{"key":"26_CR19","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0304-3975(80)90060-2","volume":"12","author":"L. Valiant","year":"1980","unstructured":"L. Valiant, Negation can be exponentially powerful, Theoretical Computer Science 12 (1980), 303\u2013314.","journal-title":"Theoretical Computer Science"},{"key":"26_CR20","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1137\/0221040","volume":"21","author":"H. Venkateswaran","year":"1992","unstructured":"H. Venkateswaran, Circuit definitions of nondeterministic complexity classes, SIAM J. Comput. 21 (1992) 655\u2013670.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-62034-6_58.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:27:29Z","timestamp":1742599649000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-62034-6_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540620341","9783540496311"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-62034-6_58","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}