Decidability of absorption in relational structures of bounded width

作者：Bulin Jakub^*

来源：ALGEBRA UNIVERSALIS, 2014, 72(1): 15-28.

DOI：10.1007/s00012-014-0283-2

• absorbing subuniverse
• near unanimity operation
• Jonsson operations
• congruence meet semidistributivity
• finitely related algebra
• constraint satisfaction problem
• bounded width

The absorption theory of Barto and Kozik has proven to be a very useful tool in the algebraic approach to the Constraint Satisfaction Problem and the structure of finite algebras in general. We address the following problem: Given a finite relational structure A and a subset B subset of A, is it decidable whether B is an absorbing subuniverse? We provide an affirmative answer in the case when A has bounded width (i.e., the algebra of polymorphisms of A generates a congruence meet semidistributive variety). As a by-product, we confirm that in this case the notion of Jonsson absorption coincides with the usual absorption. We also show that several open questions about absorption in relational structures can be reduced to digraphs.

• 出版日期2014-8