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

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
نویسندگان
, ,