inria-00089497, version 1
Incremental Parametric Development of Greedy Algorithms
Dominique Cansell 1Dominique Méry
1
6th International Workshop on Automatic Verification of Critical Systems - AVoCS 2006 (2006) 48-62
Résumé : The event B method provides a general framework for modelling both data structures and algorithms. B models are validated by discharging proof obligations ensuring safety properties. We address the problem of development of greedy algorithms using the seminal work of S. Curtis; she has formalised greedy algorithms in a relational calculus and has provided a list of results ensuring optimality results. Our first contribution is a re-modelling of Curtis's results in the event B framework and a mechanical checking of theorems on greedy algorithms The second contribution is the reuse of the mathematical framework for developing greedy algorithms from event B models; since the resulting event B models are generic, we show how to instantiate generic event B models to derive specific greedy algorithms; generic event B developments help in managing proofs complexity. Consequently, we contribute to the design of a library of proof-based developed algorithms.
- 1 : MOSEL (INRIA Lorraine - LORIA)
- INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
- Domaine : Informatique/Logique en informatique
- Mots-clés : Formal method – B event-based method – refinement – safety – greedy algorithms
- inria-00089497, version 1
- http://hal.inria.fr/inria-00089497
- oai:hal.inria.fr:inria-00089497
- Contributeur : Stephan Merz
- Soumis le : Vendredi 18 Août 2006, 19:53:03
- Dernière modification le : Mardi 10 Mai 2011, 15:48:46