Completeness results for basic narrowing
Completeness results for basic narrowing
复制标题
基本缩小的完整性结果
DOI：
10.1007/bf01190830
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
E. Hamoen
中科院分区：
文献类型：
--
作者：
A. Middeldorp;E. Hamoen
在本文中，我们分析的基本窄的完整性结果。我们表明，基本的缩小是不完整的正规化解决方案的方程理论所定义的合流项重写系统，相反，已被obtured。通过对重写规则施加语法限制，我们恢复了完整性。我们反驳了Hölldobler的结果，该结果表明，在重写规则的条件中没有额外变量的条件项重写系统的完整性（即合流和终止）基本条件缩小。在本文的最后一部分中，我们扩展了Giovannetti和Moiso的完备性结果水平合流和终止条件系统与额外的变量的条件系统，也可能有额外的变量在右手边的规则。
In this paper we analyze completeness results for basic narrowing. We show that basic narrowing is not complete with respect to normalizable solutions for equational theories defined by confluent term rewriting systems, contrary to what has been conjectured. By imposing syntactic restrictions on the rewrite rules we recover completeness. We refute a result of Hölldobler which states the completeness of basic conditional narrowing for complete (i.e. confluent and terminating) conditional term rewriting systems without extra variables in the conditions of the rewrite rules. In the last part of the paper we extend the completeness results of Giovannetti and Moiso for level-confluent and terminating conditional systems with extra variables in the conditions to systems that may also have extra variables in the right-hand sides of the rules.