# 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