hal-00741077, version 2
Using models to model-check recursive schemes
Sylvain Salvati
a, 1Igor Walukiewicz 2
Résumé : We propose a model-based approach to the model checking problem for recursive schemes. Since simply typed lambda calculus with the fixpoint operator, lambda-Y-calculus, is equivalent to schemes, we propose to use a model of lambda-Y to discriminate the terms that satisfy a given property. If a model is finite in every type, this gives a decision procedure. We provide a construction of such a model for every property expressed by automata with trivial acceptance conditions and divergence testing. We argue that having a model capable of recognizing terms satisfying a given property has other benefits than just providing decidability of the model-checking problem. We show a very simple construction transforming a scheme to a scheme reflecting a given property.
- a – INRIA
- 1 : INRIA Bordeaux - Sud-Ouest (INRIA Bordeaux - Sud-Ouest)
- INRIA
- 2 : Laboratoire Bordelais de Recherche en Informatique (LaBRI)
- CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) – Université Victor Segalen - Bordeaux II
- Domaine : Informatique/Logique en informatique
- Versions disponibles : v1 (11-10-2012) v2 (12-10-2012)
- hal-00741077, version 2
- http://hal.inria.fr/hal-00741077
- oai:hal.inria.fr:hal-00741077
- Contributeur : Sylvain Salvati
- Soumis le : Vendredi 12 Octobre 2012, 10:57:30
- Dernière modification le : Vendredi 12 Octobre 2012, 14:46:29






Documents associés
Exporter