Strong sequentiality of left-linear overlapping term rewriting systems
Strong sequentiality of left-linear overlapping term rewriting systems
复制标题
左线性重叠术语重写系统的强顺序性
DOI：
10.1109/lics.1992.185540
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
Y. Toyama
中科院分区：
文献类型：
--
作者：
Y. Toyama
G. Huet和J.J.Levy（INRIA Rep.359，1979）表明，对于每个强序列正交（即，左线性和非重叠）项重写系统，索引约简策略是规范化的。他们的结果被扩展到重叠项重写系统。证明了强序列左线性项重写系统的索引约简是正规化的，在这类系统中，每个临界对都可以用根平衡约简连接。这类系统包括所有弱正交左正规系统，其最左最外归约策略是正规化的。<<ETX>>
G. Huet and J.J. Levy (INRIA Rep. 359, 1979) showed that for every strongly sequential orthogonal (i.e., left-linear and non-overlapping) term rewriting system, index reduction strategy is normalizing. Their result is extended to overlapping term rewriting systems. It is shown that index reduction is normalizing for the class of strongly sequential left-linear term rewriting systems in which every critical pair can be joined with root balanced reductions. This class includes all weakly orthogonal left-normal systems, for which a leftmost-outermost reduction strategy is normalizing.<<ETX>>