Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Calculating Invariants as Coreflexive Bisimulations
| |
|
Calculating Invariants as Coreflexive Bisimulations
Luís S. Barbosa1, José N. Oliveira1 and Alexandra Silva2
| (1) |
CCTC, Universidade do Minho, 4700-320 Braga, Portugal |
| (2) |
Centrum voor Wiskunde en Informatica (CWI), Kruislaan 413, NL-1098 SJ Amsterdam, |
Abstract
Invariants, bisimulations and assertions are the main ingredients of coalgebra theory applied to software systems. In this
paper we reduce the first to a particular case of the second and show how both together pave the way to a theory of coalgebras
which regards invariant predicates as types. An outcome of such a theory is a calculus of invariants’ proof obligation discharge,
a fragment of which is presented in the paper.
The approach has two main ingredients: one is that of adopting relations as “first class citizens” in a pointfree reasoning
style; the other lies on a synergy found between a relational construct, Reynolds’ relation on functions involved in the abstraction theorem on parametric polymorphism and the coalgebraic account of bisimulations and invariants. This leads to an elegant proof of
the equivalence between two different definitions of bisimulation found in coalgebra literature (due to B. Jacobs and Aczel
& Mendler, respectively) and to their instantiation to the classical Park-Milner definition popular in process algebra.
Keywords coalgebraic reasoning - proof obligations - pointfree transform - program calculation
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|