Presentation of a Game Semantics for First-Order Propositional Logic - Computer Science > Logic in Computer ScienceReportar como inadecuado




Presentation of a Game Semantics for First-Order Propositional Logic - Computer Science > Logic in Computer Science - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: Game semantics aim at describing the interactive behaviour of proofs byinterpreting formulas as games on which proofs induce strategies. In thisarticle, we introduce a game semantics for a fragment of first orderpropositional logic. One of the main difficulties that has to be faced whenconstructing such semantics is to make them precise by characterizing definablestrategies - that is strategies which actually behave like a proof. Thischaracterization is usually done by restricting to the model to strategiessatisfying subtle combinatory conditions such as innocence, whose preservationunder composition is often difficult to show. Here, we present an originalmethodology to achieve this task which requires to combine tools from gamesemantics, rewriting theory and categorical algebra. We introduce adiagrammatic presentation of definable strategies by the means of generatorsand relations: those strategies can be generated from a finite set of``atomic- strategies and that the equality between strategies generated insuch a way admits a finite axiomatization. These generators satisfy laws whichare a variation of bialgebras laws, thus bridging algebra and denotationalsemantics in a clean and unexpected way.



Autor: Samuel Mimram PPS

Fuente: https://arxiv.org/







Documentos relacionados