{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:50:53Z","timestamp":1725558653084},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540202165"},{"type":"electronic","value":"9783540452089"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45208-9_4","type":"book-chapter","created":{"date-parts":[[2010,6,28]],"date-time":"2010-06-28T04:49:20Z","timestamp":1277700560000},"page":"23-36","source":"Crossref","is-referenced-by-count":19,"title":["On the Computational Complexity of Cut-Elimination in Linear Logic"],"prefix":"10.1007","author":[{"given":"Harry G.","family":"Mairson","sequence":"first","affiliation":[]},{"given":"Kazushige","family":"Terui","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Asperti, A.: Light affine logic. In: Proceedings of the Thirteenth Annual IEEE Symposium on Logic in Computer Science, pp. 300\u2013308 (1998)","DOI":"10.1109\/LICS.1998.705666"},{"issue":"1","key":"4_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/504077.504081","volume":"3","author":"A. Asperti","year":"2002","unstructured":"Asperti, A., Roversi, L.: Intuitionistic light affine logic (proof-nets, normalization complexity, expressive power, programming notation). ACM Transactions on Computational Logic\u00a03(1), 1\u201339 (2002)","journal-title":"ACM Transactions on Computational Logic"},{"issue":"1","key":"4_CR3","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S0168-0072(02)00042-8","volume":"120","author":"L. Tortora de Falco","year":"2003","unstructured":"Tortora de Falco, L.: The additive multiboxes. Annals of Pure and Applied Logic\u00a0120(1), 65\u2013102 (2003)","journal-title":"Annals of Pure and Applied Logic"},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(87)90045-4","volume":"50","author":"J.-Y. Girard","year":"1987","unstructured":"Girard, J.-Y.: Linear logic. Theoretical Computer Science\u00a050, 1\u2013102 (1987)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"4_CR5","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1006\/inco.1998.2700","volume":"14","author":"J.-Y. Girard","year":"1998","unstructured":"Girard, J.-Y.: Light linear logic. Information and Computation\u00a014(3), 175\u2013204 (1998)","journal-title":"Information and Computation"},{"key":"4_CR6","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. Garey","year":"1978","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco (1978)"},{"key":"4_CR7","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0304-3975(89)90100-X","volume":"64","author":"J.R. Hindley","year":"1989","unstructured":"Hindley, J.R.: BCK-combinators and linear \u03bb-terms have types. Theoretical Computer Science\u00a064, 97\u2013105 (1989)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"4_CR8","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E.: The circuit value problem is logspace complete for P. SIGACT News\u00a07(1), 18\u201320 (1975)","journal-title":"SIGACT News"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"Lafont, Y.: Soft linear logic and polynomial time. Theoretical Computer Science (to appear)","DOI":"10.1016\/j.tcs.2003.10.018"},{"key":"4_CR10","series-title":"London Mathematical Society Lecture Notes Series","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1017\/CBO9780511629150.006","volume-title":"Advances in Linear Logic","author":"P.D. Lincoln","year":"1995","unstructured":"Lincoln, P.D.: Deciding provability of linear logic formulas. In: Advances in Linear Logic. London Mathematical Society Lecture Notes Series, vol.\u00a0222, pp. 109\u2013122. Cambridge University Press, Cambridge (1995)"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Mairson, H.G., Rival, X.: Proofnets and context semantics for the additives. Computer Science Logic (CSL), 151\u2013166 (2002)","DOI":"10.1007\/3-540-45793-3_11"},{"key":"4_CR12","unstructured":"Mairson, H.G.: Linear lambda calculus and polynomial time. Journal of Functional Programming (to appear)"},{"key":"4_CR13","unstructured":"Neergaard, P.M., Mairson, H.G.: LAL is square: representation and expressiveness in light affine logic. Presented at the Fourth International Workshop on Implicit Computational Complexity (2002)"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"Schubert, A.: The Complexity of \u03b2-Reduction in Low Orders. Typed Lambda Calculi and Applications (TLCA), 400\u2013414 (2001)","DOI":"10.1007\/3-540-45413-6_31"},{"key":"4_CR15","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0304-3975(79)90007-0","volume":"9","author":"R. Statman","year":"1979","unstructured":"Statman, R.: The typed \u03bb-calculus is not elementary recursive. Theoretical Computer Science\u00a09, 73\u201381 (1979)","journal-title":"Theoretical Computer Science"},{"key":"4_CR16","unstructured":"Terui, K.: Light affine lambda calculus and polytime strong normalization. In: Proceedings of the sixteenth annual IEEE symposium on Logic in Computer Science, pp. 209\u2013220 (2001), The full version is available at \n \n http:\/\/research.nii.ac.jp\/~terui"}],"container-title":["Lecture Notes in Computer Science","Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45208-9_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T04:03:40Z","timestamp":1552622620000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45208-9_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540202165","9783540452089"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45208-9_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}