首页> 外文期刊>Theoretical computer science >On principal types of combinators
【24h】

On principal types of combinators

机译:关于组合器的主要类型

获取原文
获取原文并翻译 | 示例
       

摘要

In this paper we study (in some cases) the relationship between the combinatory completeness of a set of typable combinators, with simple types, for a system of lambda-calculus and the axiomatic completeness, under substitution and modus ponens, of the respective set of principal types for the corresponding logical system. We show that combinatory completeness is a necessary, but not sufficient, condition for axiomatic completeness in the lambda k- and in the lambda g-calculus, while the two problems become equivalent for the BCK-lambda- as well as for the BCI-lambda-calculus. Furthermore, we present an algorithm which, whenever (B, alpha) is a principal pair for some normal BCK-lambda-term M, reconstructs M up to a-conversion and which fails if there is no normal BCK-lambda-term for which (B,alpha) is a principal pair. From the correctness proof of the algorithm we also obtain another proof for the fact that each BCK-lambda-term in normal form is completely determined by its principal pairs. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 13]
机译:在本文中,我们研究(在某些情况下)对于lambda演算系统,具有简单类型的一组可键入组合符的组合完整性与相应替换集和惯用形式下公理性完整性之间的关系。对应逻辑系统的主体类型。我们表明组合完整性是lambda k-和lambda g-演算中公理完整性的必要但不充分的条件,而对于BCK-lambda-和BCI-lambda这两个问题变得等效-结石。此外,我们提出了一种算法,只要(B,alpha)是某个正常BCK-lambda-term M的主体对,就将M重构到a转换,并且如果没有正常的BCK-lambda-term会失败。 (B,alpha)是主要对。从该算法的正确性证明中,我们还获得了以下事实的证明:正常形式的每个BCK-lambda项完全由其主对决定。 (C)2000 Elsevier Science B.V.保留所有权利。 [参考:13]

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号