首页    期刊浏览 2025年02月23日 星期日
登录注册

文章基本信息

  • 标题:Continuation-Passing Style and Strong Normalisation for Intuitionistic Sequent Calculi
  • 本地全文:下载
  • 作者:Jose Espirito Santo ; Ralph Matthes ; Luis Pinto
  • 期刊名称:Logical Methods in Computer Science
  • 印刷版ISSN:1860-5974
  • 电子版ISSN:1860-5974
  • 出版年度:2009
  • 卷号:5
  • 期号:02
  • DOI:10.2168/LMCS-5(2:11)2009
  • 出版社:Technical University of Braunschweig
  • 摘要:

    The intuitionistic fragment of the call-by-name version of Curien and
    Herbelin's λ--μ-μ~-calculus is isolated and proved strongly
    normalising by means of an embedding into the simply-typed lambda-calculus. Our
    embedding is a continuation-and-garbage-passing style translation, the
    inspiring idea coming from Ikeda and Nakazawa's translation of Parigot's
    λ-μ-calculus. The embedding strictly simulates reductions while usual
    continuation-passing-style transformations erase permutative reduction steps.
    For our intuitionistic sequent calculus, we even only need "units of garbage"
    to be passed. We apply the same method to other calculi, namely successive
    extensions of the simply-typed λ-calculus leading to our intuitionistic
    system, and already for the simplest extension we consider (λ-calculus
    with generalised application), this yields the first proof of strong
    normalisation through a reduction-preserving embedding. The results obtained
    extend to second and higher-order calculi.

  • 关键词:Lambda-Calculus;Extension;Embeddings
国家哲学社会科学文献中心版权所有