Gyenge többségi függvények = Weak near-unanimity operations

Maróti, Miklós (2012) Gyenge többségi függvények = Weak near-unanimity operations. Project Report. OTKA.

Preview

PDF 75475_ZJ1.pdf Download (89kB) | Preview

Abstract

Az OTKA pályázatom benyújtása (2008. február 11) óta 8 cikkem jelent nemzetközi folyóiratokban, de ezek közül csak kettő cikk született a kutatási programban megadott témában a beszámolási időszak alatt, ezért a többi 6 megjelent cikket nem tüntettem fel a jelentésben. Ezen cikkeken kívül a kutatási tervnek megfelelően további 3 kézirat van publikálásra benyújtva, illetve egy kézirat született, amely nincsen még benyújtva. A kutatási időszakban összesen hat nemzetközi konferencián adtam elő, ezek közül négyen meghívott előadóként. Az [1] cikkben egy irányított fákból álló speciális gráfosztályra, az úgynevezett speciális triádokra bizonyítjuk a homomorfizmus problémára vonatkozó dichotómia sejtés. A [2] cikkben algoritmust adunk arra, hogy láncok direkt szorzatában az azonos elemszámú ideálok melyikében maximális az elemek magasságának összege. A [3] kéziratban a korlátos szélességű és kevés részhatvánnyal rendelkező algebrákra vonatkozó kényszerkielégíthetőségi problémát megoldó algoritmusokat ötvöztem. A [4] kéziratban bebizonyítottuk a Valeriote sejtést reflexív irányított gráfokra. Az [5] kéziratban a Valeriote sejtés több ekvivalens megfogalmazását adtuk meg. A [6] kéziratban a CSP probléma egy teljesen új redukcióját vezettük be, amely segítségével újabb algebraosztályokra bizonyítható a dichotómia sejtés. | Since the submission of my OTKA grant proposal (2008/08/11) I had eight articles appeared in international journals, but only two of them were on a topic listed in the project proposal. Therefore, I did not mention the other 6 in this report. Beside these articles I have 3 submitted manuscripts and one manuscript not jet submitted. During the three years of this research grant I have given 6 talks on international conferences, four of them were invited plenary talks. In [1] we have proved the constraint satisfaction dichotomy conjecture for a special class of directed trees, for the class of special triads. In [2] we give an algorithm to determine the order ideal of a direct product of chains in which the number of elements equals a fixed integer and the sum of heights of elements is maximal. In [3] I have combined the algorithms solving the constraint satisfaction problem for bounded width algebras and for algebras of few subpowers. In [4] we have proved the Valeriote conjecture for reflexive directed graphs. In [5] we have given equivalent formulations of the Valeriote conjecture. in [6] we have introduced a completely new reduction of CSP problems that allowed the proof of the dichotomy conjecture for various new classes of algebras.

Actions (login required)

Edit Item