{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:53:04Z","timestamp":1725663184335},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540100034"},{"type":"electronic","value":"9783540393467"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1980]]},"DOI":"10.1007\/3-540-10003-2_103","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:01:19Z","timestamp":1330189279000},"page":"621-631","source":"Crossref","is-referenced-by-count":3,"title":["On the size complexity of monotone formulas"],"prefix":"10.1007","author":[{"given":"Marc","family":"Snir","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,24]]},"reference":[{"key":"50_CR1","unstructured":"A.V. Aho, J.E. Hopcroft and J.D. Ullman. The design and analysis of computer algorithms. Addison-Wesley, 1974."},{"key":"50_CR2","doi-asserted-by":"crossref","unstructured":"A. Ehrenfeucht and P. Zeiger. Complexity measures for regular expressions. Proc. 6th ACM Symposium on Theory of Computing (1974) 75\u201379.","DOI":"10.1145\/800119.803886"},{"key":"50_CR3","unstructured":"M. Jerrum and M. Snir. Some exact complexity results for straight line computations over semirings. University of Edinburgh Technical Report CSR-58-80 (1980)."},{"key":"50_CR4","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1137\/0204009","volume":"4","author":"W. Miller","year":"1975","unstructured":"W. Miller. Computational complexity and numerical stability. SIAM J. Computing, 4 (1975) 97\u2013107.","journal-title":"SIAM J. Computing"},{"key":"50_CR5","doi-asserted-by":"crossref","unstructured":"H.J. Ryser. Combinatorial Mathematics. The Carus Mathematical Monographs 14, 1963.","DOI":"10.5948\/UPO9781614440147"},{"key":"50_CR6","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0304-3975(76)90083-9","volume":"2","author":"C. P. Schnorr","year":"1976","unstructured":"C.P. Schnorr. A lower bound on the number of additions in monotone computations. Theoretical Computer Science, 2 (1976) 305\u2013315.","journal-title":"Theoretical Computer Science"},{"key":"50_CR7","doi-asserted-by":"crossref","unstructured":"E. Shamir and M. Snir. On the depth complexity of formulas. Mathematical System Theory (to appear).","DOI":"10.1007\/BF01744302"},{"key":"50_CR8","doi-asserted-by":"crossref","unstructured":"L.G. Valiant. Negation can be exponentially powerfu. Proc. 11th ACM Symposium on Theory of Computing (1979) 189\u2013196.","DOI":"10.1145\/800135.804412"},{"key":"50_CR9","doi-asserted-by":"crossref","unstructured":"L.G. Valiant. The complexity of computing the permanent. Theoretical Computer Science (to appear).","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"50_CR10","doi-asserted-by":"crossref","unstructured":"L.G. Valiant. Completeness classes in algebra. Proc. 11th ACM Symposium on Theory of Computing (1979) 249\u2013261.","DOI":"10.1145\/800135.804419"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-10003-2_103.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T20:33:03Z","timestamp":1619555583000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10003-2_103"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1980]]},"ISBN":["9783540100034","9783540393467"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/3-540-10003-2_103","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1980]]}}}