Publications

Conference Papers

Une logique pour représenter des variations propositionnelles

Published in Journées d'intelligence artificielle fondamentale -- plateforme AFIA 2023, 2023

La logique propositionnelle (comme d’autres logiques) peut être vue comme une façon de représenter des ensembles d’états du monde (les interprétations). La représentation de variations d’un ensemble d’états du monde à un autre est motivée par des travaux sur le raisonnement à partir de cas : la comparaison entre deux problèmes et le passage d’une solution à une autre peuvent être vus comme des variations d’un ensemble d’états à un autre. Cela a conduit à une notation pour représenter ces variations (une syntaxe) et cet article étudie comment associer à cette notation une sémantique en théorie des modèles dans laquelle une interprétation est un couple d’interprétations en logique propositionnelle (un des états et l’autre). L’article entame une étude classique de cette logique (syntaxe, sémantique, équivalences, NP-complétude de la satisfiabilité, etc.) et de façons d’associer à un couple de formules propositionnelles une formule de cette logique. L’article se termine par une discussion envisageant une poursuite de cette étude et des applications potentielles.

Recommended citation: Nicolas François, Thomas Laure, Jean Lieber. Une logique pour représenter des variations propositionnelles. Journées d'intelligence artificielle fondamentale -- plateforme AFIA 2023, Zied Bouraoui; François Schwarzentruber; Anaëlle Wilczynski, Jul 2023, Strasbourg, France. pp.11. ⟨hal-04268839⟩
Download Paper

Preprints

Existential and positive games: a comonadic and axiomatic view

Published in , 2025

A number of model-comparison games central to (finite) model theory, such as pebble and Ehrenfeucht-Fraïssé games, can be captured as comonads on categories of relational structures. In particular, the coalgebras for these comonads encode in a syntax-free way preservation of resource-indexed logic fragments, such as first-order logic with bounded quantifier rank or a finite number of variables. In this paper, we extend this approach to existential and positive fragments (i.e., without universal quantifiers and without negations, respectively) of first-order and modal logic. We show, both concretely and at the axiomatic level of arboreal categories, that the preservation of existential fragments is characterised by the existence of so-called pathwise embeddings, while positive fragments are captured by a newly introduced notion of positive bisimulation. As an application, we offer a new proof of an equi-resource Lyndon positivity theorem for (multi)modal logic.

Recommended citation: S. Abramsky, T. Laure, L. Reggio (2025) "Existential and positive games: a comonadic and axiomatic view."
Download Paper | Download Bibtex