ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS Journal Articles

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.

authors

• FREESE, RALPH
• Valeriote, Matthew Anthony

status

• published 

publication date

• February 2009

has subject area

• 0101 Pure Mathematics (FoR)
• 0103 Numerical and Computational Mathematics (FoR)
• 0802 Computation Theory and Mathematics (FoR)
• General Mathematics (Science Metrix)

published in

• International Journal of Algebra and Computation  Journal

keywords

• ALGEBRAS
• CONGRUENCE MODULARITY
• LATTICES
• LOCALLY FINITE VARIETIES
• Maltsev condition
• Mathematics
• Physical Sciences
• Science & Technology
• computational complexity
• congruence distributive
• congruence modular
• idempotent algebra
• tame congruence theory

Digital Object Identifier (DOI)

• 10.1142/s0218196709004956

start page

• 41

end page

• 77

volume

• 19

issue

• 01