ensl-00155308, version 2
Complete Lattices and Up-to Techniques
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:
- 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
- http://hal-ens-lyon.archives-ouvertes.fr/ensl-00155308
- 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


Associated documents
Export