首页> 外文会议>Automata, languages and programming >On Constructor Rewrite Systems and the Lambda-Calculus
【24h】

On Constructor Rewrite Systems and the Lambda-Calculus

机译:构造函数重写系统和Lambda演算

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

摘要

We prove that orthogonal constructor term rewrite systems and lambda-calculus with weak (i.e., no reduction is allowed under the scope of a lambda-abstraction) call-by-value reduction can simulate each other with a linear overhead. In particular, weak call-by-value beta-reduction can be simulated by an orthogonal constructor term rewrite system in the same number of reduction steps. Conversely, each reduction in an orthogonal term rewrite system can be simulated by a constant number of weak call-by-value beta-reduction steps. This is relevant to implicit computational complexity, because the number of beta steps to normal form is polynomially related to the actual cost (that is, as performed on a Turing machine) of normalization, under weak call-by-value reduction. Orthogonal constructor term rewrite systems and lambda-calculus are thus both polynomially related to Turing machines, taking as notion of cost their natural parameters.
机译:我们证明了正交构造函数项重写系统和弱(即在lambda抽象的范围内不允许减少)的lambda演算可以按线性开销相互模拟。特别地,可以通过正交构造函数项重写系统以相同数量的减少步骤来模拟弱按值调用beta减少。相反,正交项重写系统中的每个减少都可以通过恒定数量的弱按值调用beta减少步骤来模拟。这与隐式的计算复杂性有关,因为在弱按值调用减少的情况下,正常形式的beta步数与标准化的实际成本(即在图灵机上执行)在多项式上相关。因此,正交构造函数项重写系统和lambda微积分都与Turing机在多项式上相关,并以成本为代价来考虑其自然参数。

著录项

  • 来源
  • 会议地点 Rhodes(GR);Rhodes(GR);Rhodes(GR);Rhodes(GR);Rhodes(GR);Rhodes(GR);Rhodes(GR);Rhodes(GR);Rhodes(GR);Rhodes(GR)
  • 作者

    Ugo Dal Lago; Simone Martini;

  • 作者单位

    Dipartimento di Scienze dell'Informazione, Universita di Bologna Mura Anteo Zamboni 7, 40127 Bologna, Italy;

    Dipartimento di Scienze dell'Informazione, Universita di Bologna Mura Anteo Zamboni 7, 40127 Bologna, Italy;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 程序设计、软件工程;
  • 关键词

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号