The Undecidability of the Word Problem for Distributive Residuated Lattices
The Undecidability of the Word Problem for Distributive Residuated Lattices
复制标题
分配剩余格字问题的不可判定性
DOI：
10.1007/978-1-4757-3627-4_12
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Nikolaos Galatos
中科院分区：
文献类型：
--
作者：
Nikolaos Galatos
设 A==(XI R) 是变体 V 中的有限呈现代数。如果没有算法可以决定绝对自由项代数 Tv (X) 中的任意两个给定单词是否表示 A 的同一个元素，则称代数 A 存在不可判定的字问题。如果 V 包含这样的代数 A，我们说它存在不可判定的字问题。 l-群是不可判定的。）本文的主要结果是字问题对于一系列变量的不可判定性，包括分配剩余格的多样性和交换分配格的多样性。子范围（包括后一种类型）的结果是 Urquhart 定理的结果 [7]。这里的证明基于各种半群的字问题的不可判定性，并利用了冯·诺依曼引入的 n 框架的概念。证明中的方法扩展了 Lipshitz 和 Urquhart 分别为各种模格和分配格序半群建立不可判定性结果的思想。
Let A==(XI R) be a finitely presented algebra in a variety V. The algebra A is said to have an undecidable word problem if there is no algorithm that decides whether or not any two given words in the absolutely free term algebra Tv (X) represent the same element of A. If V contains such an algebra A, we say that it has an undecidable word problem.(It is weIl known that the word problem for the varieties of semigroups, groups and l-groups is undecidable.)The main result of this paper is the undecidability of the word problem for a range of varieties including the variety of distributive residuated lattices and the variety of commutative distributive ones. The result for a subrange, including the latter variety, is a consequence of a theorem by Urquhart [7]. The proof here is based on the undecidability of the word problem for the variety of semigroups and makes use of the concept of an n-frame, introduced by von Neumann. The methods in the proof extend ideas used by Lipshitz and Urquhart to establish undecidability results for the varieties of modular lattices and distributive latticeordered semigroups, respectively.