Outils

Formalisation en Rocq de la transformation de graphes catégorielle

Date
Vendredi 04 décembre 2026
Horaires

10h

Intervenant(s)

Soutenance de thèse de Samuel ARSAC, sous la direction de Russell HARMER et la codirection de Damien POUS

Langue(s) des interventions
Description générale

Résumé de la thèse

La réécriture catégorielle de graphes, ou transformation de graphes, est une théorie permettant de définir des règles de réécriture sur des graphes, en association avec la sémantique opérationnelle du double pushout (DPO), en utilisant les catégories pour faire abstraction des différences entre les différents modèles de graphes concrets. Cette théorie a trouvé diverses applications en informatique, notamment dans le génie logiciel basé sur des modèles et dans la définition de la syntaxe et de la sémantique des langages de spécification visuels et orientés objet, en physique mathématique, comme dans la réécriture des diagrammes de cordes, et dans la modélisation de systèmes (bio-)chimiques, où les règles de réécriture modélisent les interactions entre particules ou molécules. Dans ce domaine, on utilise souvent des catégories adhésives. Celles-ci incluent toutes les catégories de préfaisceaux, et donc de nombreuses catégories de multigraphes. Cependant, il existe d’importantes catégories de graphes qui ne sont pas adhésives. Cela a motivé l’introduction de notions plus faibles pour couvrir ces cas tout en permettant d’établir de bonnes propriétés de la sémantique DPO. Par exemple, la catégorie des graphes simples n’est que rm-quasi-adhésive, tandis que la catégorie des graphes de termes est rm-adhésive. La littérature sur ce sujet est fragmentée, diverses notions ayant été introduites au fil des ans, ce qui rend plus difficile la compréhension du champ d’application des théorèmes figurant dans les publications plus anciennes. Leur formalisation dans un assistant de preuve donne l’occasion de réexaminer et de clarifier les hypothèses et les démonstrations des principaux théorèmes.
L'une des difficultés d'une telle formalisation réside dans la structuration des définitions, de manière à ce que les lemmes puissent être énoncés et utilisés sous leur forme la plus générale, et que les instances puissent être définies de la manière la plus efficace possible et déduites automatiquement. Pour ce faire, nous avons choisi d’utiliser Hierarchy Builder (HB), qui fournit un langage de haut niveau permettant de définir des hiérarchies de structures, avec des fonctionnalités avancées telles que l’héritage multiple. HB vérifie la cohérence de ces descriptions de haut niveau et les traduit en records Rocq, structures canoniques et déclarations de coercions appropriés, afin d’obtenir des notations concises et des mécanismes d’inférence robustes sans intervention supplémentaire de l’utilisateur. Nous implémentons tout d’abord une bibliothèque de théorie des catégories à usage général comprenant toutes les notions de base dont nous avons besoin. Ensuite, nous formalisons (i) les définitions des catégories adhésives, rm-adhésives et rm-quasi-adhésives, (ii) deux théorèmes importants fournissant plusieurs caractérisations de ces structures, (iii) deux théorèmes clés issus de la réécriture catégorielle de graphes, (iv) des instances prototypiques (types, setoïdes, types finis, graphes simples, préfaisceaux et catégories slice), et (v) une instance spécifique (ordinaux finis) avec des pushouts et des pullbacks calculables efficacement. Les bibliothèques abstraites ne dépendent pas d’axiomes, et nous détaillons les axiomes nécessaires à certaines des instances concrètes.


Rocq formalization of categorical graph transformation

Categorical graph rewriting, or graph transformation, is a framework for defining rewriting rules on graphs, together with the double-pushout (DPO) operational semantics, using categories to abstract away the differences between specific concrete graph models. It has found various applications in computer science, such as model-based software engineering and in defining the syntax and semantics of visual and object-oriented specification languages; in mathematical physics, such as the rewriting of string diagrams; and in modeling (bio-)chemical systems, where rewriting rules model the interactions between particles or molecules. In this domain, one often uses adhesive categories; these include all presheaf categories, hence many categories of multigraphs. However, there are important categories of graphs that are not adhesive. This motivated the introduction of weaker notions to cover those cases and still make it possible to establish good properties of the DPO semantics. For example, the category of simple graphs is only rm-quasiadhesive while the category of term graphs is rm-adhesive. The literature on this subject is fragmented, with various notions introduced over the years, making the field of application of theorems in older publications harder to understand. Formalizing them in a proof assistant gives an opportunity to reexamine and clarify the hypotheses and the proofs of the main theorems. A difficult task in such a formalization consists in structuring the definitions so that lemmas can be stated and used in their most general form, and instances can be defined in the most efficient way and inferred automatically. To this end, we choose to use Hierarchy Builder (HB), which provides a high-level language to define hierarchies of structures, with advanced features such as multiple inheritance. HB checks the consistency of these high-level descriptions and translates them into appropriate Rocq records, canonical structures and coercion declarations, to obtain concise notations and robust inference mechanisms without further user input. We first implement a general purpose category theory library including all the basic notions we require. Then, we formalize (i) the definitions of adhesive, rm-adhesive and rm-quasiadhesive categories; (ii) two important theorems providing several characterizations of those structures; (iii) two key theorems from categorical graph rewriting; (iv) prototypical instances (types, setoids, finite types, simple graphs, presheaves and slice categories); and (v) a specific instance (finite ordinals) with efficiently computable pushouts and pullbacks. The abstract libraries are axiom-free, and we detail the axioms which are needed for some of the concrete instances.

Gratuit

Mots clés

Disciplines