Computers and universal algebra: Some directions (Q1902542): Difference between revisions
From MaRDI portal
Latest revision as of 17:19, 23 May 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Computers and universal algebra: Some directions |
scientific article |
Statements
Computers and universal algebra: Some directions (English)
0 references
10 April 1996
0 references
The paper contains an overview of universal algebra problems considered from the point of view of computational complexity. The author discusses all important results or open problems on polynomial time and non- polynomial time algorithms for finding principal congruences, subdirectly irreducible members, subdirect decompositions, for determining whether a finite algebra generates a discriminator variety etc. Especially, the author discusses these problems for free spectra, the isomorphism problem, the equivalence problem, and for unification and term rewriting systems.
0 references
survey
0 references
NP-completeness
0 references
polynomial time algorithm
0 references
computational complexity
0 references
principal congruence
0 references
subdirectly irreducible members
0 references
subdirect decompositions
0 references
discriminator variety
0 references
free spectra
0 references
isomorphism problem
0 references
equivalence problem
0 references
unification
0 references
term rewriting systems
0 references
