Journal article
ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
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 …
Authors
FREESE R; VALERIOTE MA
Journal
International Journal of Algebra and Computation, Vol. 19, No. 01, pp. 41–77
Publisher
World Scientific Publishing
Publication Date
2 2009
DOI
10.1142/s0218196709004956
ISSN
0218-1967