Decidability for left-linear growing term rewriting systems
Decidability for left-linear growing term rewriting systems
复制标题
DOI：
10.1006/inco.2002.3157
复制
发表时间：
2002-11-01
影响因子：
1
通讯作者：
Toyama, Y
中科院分区：
文献类型：
--
作者：
Nagaya, T;Toyama, Y
如果每个变量都发生在左侧和重写规则的右侧，则称为术语重写系统，如果在左侧或左侧发生一个。 Jacquemard表明，线性（即左右线性）生长期限重写系统的可达到性和顺序是可决定的。在本文中，我们表明，雅克马德的结果可以扩展到左线增长的重写系统，这些系统可能具有右非线性重写规则。这意味着可以决定某些右键术语重写系统的可及性和可加工性，这改善了Oyamaguchi的右地面术语重写系统的结果。我们的结果扩展了具有符合规范策略的可决定性呼叫的左线性术语重写系统的类别。此外，我们证明终止属性对于几乎正交增长的术语重写系统是可决定的。 （C）2002 Elsevier Science（美国）。
A term rewriting system is called growing if each variable occurring on both the left-hand side and the right-hand side of a rewrite rule occurs at depth zero or one in the left-hand side. Jacquemard showed that the reachability and the sequentiality of linear (i.e., left-right-linear) growing term rewriting systems are decidable. In this paper we show that Jacquemard's result can be extended to left-linear growing rewriting systems that may have right-nonlinear rewrite rules. This implies that the reachability and the joinability of some class of right-linear term rewriting systems are decidable, which improves the results for right-ground term rewriting systems by Oyamaguchi. Our result extends the class of left-linear term rewriting systems having a decidable call-by-need normalizing strategy. Moreover, we prove that the termination property is decidable for almost orthogonal growing term rewriting Systems. (C) 2002 Elsevier Science (USA).