×

zbMATH — the first resource for mathematics

The undecidability of the word problem for distributive residuated lattices. (English) Zbl 1073.06007
MartĂ­nez, Jorge (ed.), Ordered algebraic structures. Proceedings of the conference on lattice-ordered groups and \(f\)-rings held at the University of Florida, Gainesville, FL, USA, February 28–March 3, 2001. Dordrecht: Kluwer Academic Publishers (ISBN 1-4020-0752-3). Developments in Mathematics 7, 231-243 (2002).
Summary: Let \({\mathbf A} = \langle X\mid R\rangle\) be a finitely presented algebra in a variety \(\mathcal 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 \(T_\nu(X)\) represent the same element of \(\mathbf A\). If \(V\) contains such an algebra \(\mathbf A\), we say that it has an undecidable word problem. (It is well 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 A. Urquhart [J. Symb. Logic 49, No. 4, 1059–1073 (1984; Zbl 0581.03011)]. 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 Lipschitz and Urquhart to establish undecidability results for the varieties of modular lattices and distributive lattice-ordered semigroups, respectively.
For the entire collection see [Zbl 1068.06001].

MSC:
06F05 Ordered semigroups and monoids
03D35 Undecidability and degrees of sets of sentences
03D40 Word problems, etc. in computability and recursion theory
06B25 Free lattices, projective lattices, word problems
PDF BibTeX XML Cite