Confluence and Termination of Simply Typed Term Rewriting Systems
Confluence and Termination of Simply Typed Term Rewriting Systems
复制标题
简单类型术语重写系统的汇合和终止
DOI：
10.1007/3-540-45127-7_25
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Toshiyuki Yamada
中科院分区：
文献类型：
--
作者：
Toshiyuki Yamada
我们建议简单地输入术语重写系统（STTRSS），该系统通过允许高阶功能扩展一阶重写。我们研究了一种简单的汇合方法，该方法采用了平行还原的钻石特性的表征。通过应用证明方法，我们获得了正交条件性STTRS的新汇合结果。我们还讨论了一种基于单调解释来证明终止STTRS的语义方法。
We propose simply typed term rewriting systems (STTRSs), which extend first-order rewriting by allowing higher-order functions. We study a simple proof method for confluence which employs a characterization of the diamond property of a parallel reduction. By an application of the proof method, we obtain a new confluence result for orthogonal conditional STTRSs. We also discuss a semantic method for proving termination of STTRSs based on monotone interpretation.