{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:32Z","timestamp":1742617172850,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":50,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540581406"},{"type":"electronic","value":"9783540484424"}],"license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58140-5_19","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:18:33Z","timestamp":1330269513000},"page":"184-190","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Computational and concurrency models of linear logic"],"prefix":"10.1007","author":[{"given":"Max I.","family":"Kanovich","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"19_CR1","unstructured":"S.Abramsky. Computational interpretation of linear logic. Imperial College Research Report DOC 90\/20, 1990."},{"key":"19_CR2","unstructured":"S.Abramsky, Computational Interpretations of Linear Logic, Theoretical Computer Science, 1992, Special Issue on the 1990 Workshop on Math. Found. Prog. Semantics. To appear."},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"S.Abramsky and R.Jagadeesan. Games and Full Completeness for Multiplicative Linear Logic. Imperial College Technical Report DOC 92\/24, 1992.","DOI":"10.1007\/3-540-56287-7_113"},{"key":"19_CR4","unstructured":"A.V.Aho, J.E.Hopcroft, and J.D.Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1976."},{"key":"19_CR5","unstructured":"A.Asperti. A Logic for Concurrency. Technical Report. Dipartimento di Informatica, Universita di Pisa, 1987."},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"A.Asperti, G.-L.Ferrari, and R.Gorrieri. Implicative formulae in the\u2019 proofs as computations\u2019 analogy. In Proc. 17-th ACM Symposium on Principles of Programming Languages, San-Francisco, January 1990, p.59\u201371","DOI":"10.1145\/96709.96715"},{"key":"19_CR7","volume-title":"Language in Action","author":"J. Benthem van","year":"1991","unstructured":"J. van Benthem. Language in Action. North-Holland, Amsterdam, 1991."},{"key":"19_CR8","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0168-0072(92)90073-9","volume":"56","author":"A. Blass","year":"1992","unstructured":"A.Blass. A game semantics for linear logic. Annals Pure Appl. Logic, 56 (1992) pp.183\u2013220.","journal-title":"Annals Pure Appl. Logic"},{"key":"19_CR9","volume-title":"Technical Report","author":"A. Brown","year":"1989","unstructured":"A.Brown. Relating Petri Nets to Formulas of Linear Logic. Technical Report. LFCS, Edinburgh, 1989."},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"P.Degano, J.Meseguer, and U.Montanari. Axiomatizing net computations and processes. In Proc. 4-th Annual IEEE Symposium on Logic in Computer Science, Philadelphia, June 1989, p.175\u2013185.","DOI":"10.1109\/LICS.1989.39172"},{"key":"19_CR11","unstructured":"M.R.Garey and D.S.Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. 1979."},{"key":"19_CR12","unstructured":"V.Gehlot and C.A.Gunter. Normal process representatives. In Proc. 5-th Annual IEEE Symposium on Logic in Computer Science, Philadelphia, June 1990."},{"issue":"1","key":"19_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(87)90045-4","volume":"50","author":"J.-Y. Girard","year":"1987","unstructured":"J.-Y.Girard. Linear logic. Theoretical Computer Science, 50:1, 1987, pp.1\u2013102.","journal-title":"Theoretical Computer Science"},{"key":"19_CR14","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1007\/BFb0014972","volume":"n\u2218257","author":"J.-Y. Girard","year":"1987","unstructured":"J.-Y.Girard and Y.Lafont. Linear logic and lazy computation, Proceedings of TAP-SOFT 87, Springer Lecture Notes in Computer Science n\u2218257, 1987, pp. 52\u201366.","journal-title":"Springer Lecture Notes in Computer Science"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"J.-Y.Girard. Towards a Geometry of Interaction. Categories in Computer Science and Logic, Contemporary Mathematics 92, AMS 1989, p.69\u2013108.","DOI":"10.1090\/conm\/092\/1003197"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"J.-Y.Girard. Geometry of interaction I: interpretation of system F, Logic Colloquium 88, eds. Ferro & al., North Holland 1989.","DOI":"10.1016\/S0049-237X(08)70271-4"},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"J.-Y.Girard. Geometry of Interaction II: deadlock-free algorithms, Proceedings of COLOG'88, eds Martin-L\u00f6f & Mints, Springer Lecture Notes in Theoretical Computer Science 417, pp.76\u201393.","DOI":"10.1007\/3-540-52335-9_49"},{"key":"19_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(92)90386-T","volume":"97","author":"J.-Y. Girard","year":"1992","unstructured":"J.-Y.Girard, A.Scedrov, and P.J.Scott, Bounded Linear Logic: A Modular Approach to Polynomial Time Computability, Theoretical Computer Science, 97, 1992, pp.1\u201366.","journal-title":"Theoretical Computer Science"},{"key":"19_CR19","doi-asserted-by":"crossref","unstructured":"J.-Y.Girard. A new constructive logic: classical logic, Mathematical Structures in Computer Science, vol 1.3, 1991.","DOI":"10.1017\/S0960129500001328"},{"key":"19_CR20","doi-asserted-by":"crossref","unstructured":"J.-Y.Girard. On the unity of logic, Annals of Pure and Applied logic, vol. 59.3, 1993.","DOI":"10.1016\/0168-0072(93)90093-S"},{"key":"19_CR21","doi-asserted-by":"crossref","unstructured":"J.-Y.Girard. Linear logic: a survey, Logic & Algebra of Specification, NATO ASI Series F, 94, eds. Bauer & al., Springer Verlag, 1993.","DOI":"10.1007\/978-3-642-58041-3_3"},{"key":"19_CR22","unstructured":"J.-Y.Girard. Geometry of interaction III: the general case, Proceedings of the Workshop on Linear Logic, MIT Press, (to appear)"},{"key":"19_CR23","unstructured":"C.A.Gunter and V.Gehlot. Nets as Tensor Theories. In Proc. 10-th International Conference on Application and Theory of Petri Nets, Bonn, 1989, p.174\u2013191"},{"key":"19_CR24","volume-title":"Ph.D.Thesis","author":"D.H.J. Jongh de","year":"1968","unstructured":"D.H.J. de Jongh. Investigations on the intuitionistic propositional calculus. Ph.D.Thesis, University of Wisconsin, Madison, 1968."},{"key":"19_CR25","unstructured":"M.I.Kanovich. The multiplicative fragment of Linear Logic is NP-complete. Technical Report X-91-13, University of Amsterdam, Institute for Language, Logic, and Information, June 1991"},{"key":"19_CR26","unstructured":"M.I.Kanovich. The Horn fragment of Linear Logic is NP-complete. Technical Report X-91-14, University of Amsterdam, Institute for Language, Logic, and Information, August 1991"},{"key":"19_CR27","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1007\/3-540-54415-1_67","volume":"526","author":"M.I. Kanovich","year":"1991","unstructured":"M.I.Kanovich. Efficient program synthesis: Semantics, Logic, Complexity. Theoretical Aspects of Computer Software, TACS'91, Japan, Sendai, September 1991. In Lecture Notes in Computer Science, 526, p.615\u2013632","journal-title":"Lecture Notes in Computer Science"},{"key":"19_CR28","volume-title":"Technical Report CS-R9157","author":"M.I. Kanovich","year":"1991","unstructured":"M.I.Kanovich. Fast theorem proving in intuitionistic propositional logic. Centre for Mathematics and Computer Science, Computer Science\/Department of Software Technology, Technical Report CS-R9157, December 1991, Amsterdam"},{"key":"19_CR29","doi-asserted-by":"crossref","unstructured":"M.I.Kanovich. Horn Programming in Linear Logic is NP-complete. In Proc. 7-th Annual IEEE Symposium on Logic in Computer Science, Santa Cruz, June 1992, pp.200\u2013210","DOI":"10.1109\/LICS.1992.185533"},{"key":"19_CR30","unstructured":"M.I.Kanovich. Complexity of LL fragments. Email message. 14 July 1992."},{"key":"19_CR31","doi-asserted-by":"crossref","unstructured":"M.I.Kanovich. The complexity of Horn Fragments of Linear Logic, Annals Pure Appl. Logic, (1993) (to appear)","DOI":"10.1016\/0168-0072(94)90085-X"},{"key":"19_CR32","doi-asserted-by":"crossref","unstructured":"M.I.Kanovich. Linear Logic as a Logic of Computations, Annals Pure Appl. Logic, 67 (1994).","DOI":"10.1016\/0168-0072(94)90011-6"},{"key":"19_CR33","unstructured":"M.I.Kanovich. Simulating Linear Logic in 1-Only Linear Logic. CNRS, Laboratoire de Math\u00e9matiques Discr\u00e8tes, Pr\u00e9tirage n\u2218 94-02, January 1994, 81 p. Available by anonymous ftp from host ftp.lmd.univ-mrs.fr and the file pub\/kanovich\/unit-only.dvi."},{"key":"19_CR34","unstructured":"M.I.Kanovich. The Independent Basis of Neutral Formulas in Linear Logic. CNRS, Laboratoire de Math\u00e9matiques Discr\u00e8tes, Pr\u00e9tirage n\u2218 94-08, March 1994, 43 p. Available by anonymous ftp from host ftp.lmd.univ-mrs.fr and the file pub\/kanovich\/neutrals.dvi."},{"key":"19_CR35","doi-asserted-by":"crossref","unstructured":"Y.Lafont and T.Streicher. Games semantics for linear logic. In Proc. 6-th Annual IEEE Symposium on Logic in Computer Science, 43\u201351, Amsterdam, July 1991.","DOI":"10.1109\/LICS.1991.151629"},{"issue":"3","key":"19_CR36","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1080\/00029890.1958.11989160","volume":"65","author":"J. Lambek","year":"1958","unstructured":"J.Lambek. The mathematics of sentence structure. American Mathematical Monthly, 65(3):154\u2013170, 1958.","journal-title":"American Mathematical Monthly"},{"key":"19_CR37","unstructured":"P.Lincoln, J.Mitchell, A.Scedrov, and N.Shancar. Decision Problems for Propositional Linear Logic. Technical Report SRI-CSL-90-08, CSL, SRI International, August 1990."},{"key":"19_CR38","doi-asserted-by":"crossref","unstructured":"P.Lincoln, J.Mitchell, A.Scedrov, and N.Shankar. Decision Problems for Propositional Linear Logic. In Proc. 31st IEEE Symp. on Foundations of Computer Science, 662\u2013671, 1990.","DOI":"10.1109\/FSCS.1990.89588"},{"key":"19_CR39","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0168-0072(92)90075-B","volume":"56","author":"P. Lincoln","year":"1992","unstructured":"P.Lincoln, J.Mitchell, A.Scedrov, and N.Shankar. Decision Problems for Propositional Linear Logic. Annals Pure Appl. Logic, 56 (1992) pp. 239\u2013311.","journal-title":"Annals Pure Appl. Logic"},{"key":"19_CR40","doi-asserted-by":"crossref","unstructured":"P.Lincoln, A.Scedrov, and N.Shancar. Linearizing Intuitionistic Implication. In Proc. 6-th Annual IEEE Symposium on Logic in Computer Science, 51\u201362, Amsterdam, July 1991.","DOI":"10.1109\/LICS.1991.151630"},{"key":"19_CR41","unstructured":"P.Lincoln and T.Winkler. Constant multiplicative Linear Logic is NP-complete. Draft, 1992."},{"key":"19_CR42","doi-asserted-by":"crossref","unstructured":"N.Marti-Oliet and J.Mesequer. From Petri Nets to Linear Logic. In: Springer LNCS 389, ed. by D.R.Pitt et al., 1989, p.313\u2013340","DOI":"10.1007\/BFb0018359"},{"key":"19_CR43","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0001-8708(82)90048-2","volume":"46","author":"E. Mayr","year":"1982","unstructured":"E.Mayr and A.Meyer. The complexity of the word problems for commutative semigroups and polynomial ideals. Advances in Mathematics, 46, 305\u2013329, 1982.","journal-title":"Advances in Mathematics"},{"issue":"N3","key":"19_CR44","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1137\/0213029","volume":"13","author":"E. Mayr","year":"1984","unstructured":"E.Mayr, An algorithm for the general Petri net reachability problem. SIAM J.Comput., 13, N 3, 441\u2013460, 1984.","journal-title":"SIAM J.Comput."},{"key":"19_CR45","unstructured":"J.Meseguer and U.Montanari. Petri Nets Are Monoids. Research Report SRI-CSL-88-3, SRI International, Menlo Park, January 1988."},{"issue":"3","key":"19_CR46","doi-asserted-by":"crossref","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"M. Minsky","year":"1961","unstructured":"M.Minsky. Recursive unsolvability of Post's problem of\u2019 tag\u2019 and other topics in the theory of Turing machines. Annals of Mathematics, 74:3:437\u2013455, 1961.","journal-title":"Annals of Mathematics"},{"key":"19_CR47","doi-asserted-by":"crossref","first-page":"327","DOI":"10.2307\/2963526","volume":"25","author":"I. Nishimura","year":"1960","unstructured":"I.Nishimura. On formulas of one propositional variable in intuitionistic propositional calculus. J.Symb.Logic, 25, 327\u2013331, 1960.","journal-title":"J.Symb.Logic"},{"key":"19_CR48","first-page":"1","volume-title":"AMAST'91: Algebraic Methodology and Software Technology","author":"V.R. Pratt","year":"1992","unstructured":"V.R.Pratt, Event spaces and their linear logic, In AMAST'91: Algebraic Methodology and Software Technology, Iowa City, 1991, Workshops in Computing, 1\u201323, Springer-Verlag, 1992."},{"key":"19_CR49","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0304-3975(79)90006-9","volume":"9","author":"R. Statman","year":"1979","unstructured":"R.Statman, Intuitionistic propositional logic is Polynomial-Space complete. Theoret. Computer Sci., 9, 67\u201372, 1979.","journal-title":"Theoret. Computer Sci."},{"key":"19_CR50","unstructured":"A.S.Troelstra, Lectures on Linear Logic, CSLI Lecture Notes No. 29, Center for the Study of Language and Information, Stanford University, 1992."}],"container-title":["Lecture Notes in Computer Science","Logical Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58140-5_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:20:34Z","timestamp":1742595634000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58140-5_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540581406","9783540484424"],"references-count":50,"URL":"https:\/\/doi.org\/10.1007\/3-540-58140-5_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]},"assertion":[{"value":"7 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}