|
|
Generalizing CSP-related results to infinite algebras
Olšák, Miroslav ; Barto, Libor (advisor) ; Zhuk, Dmitrii (referee) ; Pinsker, Michael (referee)
The recent research on constraint satisfaction problems (CSPs) on fixed finite templates provided useful tools for computational complexity and universal algebra. However, the research mainly focused on finite relational structures, and consequently, finite algebras. We pursue a generalization of these tools and results into the domain of infinite algebras. In particular, we show that despite the fact that the Maltsev condition s(r, a, r, e) = s(a, r, e, a) does not characterize Taylor algebras (i.e., algebras that satisfy a nontrivial idem- potent Maltsev condition) in general, as it does in the finite case, there is another strong Maltsev condition characterizing Taylor algebras, and s(r, a, r, e) = s(a, r, e, a) characterizes another interesting broad class of algebras. We also provide a (weak) Maltsev condition for SD(∧) algebras (i.e., algebras that satisfy an idem- potent Maltsev condition not satisfiable in a module). Beyond Maltsev conditions, we study loop lemmata and, in particular, reprove a well known finite loop lemma by two different general (infinite) approaches.
|
guest ::
