Algebra universalis Algebra and Number Theory
On the uniform word problem for lattices
Abstract
Abstract An algorithm that decides the uniform word problem for lattices is given and shown to have $$O(n^3)$$ O ( n 3 ) running-time, which also gives an $$O(n^3)$$ O ( n 3 ) algorithm for the quasi-equational theory of lattices. This result continues a long sequence of algorithms for this problem, starting with Skolem in 1920. The algorithm makes use of Cosmadakis’ algorithm for the uniform word problem and Freese’s algorithm for the word problem for free lattices.