Polynomial Time Uniform Word Problems
Stanley N. Burris · Mathematical logic quarterly · 1995
Abstract We have two polynomial time results for the uniform word problem for a quasivarietyQ: (a) The uniform word problem forQcan be solved in polynomial time iff one can find a certain congruence on finite partial algebras in polynomial time. (b) LetQ* be the relational class determined byQ. If any universal Horn class between the universal closureS(Q*) and the weak embedding closureS̄(Q*) ofQ* is finitely axiomatizable then the uniform word problem forQis solvable in polynomial time. This covers Skolem's 1920 solution to the uniform word problem for lattices and Evans' 1953 applications of the weak embeddability property for finite partialValgebras.