Search

Abstract: We consider the multiplicative and exponential fragment of linear logic (MELL) and give a geometry of interaction (GoI) semantics for it based on unique decomposition categories. We prove a soundness and finiteness theorem for this interpretation. We show that Girard''s original approach to GoI 1 via operator algebras is exactly captured in this categorical framework. [Copyright &y& Elsevier]

Abstract: Ludics [J.-Y. Girard, Locus solum, Math. Structures in Comput. Sci. 11 (2001) 301–506] is a recent proposal of analysis of interaction, developed by abstracting away from proof-theory. It provides an elegant, abstract setting in which interaction between agents (proofs/programs/processes) can be studied at a foundational level, together with a notion of equivalence from the point of view of the observer. An agent should be seen as some kind of black box. An interactive observation on an agent is obtained by testing it against other agents. In this paper we explore what can be observed interactively in this setting. In particular, we characterize the objects that can be observed in a single test: the primitive observables of the theory. Our approach builds on an analysis of the geometrical properties of the agents, and highlights a deep interleaving between two partial orders underlying the combinatorial structures: the spatial one and the temporal one. [Copyright &y& Elsevier]