Back to Search
Start Over
ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS.
- Source :
-
International Journal of Algebra & Computation . Feb2009, Vol. 19 Issue 1, p41-77. 37p. 3 Diagrams. - Publication Year :
- 2009
-
Abstract
- This paper studies the complexity of determining if a finite algebra generates a variety that satisfies various Maltsev conditions, such as congruence distributivity or modularity. For idempotent algebras we show that there are polynomial time algorithms to test for these conditions but that in general these problems are EXPTIME complete. In addition, we provide sharp bounds in terms of the size of two-generated free algebras on the number of terms needed to witness various Maltsev conditions, such as congruence distributivity. [ABSTRACT FROM AUTHOR]
- Subjects :
- *ALGEBRA
*MATHEMATICS
*POLYNOMIALS
*ALGORITHMS
*FOUNDATIONS of arithmetic
Subjects
Details
- Language :
- English
- ISSN :
- 02181967
- Volume :
- 19
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- International Journal of Algebra & Computation
- Publication Type :
- Academic Journal
- Accession number :
- 36625701
- Full Text :
- https://doi.org/10.1142/S0218196709004956