Premium
Polynomial Time Uniform Word Problems
Author(s) -
Burris Stanley
Publication year - 1995
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19950410204
Subject(s) - mathematics , polynomial , word (group theory) , closure (psychology) , word problem (mathematics education) , embedding , alternating polynomial , combinatorics , class (philosophy) , time complexity , congruence (geometry) , discrete mathematics , pure mathematics , matrix polynomial , arithmetic , mathematical analysis , computer science , geometry , artificial intelligence , economics , market economy
We have two polynomial time results for the uniform word problem for a quasivariety Q : (a) The uniform word problem for Q can be solved in polynomial time iff one can find a certain congruence on finite partial algebras in polynomial time. (b) Let Q * be the relational class determined by Q . If any universal Horn class between the universal closure S ( Q *) and the weak embedding closure S̄ ( Q *) of Q * is finitely axiomatizable then the uniform word problem for Q is 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 partial V algebras.