Polynomial Time Uniform Word Problems
Copyright policy )Polynomial Time Uniform Word Problems
AbstractWe 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.
Partial algebras, Analysis of algorithms and problem complexity, universal theory of lattices, uniform word problem, quasivariety, Free lattices, projective lattices, word problems, polynomial time decidability, weak embedding closure, Word problems (aspects of algebraic structures), finite axiomatizability, Word problems, etc. in computability and recursion theory, universal Horn class, universal closure, Quasivarieties
Partial algebras, Analysis of algorithms and problem complexity, universal theory of lattices, uniform word problem, quasivariety, Free lattices, projective lattices, word problems, polynomial time decidability, weak embedding closure, Word problems (aspects of algebraic structures), finite axiomatizability, Word problems, etc. in computability and recursion theory, universal Horn class, universal closure, Quasivarieties
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).20 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!