Study on Rewriting Theory for Analysis, Verification and Efficient Execution of Functional Programs

函数式程序分析、验证和高效执行的重写理论研究

• 批准号: 15500007
• 负责人: SAKAI Masahiko
• 金额: $ 1.6万
• 依托单位: Nagoya University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2003
• 资助国家: 日本
• 起止时间: 2003 至 2005
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-15500007/
• 关键词: term rewriting system; functional language; normalizing strategy; termination proof; implicit induction; outer-most strategy

This research is toward removing gaps that prevent from applying results of term rewriting systems (TRS for short) to fuctional languages. The following results were obtained ;(1) The previously proposed dependency pair method for proving termination of higher-order rewrite systems cannot be applied for ones containing nested variable in a right-hand side and containing copy rules. We succeeded to remove the strong restriction from it for proving termination of simple-typed rewriting systems.(2) We showed that the needed redexes with respect to strong sequential or NV approximation are decidable by using tree-automata technique and the de Bruijn notations.(3) It appeared that theorems provable by implicit induction in higher-order rewrite systems are the subclass of the inductive theorems. The case happens that some inductive theorems are judged to be not inductive. We gave a condition to prevent this situation.(4) We gave a condition that guarantees the outer-most reduction strategy to be complete for overlapping TRSs, and showed a transformation of TRSs that produce TRSs that satisfy the condition.(5) We developed a transformation of TRSs whose outputs define the inverse computation of the input constructor TRSs. In the computation, innermost narrowing is effective for obtaining all results in case of linear TRSs with extra variables.

这项研究是为了消除差距，以防止将术语重写系统（简称为TR）应用于授权语言。获得以下结果;（1）先前提出的用于证明终止高阶重写系统的依赖对方法不能应用于右侧包含嵌套变量并包含复制规则的系统。我们成功地从中取出了强大的限制，以证明简单类型的重写系统的终止。（2）我们表明，通过使用tree-automata技术和de bruijn notions进行了强有的顺序或NV近似相对于强的顺序或NV近似。（3）看来，Intems在较高的订单中似乎是由式的归纳来构成的。据此认为某些归纳定理被认为不是归纳的。我们提供了一种防止这种情况的条件。（4）我们提供了一种条件，该条件保证了重叠TRS的最外层减少策略，并显示出产生满足条件的TRS的转换。（5）我们开发了TRSS的转换，其输出定义了输入构建体TRS的反向计算。在计算中，最终狭窄对于在具有额外变量的线性TRS的情况下可获得所有结果。

项目成果

Primitive Indeuctive Theorems Bridge Implicit Induction Methods and Inductive Theorems in Higher-Order Rewriting

原归纳定理将隐式归纳法和高阶重写中的归纳定理联系起来

• 发表时间: 2005
• 期刊: IEICE Trans. on Information and Systems E88-D・12
• 作者: K.Kusakari;M.Sakai;T.Sakabe
• 通讯作者: T.Sakabe

M.Sakai, K.Okamoto: "Innermost Reductions Find All Normal Forms on Right-Linear Terminating Overlay TRSs"3rd Int'l Workshop on Reduction Strategies in Rewriting and Programming. WRS'03. 198-211 (2003)

M.Sakai、K.Okamoto：“最内层约简在右线性终止覆盖 TRS 上查找所有范式”第三届重写和编程中约简策略国际研讨会。

Proving Sufficient Completeness of Functional Programs based on Recursive Structure Analysis and Strong Computability

基于递归结构分析和强可计算性证明函数程序的充分完备性

• 发表时间: 2005
• 期刊: Information Technology Letters(in Japanese) Vol.LA-001
• 作者: Keita Sakurai;Keiichirou Kusakari;Naoki Nishida;Masahiko Sakai;Toshiki Sakabe
• 通讯作者: Toshiki Sakabe

A Computation Model of Term Rewriting Systems with Extra Variables

带有额外变量的术语重写系统的计算模型

• 发表时间: 2003
• 期刊: Computer Software (in Japanese) Vol.20, No.5
• 作者: Naoki Nishida;Masahiko Sakai;Toshiki Sakabe
• 通讯作者: Toshiki Sakabe

N.Nishida, M.Sakai, T.Sakabe: "Narrowing-based Simulation of Term Rewriting Systems with Extra Variables and its Termination Proof"12th Int'l Workshop on Functional and (Constraint) Logic Programming. WFLP'03. 198-211 (2003)

N.Nishida、M.Sakai、T.Sakabe：“带有额外变量的术语重写系统的基于窄化的模拟及其终止证明”第十二届函数和（约束）逻辑编程国际研讨会。