Finite complete rewriting systems and the complexity of the word problem
Finite complete rewriting systems and the complexity of the word problem
复制标题
有限完全重写系统和应用题的复杂性
DOI：
10.1007/bf00271645
复制
发表时间：
1984
期刊：
影响因子：
0.6
通讯作者：
F. Otto
中科院分区：
文献类型：
--
作者：
G. Bauer;F. Otto
摘要众所周知，有限完备重写系统的字问题是可判定的。在这里，它表明，在一般情况下，这一结果不能得到改善。这是通过证明，每个足够丰富的复杂性类可以实现的有限的完整的重写系统的字问题。此外，在有限完全重写系统的字问题的复杂性和由该重写系统生成的链的长度的最小上界的复杂性之间存在差距，并且该差距可以变得任意大。因此，这些链的长度并不能提供任何关于单词问题复杂性的信息。最后，它表明，允许一个有限的完全重写系统的属性是不是有限幺半群表示的不变量。
SummaryIt is well known that the word problem for a finite complete rewriting system is decidable. Here it is shown that in general this result cannot be improved. This is done by proving that each sufficiently rich complexity class can be realized by the word problem for a finite complete rewriting system. Further, there is a gap between the complexity of the word problem for a finite complete rewriting system and the complexity of the least upper bound for the lengths of the chains generated by this rewriting system, and this gap can get arbitrarily large. Thus, the lengths of these chains do not give any information about the complexity of the word problem. Finally, it is shown that the property of allowing a finite complete rewriting system is not an invariant of finite monoid presentations.