Narrowing-based simulation of term rewriting systems with extra variables
Narrowing-based simulation of term rewriting systems with extra variables
复制标题
具有额外变量的术语重写系统的基于窄化的模拟
DOI：
10.1016/s1571-0661(04)80693-5
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Toshiki Sakabe
中科院分区：
文献类型：
--
作者：
Naoki Nishida;Masahiko Sakai;Toshiki Sakabe
通过允许在重写规则中包含额外变量而扩展的术语重写系统 (TRS) 称为 EV-TRS。它们的性质很恶劣，因为按照它们的规则使用额外变量进行的每一步归约都是无限分支的，并且它们不会终止。为了解决这些问题，本文表明窄化可以将 EV-TRS 的缩减序列模拟为从地面项开始的窄化序列。我们证明了地面缩小序列对于缩减序列的合理性。我们证明了右线性系统情况的完整性，以及在归约序列中归约的任何 redex 都不是通过额外变量引入的情况的完整性。此外，我们给出了一种证明模拟终止的方法，将证明TRS终止的依赖对方法扩展到从地面项开始缩小EV-TRS的方法。我们证明该方法对于右线性或构造函数系统很有用。
Term rewriting systems (TRSs) extended by allowing to contain extra variables in their rewrite rules are called EV-TRSs. They are ill-natured since every one-step reduction by their rules with extra variables is infinitely branching and they are not terminating. To solve these problems, this paper shows that narrowing can simulate reduction sequences of EV-TRSs as narrowing sequences starting from ground terms. We prove the soundness of ground narrowing sequences for the reduction sequences. We prove the completeness for the case of right-linear systems, and also for the case that any redex reduced in the reduction sequence is not introduced by means of extra variables. Moreover, we give a method to prove the termination of the simulation, extending the dependency pair method to prove termination of TRSs, into that of narrowing on EV-TRSs starting from ground terms. We show that the method is useful for right-linear or constructor systems.
具有复数性
DOI：
--
发表时间：
2021
期刊：
研究紀要 : 神戸大学附属中等論集
影响因子：
--
作者：
Keiko Kaga ; Mayuko Suzuki ; Megumi Okutani ; Kumiko Ohmoto;虫明眞砂子;中川雅道;虫明眞砂子;奥谷めぐみ・鈴木真由子・加賀恵子・大本久美子;虫明眞砂子（高橋昌子）;奥谷めぐみ・鈴木真由子・加賀恵子・大本久美子;小路口真理美;小路口真理美;鈴木真由子・大本久美子・加賀恵子・奥谷めぐみ;大本久美子・鈴木真由子;小路口聡;大本久美子・鈴木真由子;奥谷めぐみ;中川雅道;近藤晶，三寺潤，笠井利浩;近藤晶，笠井利浩，三寺潤;近藤晶，笠井利浩，三寺潤;中川雅道
通讯作者：
中川雅道