کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4654387 | 1632829 | 2008 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Majority functions on structures with finite duality
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A majority function is a ternary near-unanimity function. Dalmau and Krokhin have recently shown that the existence of a majority polymorphism on a relational structure is reflected in the complexity of the corresponding constraint satisfaction problem, implying that the problem has “bounded path duality”. Here we restrict our attention to core structures with finite duality. We completely characterise those among them which admit majority polymorphisms as those whose minimal obstructions are “caterpillars”.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 29, Issue 4, May 2008, Pages 979–986
Journal: European Journal of Combinatorics - Volume 29, Issue 4, May 2008, Pages 979–986
نویسندگان
Cynthia Loten, Claude Tardif,