{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:06:40Z","timestamp":1725664000390},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540578871"},{"type":"electronic","value":"9783540483830"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57887-0_119","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T08:38:48Z","timestamp":1330245528000},"page":"642-666","source":"Crossref","is-referenced-by-count":5,"title":["Petri nets, Horn programs, Linear Logic, and vector games"],"prefix":"10.1007","author":[{"given":"Max I.","family":"Kanovich","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"33_CR1","unstructured":"S.Abramsky. Computational interpretation of linear logic. Imperial College Research Report DOC 90\/20, 1990."},{"key":"33_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":"33_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":"33_CR4","unstructured":"A.Asperti. A Logic for Concurrency. Technical Report. Dipartimento di Informatica, Universita di Pisa, 1987."},{"key":"33_CR5","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":"33_CR6","volume-title":"Language in Action","author":"J. Benthem van","year":"1991","unstructured":"J. van Benthem. Language in Action. North-Holland, Amsterdam, 1991."},{"key":"33_CR7","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":"33_CR8","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":"33_CR9","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":"33_CR10","unstructured":"M.R.Garey and D.S.Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. 1979."},{"key":"33_CR11","doi-asserted-by":"crossref","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.","DOI":"10.1109\/LICS.1990.113746"},{"key":"33_CR12","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\u2013102, 1987.","journal-title":"Theoretical Computer Science"},{"key":"33_CR13","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:1\u201366, 1992.","journal-title":"Theoretical Computer Science"},{"key":"33_CR14","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":"33_CR15","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":"33_CR16","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":"33_CR17","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":"33_CR18","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":"33_CR19","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":"33_CR20","doi-asserted-by":"crossref","unstructured":"M.I.Kanovich. Linear Logic as a Logic of Computations, Annals Pure Appl. Logic, (1993) (to appear)","DOI":"10.1016\/0168-0072(94)90011-6"},{"key":"33_CR21","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"},{"key":"33_CR22","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":"33_CR23","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":"33_CR24","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":"33_CR25","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":"33_CR26","unstructured":"P.Lincoln and T.Winkler. Constant multiplicative Linear Logic is NP-complete. Draft, 1992."},{"key":"33_CR27","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":"33_CR28","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":"33_CR29","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":"33_CR30","volume-title":"Research Report SRI-CSL-88-3","author":"J. Meseguer","year":"1988","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":"33_CR31","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":"33_CR32","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":"33_CR33","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","Theoretical Aspects of Computer Software"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57887-0_119.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T14:36:35Z","timestamp":1687271795000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57887-0_119"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540578871","9783540483830"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/3-540-57887-0_119","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}