Polynomial Time Uniform Word Problems | Zendy

Burris Stanley | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research