Categories of Coalgebras with Monadic Homomorphisms

Abstract : Abstract graph transformation approaches traditionally consider graph structures as algebras over signatures where all function symbols are unary.Attributed graphs, with attributes taken from (term) algebras over arbitrary signatures do not fit directly into this kind of transformation approach, since algebras containing function symbols taking two or more arguments do not allow component-wise construction of pushouts. We show how shifting from the algebraic view to a coalgebraic view of graph structures opens up additional flexibility, and enables treating term algebras over arbitrary signatures in essentially the same way as unstructured label sets. We integrate substitution into our coalgebra homomorphisms by identifying a factoring over the term monad, and obtain a flexible framework for graphs with symbolic attributes. This allows us to prove that pushouts can be constructed for homomorphisms with unifiable substitution components.We formalised the presented development in Agda, which crucially aided the exploration of the complex interaction of the different functors, and enables us to report all theorems as mechanically verified.
Type de document :
Communication dans un congrès
Marcello M. Bonsangue. 12th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Apr 2014, Grenoble, France. Lecture Notes in Computer Science, LNCS-8446, pp.151-167, 2014, Coalgebraic Methods in Computer Science. 〈10.1007/978-3-662-44124-4_9〉
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01408758
Contributeur : Hal Ifip <>
Soumis le : lundi 5 décembre 2016 - 13:25:10
Dernière modification le : lundi 5 décembre 2016 - 14:28:33
Document(s) archivé(s) le : mardi 21 mars 2017 - 01:29:58

Fichier

328263_1_En_9_Chapter.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Wolfram Kahl. Categories of Coalgebras with Monadic Homomorphisms. Marcello M. Bonsangue. 12th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Apr 2014, Grenoble, France. Lecture Notes in Computer Science, LNCS-8446, pp.151-167, 2014, Coalgebraic Methods in Computer Science. 〈10.1007/978-3-662-44124-4_9〉. 〈hal-01408758〉

Partager

Métriques

Consultations de la notice

41

Téléchargements de fichiers

43