Article Dans Une Revue Theoretical Computer Science Année : 2025

Algebraic properties and transformations of monographs

Résumé

Monographs are graph-like structures with directed edges of unlimited length that are freely adjacent to each other. The standard nodes are represented as edges of length zero. They can be drawn in a way consistent with standard graphs and many others, like E-graphs or 8-graphs. The category of monographs share many properties with the categories of graph structures (algebras of monadic many-sorted signatures, equivalent to presheaf toposes), except that there is no terminal monograph. It is universal in the sense that its slice categories (or categories of typed monographs) are equivalent to the categories of graph structures. Type monographs thus emerge as a natural way of specifying graph structures. A detailed analysis of single and double pushout transformations of monographs is provided, and a notion of attributed typed monographs generalizing typed attributed E-graphs is analyzed w.r.t. attribute-preserving transformations.

Fichier principal
Vignette du fichier
hal-final.pdf (518) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04905427 , version 1 (22-01-2025)

Identifiants

Citer

Thierry Boy de la Tour. Algebraic properties and transformations of monographs. Theoretical Computer Science, 2025, 1024, pp.114939. ⟨10.1016/j.tcs.2024.114939⟩. ⟨hal-04905427⟩
0 Consultations
0 Téléchargements

Altmetric

Partager

More