Krivine machines and higher-order schemes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2011

Krivine machines and higher-order schemes

Résumé

We propose a new approach to analysing higher-order recursive schemes. Many results in the literature use automata models generalising pushdown automata, most notably higher-order pushdown automata with collapse (CPDA). Instead, we propose to use the Krivine machine model. Compared to CPDA, this model is closer to lambda-calculus, and incorporates nicely many invariants of computations, as for example the typing information. The usefulness of the proposed approach is demonstrated with new proofs of two central results in the field: the decidability of the local and global model checking problems for higher-order schemes with respect to the mu-calculus.
Fichier principal
Vignette du fichier
hpda-dec.pdf (295.39 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00589407 , version 1 (28-04-2011)

Identifiants

  • HAL Id : inria-00589407 , version 1

Citer

Sylvain Salvati, Igor Walukiewicz. Krivine machines and higher-order schemes. [Research Report] 2011, pp.17. ⟨inria-00589407⟩
136 Consultations
182 Téléchargements

Partager

Gmail Facebook X LinkedIn More