Majority functions on structures with finite duality
Majority functions on structures with finite duality
复制标题
有限对偶结构上的多数函数
DOI：
10.1016/j.ejc.2007.11.007
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Claude Tardif
中科院分区：
文献类型：
--
作者：
C. Loten;Claude Tardif
多数函数是一个三元近一致函数。Dalmau和Krokhin最近表明，关系结构上多数多态性的存在反映在相应约束满足问题的复杂性上，这意味着问题具有“有界路径对偶性”。这里我们将注意力限制在有限对偶的核心结构上。我们完全把其中那些承认多数多态性的人描述为那些最小障碍是“毛毛虫”的人。
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”.