A Complete Logic for Behavioural Equivalence in Coalgebras of Finitary Set Functors - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

A Complete Logic for Behavioural Equivalence in Coalgebras of Finitary Set Functors

David Sprunger
  • Fonction : Auteur
  • PersonId : 999347

Résumé

This paper presents a sound and complete sequent-style deduction system for determining behavioural equivalence in coalgebras of finitary set functors preserving weak pullbacks. We select finitary set functors because they are quotients of polynomial functors: the polynomial functor provides a ready-made signature and the quotient provides necessary additional axioms. We also show that certain operations on functors can be expressed with uniform changes to the presentations of the input functors, making this system compositional for a range of widely-studied classes of functors, such as the Kripke polynomial functors. Our system has roots in the $FLR_0$ proof system of Moschovakis et al., particularly as used by Moss, Wennstrom, and Whitney for non-wellfounded sets. Similarities can also be drawn to expression calculi in the style of Bonsangue, Rutten, and Silva.
Fichier principal
Vignette du fichier
418352_1_En_10_Chapter.pdf (321.64 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01446025 , version 1 (25-01-2017)

Licence

Paternité

Identifiants

Citer

David Sprunger. A Complete Logic for Behavioural Equivalence in Coalgebras of Finitary Set Functors. 13th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Apr 2016, Eindhoven, Netherlands. pp.156-173, ⟨10.1007/978-3-319-40370-0_10⟩. ⟨hal-01446025⟩
58 Consultations
137 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More