Using models to model-check recursive schemes - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Preprints, Working Papers, ... Year : 2012

Using models to model-check recursive schemes

Sylvain Salvati

Abstract

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.
Fichier principal
Vignette du fichier
m.pdf (339.94 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-00741077 , version 1 (11-10-2012)
hal-00741077 , version 2 (12-10-2012)

Identifiers

  • HAL Id : hal-00741077 , version 1

Cite

Sylvain Salvati, Igor Walukiewicz. Using models to model-check recursive schemes. 2012. ⟨hal-00741077v1⟩
199 View
222 Download

Share

Gmail Facebook X LinkedIn More