𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Polynomial Time Uniform Word Problems

✍ Scribed by Stanley Burris

Publisher
John Wiley and Sons
Year
1995
Tongue
English
Weight
587 KB
Volume
41
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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.

πŸ“œ SIMILAR VOLUMES

Polynomial time approximation schemes fo
Polynomial time approximation schemes for class-constrained packing problems
✍ Hadas Shachnai; Tami Tamir πŸ“‚ Article πŸ“… 2001 πŸ› Springer US 🌐 English βš– 207 KB

We consider variants of the classic bin packing and multiple knapsack problems, in which sets of items of di erent classes (colours) need to be placed in bins; the items may have di erent sizes and values. Each bin has a limited capacity, and a bound on the number of distinct classes of items it can