DECIDING SOME MALTSEV CONDITIONS IN FINITE IDEMPOTENT ALGEBRAS Journal Articles

abstract

• AbstractIn this paper we investigate the computational complexity of deciding if the variety generated by a given finite idempotent algebra satisfies a special type of Maltsev condition that can be specified using a certain kind of finite labelled path. This class of Maltsev conditions includes several well known conditions, such as congruence permutability and having a sequence of n Jónsson terms, for some given n. We show that for such “path defined” Maltsev conditions, the decision problem is polynomial-time solvable.

authors

• KAZDA, ALEXANDR
• Valeriote, Matthew Anthony

status

• published 

publication date

• June 2020

has subject area

• 0101 Pure Mathematics (FoR)
• 0802 Computation Theory and Mathematics (FoR)
• 2203 Philosophy (FoR)
• General Mathematics (Science Metrix)

published in

• Journal of Symbolic Logic (JSL)  Journal

keywords

• CONGRUENCE LATTICES
• Logic
• Maltsev condition
• Mathematics
• Physical Sciences
• Science & Technology
• Science & Technology - Other Topics
• computational complexity
• universal algebra

Digital Object Identifier (DOI)

• 10.1017/jsl.2019.73

start page

• 539

end page

• 562

volume

• 85

issue

• 2