{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,20]],"date-time":"2026-09-20T04:58:14Z","timestamp":1789880294564,"version":"4.0.1"},"reference-count":22,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2011,1,24]],"date-time":"2011-01-24T00:00:00Z","timestamp":1295827200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2011,2]]},"abstract":"<jats:p>Game semantics describe the interactive behaviour of proofs by interpreting formulas as games on which proofs induce strategies. Such a semantics is introduced here for capturing dependencies induced by quantifications in first-order propositional logic. One of the main difficulties that has to be faced during the elaboration of this kind of semantics is to characterise definable strategies, that is, strategies that actually behave like a proof. This is usually done by restricting the model to strategies satisfying subtle combinatorial conditions, whose preservation under composition is often difficult to show. In this paper we present an original methodology to achieve this task, which requires a combination of advanced tools from game semantics, rewriting theory and categorical algebra. We introduce a diagrammatic presentation of the monoidal category of definable strategies of our model using generators and relations: these strategies can be generated from a finite set of atomic strategies, and the equality between strategies admits a finite axiomatisation, and this equational structure corresponds to a polarised variation of the bialgebra notion. The work described in this paper thus forms a bridge between algebra and denotational semantics in order to reveal the structure of dependencies induced by first-order quantifiers, and lays the foundations for a mechanised analysis of causality in programming languages.<\/jats:p>","DOI":"10.1017\/s0960129510000459","type":"journal-article","created":{"date-parts":[[2011,1,24]],"date-time":"2011-01-24T10:23:56Z","timestamp":1295864636000},"page":"65-110","source":"Crossref","is-referenced-by-count":5,"title":["The structure of first-order causality"],"prefix":"10.1017","volume":"21","author":[{"given":"SAMUEL","family":"MIMRAM","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2011,1,24]]},"reference":[{"key":"S0960129510000459_ref17","unstructured":"Mimram S. (2008) S\u00e9mantique des jeux asynchrones et r\u00e9\u00e9criture 2-dimensionnelle, Ph.D. thesis, Universit\u00e9 Paris Diderot."},{"key":"S0960129510000459_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74407-8_27"},{"key":"S0960129510000459_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)81498-3"},{"key":"S0960129510000459_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-9839-7"},{"key":"S0960129510000459_ref12","doi-asserted-by":"crossref","unstructured":"Lawvere F. W. (1963) Functorial Semantics of Algebraic Theories and Some Algebraic Problems in the context of Functorial Semantics of Algebraic Theories, Ph.D. thesis, Columbia University.","DOI":"10.1073\/pnas.50.5.869"},{"key":"S0960129510000459_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-4049(03)00069-0"},{"key":"S0960129510000459_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-59340-3_13"},{"key":"S0960129510000459_ref9","first-page":"147","article-title":"Composing PROPs","volume":"13","author":"Lack","year":"2004","journal-title":"Theory and Applications of Categories"},{"key":"S0960129510000459_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(91)90003-P"},{"key":"S0960129510000459_ref6","doi-asserted-by":"publisher","DOI":"10.1145\/351268.351299"},{"key":"S0960129510000459_ref5","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.2917"},{"key":"S0960129510000459_ref22","first-page":"325","article-title":"Event Structures","volume":"255","author":"Winskel","year":"1987","journal-title":"Advances in Petri Nets"},{"key":"S0960129510000459_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044481714-3\/50009-6"},{"key":"S0960129510000459_ref3","first-page":"375","volume-title":"Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages","author":"Ghica","year":"2007"},{"key":"S0960129510000459_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/S0001-8708(03)00018-5"},{"key":"S0960129510000459_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90054-W"},{"key":"S0960129510000459_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(76)90013-X"},{"key":"S0960129510000459_ref20","first-page":"81","article-title":"The Free Adjunction","volume":"27","author":"Schanuel","year":"1986","journal-title":"Cahiers de Topologie et G\u00e9om\u00e9trie Diff\u00e9rentielle Cat\u00e9goriques"},{"key":"S0960129510000459_ref18","unstructured":"Mimram S. (2010) Computing critical pairs in 2-dimensional rewriting systems. In: Lynch, C. (ed.) Proceedings of the 21st International Conference on Rewriting Techniques and Applications, RTA 10, 11-13 July 2010, Edinburgh. Leibniz International Proceedings in Informatics (LIPIcs) 6, Schloss Dagstuhl \u2013 Leibniz-Center for Informatics gGmbH, Dagstuhl Publishing 227\u2013242."},{"key":"S0960129510000459_ref7","unstructured":"Hyland M. and Schalk A. (2002) Games on Graphs and Sequentially Realizable Functionals. Proceedings of the 17th IEEE Symposium on Logic in Computer Science 257\u2013264."},{"key":"S0960129510000459_ref19","first-page":"221","article-title":"On the PROP Corresponding to Bialgebras","volume":"43","author":"Pirashvili","year":"2002","journal-title":"Cah. Top. G\u00e9om. Diff. Cat."},{"key":"S0960129510000459_ref13","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1965-11234-4"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129510000459","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T19:36:16Z","timestamp":1556393776000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129510000459\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,24]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["S0960129510000459"],"URL":"https:\/\/doi.org\/10.1017\/s0960129510000459","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1,24]]}}}