44 articles – 42 references  [version française]

ensl-00155308, version 2

Complete Lattices and Up-to Techniques

Damien Pous () 1

5th Asian Symposium on Programming Languages and Systems 351-366

Abstract: We propose a theory of up-to techniques for proofs by coinduction, in the setting of complete lattices. This theory improves over existing results by providing a way to compose arbitrarily complex techniques with standard techniques, expressed using a very simple and modular semi-commutation property. Complete lattices are enriched with monoid operations, so that we can recover standard results about labelled transitions systems and their associated behavioural equivalences at an abstract, "point-free'' level. Our theory gives for free a powerful method for validating up-to techniques. We use it to revisit up to contexts techniques, which are known to be difficult in the weak case: we show that it is sufficient to check basic conditions about each operator of the language, and then rely on an iteration technique to deduce general results for all contexts.

  • 1:  Laboratoire de l'Informatique du Parallélisme (LIP)
  • Université de Lyon – CNRS : UMR5668 – INRIA – École Normale Supérieure - Lyon – Université Claude Bernard - Lyon I
  • Domain : Computer Science/Distributed, Parallel, and Cluster Computing
    Computer Science/Other
  • Keywords : Up-to techniques – Bisimulation – Complete lattice – Contexts – Termination
  • Comment : 24 p.
  • Available versions :  v1 (2007-06-19) v2 (2007-09-24)
 
  • ensl-00155308, version 2
  • oai:hal-ens-lyon.archives-ouvertes.fr:ensl-00155308
  • From: 
  • Submitted on: Saturday, 22 September 2007 16:37:05
  • Updated on: Thursday, 13 December 2007 21:34:31