Poludistributivnost, Problem zadovoljenja uslova i jaki Maljcevljevi uslovi

Abstract

<p>U ovoj tezi opisujemo linearne, idempotentne, jake Maljcevljeve uslove za kongruencijsku ^-poludistributivnost u lokalno konačnim varijetetima. U [40] je predstavljen jedan takav jak Maljcevljev uslov i tehnika koju su autori koristili je uop&scaron;tenje jednog od glavnih rezultata iz [46]. Glavna razlika je u tome &scaron;to jednostavna primjena Dirihleovog principa u [46] postaje dosta komplikovaniji argument Remzijevskog tipa u [40]. Mi ovdje dodatno uop&scaron;tavamo taj argument i prezentujemo dokaz pomenute karakterizacije. Svi ovi radovi koriste snažan rezultat [4] L. Barta o rje&scaron;ivosti Problema zadovoljenja uslova metodama provjere lokalne konzistencije uslova, pa je treća glava teze posvećena detaljnoj prezentaciji tog rada. Takođe, dokazujemo da neki jak Maljcevljev uslov karakteri&scaron;e kongruencijsku ^-poludistributivnost u lokalno konačnim varijetetima ako i samo ako je realizovan u određenoj četvoroelementnoj algebri. Na kraju, bavimo se i problemom pronalaženja optimalnog jakog Maljcevljevog uslova koji karakteri&scaron;e egzistenciju Tejlorovog terma u op&scaron;tem slučaju. U [53] M. Ol&scaron;ak predstavio je iznenađujući rezultat da je egzistencija Tejlorovog terma jako Maljcevljevo svojstvo. Term iz prvobitne verzije [53] ima arnost 12, dok mi ovdje prezentujemo dokaz da se arnost može redukovati na 9.</p>

<p>In this thesis we describe linear, idempotent, strong Mal&rsquo;cev conditions for congruence ^-semidistributivity in locally finite varieties. In [40] authors presented one such Mal&rsquo;cev condition and technique they used is generalization of one result from [46]. Main difference is that simple application of Pigeonhole prinicple from [46] becomes much more complicated Ramsey style argument in [40]. Here we dditionaly generalize that argument and we present the proof of above mentioned characterization. All these papers use deep result [4] by L. Barto on solvability of Constraint Satisfaction Problem by local consistency checking methods, so third chapter of this thesis is dedicated to detailed presentation of [4]. Also, we prove that some strong Mal&rsquo;cev condition characterizes congruence ^-semidistributivity in locally finite varieties if and only if it is realized in certain four element algebra. Finally, we work on the problem of finding optimal strong Mal&rsquo;cev condition for existence of Taylor term in general case. In [53] M. Olsak presented suprising result that exisstence of Taylor term is strong Malcev property. The term from first version of [53] has arity 12,<br />but here we prove that arity can be reduced to 9.</p>