{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:02:01Z","timestamp":1725562921790},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642151545"},{"type":"electronic","value":"9783642151552"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15155-2_37","type":"book-chapter","created":{"date-parts":[[2010,8,13]],"date-time":"2010-08-13T16:17:45Z","timestamp":1281716265000},"page":"417-428","source":"Crossref","is-referenced-by-count":1,"title":["Limiting Negations in Bounded Treewidth and Upward Planar Circuits"],"prefix":"10.1007","author":[{"given":"Jing","family":"He","sequence":"first","affiliation":[]},{"given":"Hongyu","family":"Liang","sequence":"additional","affiliation":[]},{"given":"Jayalal M. N.","family":"Sarma","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"37_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)log log n negation gates. SIAM Journal of Computing\u00a035(1), 201\u2013216 (2005)","journal-title":"SIAM Journal of Computing"},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"Barrington, D.A.M., Lu, C.-J., Miltersen, P.B., Skyum, S.: On Monotone Planar Circuits. In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity (CCC), pp. 24\u201331 (1999)","DOI":"10.1109\/CCC.1999.766259"},{"issue":"2-3","key":"37_CR3","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0304-3975(87)90068-5","volume":"53","author":"M. Beynon","year":"1987","unstructured":"Beynon, M., Buckle, J.: On the planar monotone computation of boolean functions. Theor. Comput. Sci.\u00a053(2-3), 267\u2013279 (1987)","journal-title":"Theor. Comput. Sci."},{"key":"37_CR4","series-title":"Lecture Notes in Computer Science","first-page":"71","volume-title":"The complexity of negation-limited networks (a brief survey)","author":"M. Fischer","year":"1974","unstructured":"Fischer, M.: The complexity of negation-limited networks (a brief survey). LNCS, vol.\u00a033, pp. 71\u201382. Springer, Heidelberg (1974)"},{"key":"37_CR5","doi-asserted-by":"crossref","unstructured":"Jansen, M., Sarma, M.N., Jayalal: Balancing Bounded Treewidth Circuits. In: Proeedings of CSR 2010 (to appear 2010)","DOI":"10.1007\/978-3-642-13182-0_21"},{"key":"37_CR6","doi-asserted-by":"crossref","unstructured":"Karchmer, M., Wigderson, A.: Monotone circuits for connectivity require super-logarithmic depth. In: Proc. of STOC 1988, pp. 539\u2013550 (1988)","DOI":"10.1145\/62212.62265"},{"issue":"3","key":"37_CR7","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/s00037-009-0265-5","volume":"18","author":"N. Limaye","year":"2009","unstructured":"Limaye, N., Mahajan, M., Sarma, M.N.J.: Upper bounds for monotone planar circuit value and variants. Computational Complexity\u00a018(3), 377\u2013412 (2009)","journal-title":"Computational Complexity"},{"issue":"4","key":"37_CR8","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"},{"issue":"3","key":"37_CR9","doi-asserted-by":"publisher","first-page":"963","DOI":"10.1137\/050644756","volume":"38","author":"I.L. Markov","year":"2008","unstructured":"Markov, I.L., Shi, Y.: Simulating quantum computation by contracting tensor networks. SIAM J. Comput.\u00a038(3), 963\u2013981 (2008)","journal-title":"SIAM J. Comput."},{"key":"37_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/BFb0024011","volume-title":"STACS 1985","author":"W.F. McColl","year":"1984","unstructured":"McColl, W.F.: On the planar monotone computation of threshold functions. In: Mehlhorn, K. (ed.) STACS 1985. LNCS, vol.\u00a0182, pp. 219\u2013230. Springer, Heidelberg (1984)"},{"key":"37_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1007\/978-3-642-02927-1_58","volume-title":"ICALP 2009","author":"H. Morizumi","year":"2009","unstructured":"Morizumi, H.: Limiting negations in formulas. In: Albers, S., et al. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 701\u2013712. Springer, Heidelberg (2009)"},{"key":"37_CR12","doi-asserted-by":"crossref","unstructured":"Raz, R., Wigderson, A.: Monotone circuits for matching require linear depth. In: STOC 1990: Proceedings of the twenty-second annual ACM symposium on Theory of computing, pp. 287\u2013292 (1990)","DOI":"10.1145\/100216.100253"},{"key":"37_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":"2","key":"37_CR14","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1137\/0222022","volume":"22","author":"M. Santha","year":"1993","unstructured":"Santha, M., Wilson, C.: Limiting negations in constant depth circuits. SIAM J. Comput.\u00a022(2), 294\u2013302 (1993)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"37_CR15","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0022-0000(84)90033-3","volume":"29","author":"J.E. Savage","year":"1984","unstructured":"Savage, J.E.: The performance of multilective vlsi algorithms. Journal of Computer and System Science\u00a029(2), 243\u2013273 (1984)","journal-title":"Journal of Computer and System Science"},{"key":"37_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-540-24587-2_13","volume-title":"Algorithms and Computation","author":"S.C. Sung","year":"2003","unstructured":"Sung, S.C., Tanaka, K.: Limiting negations in bounded-depth circuits: An extension of markovs theorem. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol.\u00a02906, pp. 108\u2013116. Springer, Heidelberg (2003)"},{"key":"37_CR17","first-page":"393","volume":"7","author":"E. Tardos","year":"1987","unstructured":"Tardos, E.: The Gap Between Monotone and Non-monotone Circuit Complexity is Exponential. Combinatorica\u00a07, 393\u2013394 (1987)","journal-title":"Combinatorica"},{"issue":"3","key":"37_CR18","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0196-6774(84)90016-6","volume":"5","author":"L.G. Valiant","year":"1984","unstructured":"Valiant, L.G.: Short monotone formulae for the majority function. J. Algorithms\u00a05(3), 363\u2013366 (1984)","journal-title":"J. Algorithms"},{"key":"37_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity: A Uniform Approach","author":"H. Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach. Springer, New York (1999)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15155-2_37.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T22:01:42Z","timestamp":1606168902000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15155-2_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642151545","9783642151552"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15155-2_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}