{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T16:18:24Z","timestamp":1774369104495,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":6,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540206958","type":"print"},{"value":"9783540245872","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-24587-2_13","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T08:59:19Z","timestamp":1280393959000},"page":"108-116","source":"Crossref","is-referenced-by-count":8,"title":["Limiting Negations in Bounded-Depth Circuits: An Extension of Markov\u2019s Theorem"],"prefix":"10.1007","author":[{"given":"Shao Chin","family":"Sung","sequence":"first","affiliation":[]},{"given":"Keisuke","family":"Tanaka","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"13_CR1","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":"13_CR2","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)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"13_CR3","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. Journal of the ACM\u00a05(4), 331\u2013334 (1958)","journal-title":"Journal of the ACM"},{"key":"13_CR4","series-title":"Lecture Notes in Computer Science","first-page":"71","volume-title":"Automata Theory and Formal Languages","author":"M.J. Fischer","year":"1974","unstructured":"Fischer, M.J.: The complexity of negation-limited networks \u2013 a brief survey. In: Brakhage, H. (ed.) GI-Fachtagung 1975. LNCS, vol.\u00a033, pp. 71\u201382. Springer, Heidelberg (1974), Revised 1977 and 1996"},{"issue":"2","key":"13_CR5","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 Journal on Computing\u00a022(2), 294\u2013302 (1993)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"13_CR6","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 gate. Information Processing Letters\u00a082(3), 155\u2013157 (2002)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24587-2_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,17]],"date-time":"2019-03-17T16:27:49Z","timestamp":1552840069000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24587-2_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540206958","9783540245872"],"references-count":6,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24587-2_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003]]}}}