Polynomial Time Uniform Word Problems
- 1 January 1995
- journal article
- research article
- Published by Wiley in Mathematical Logic Quarterly
- Vol. 41 (2) , 173-182
- https://doi.org/10.1002/malq.19950410204
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.Keywords
This publication has 10 references indexed in Scilit:
- The Equivalence Problem for Finite RingsJournal of Symbolic Computation, 1993
- Finitely Presented Lattices: Canonical Forms and the Covering RelationTransactions of the American Mathematical Society, 1989
- Finitely presented lattices: canonical forms and the covering relationTransactions of the American Mathematical Society, 1989
- The word and generator problems for latticesInformation and Computation, 1988
- On the Computational Complexity of Algebra on LatticesSIAM Journal on Computing, 1987
- A Model Theoretic Oriented Approach to Partial AlgebrasPublished by Walter de Gruyter GmbH ,1986
- The complexity of the word problems for commutative semigroups and polynomial idealsAdvances in Mathematics, 1982
- Complexity of finitely presented algebrasPublished by Association for Computing Machinery (ACM) ,1977
- Embeddability and the Word ProblemJournal of the London Mathematical Society, 1953
- The decision problem for some classes of sentences without quantifiersThe Journal of Symbolic Logic, 1943