s'authentifier
version française rss feed

hal-00585717, version 1

Decomposing Logical Relations with Forcing

Guilhem Jaber 12, Nicolas Tabareau 2

(23/03/2011)

Résumé : Logical relations have now the maturity to deal with program equivalence for realistic programming languages with features likes recursive types, higher-order references and first-class continuations. However, such advanced logical relations---which are defined with technical developments like step-indexing or heap abstractions using recursively defined worlds---can make a proof tedious. A lot of work has been done to hide step-indexing in proofs, using Gödel-Löb logic. But to date, step-indexes have still to appear explicitely in particular constructions, for instance when building recursive worlds in a stratified way. In this paper, we go one step further, proposing an extension of Abadi-Plotkin logic with forcing construction which enables to encapsulate reasoning about step-indexing or heap in different layers. Moreover, it gives a uniform and abstract management of step-indexing for recursive terms or types and for higher-order references.

  • Domaine : Informatique/Logique en informatique
    Informatique/Langage de programmation
 
  • hal-00585717, version 1
  • oai:hal.archives-ouvertes.fr:hal-00585717
  • Contributeur : 
  • Soumis le : Mercredi 13 Avril 2011, 18:44:14
  • Dernière modification le : Jeudi 14 Avril 2011, 09:12:18
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...