Decidability of absorption in relational structures of bounded width |
| |
Authors: | Jakub Bulín |
| |
Institution: | 1. Department of Algebra, Faculty of Mathematics and Physics, Charles University in Prague, Prague 1, Czech Republic
|
| |
Abstract: | 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 \({\mathbb{A}}\) and a subset \({B \subseteq A}\) , is it decidable whether B is an absorbing subuniverse? We provide an affirmative answer in the case when \({\mathbb{A}}\) has bounded width (i.e., the algebra of polymorphisms of \({\mathbb{A}}\) generates a congruence meet semidistributive variety). As a by-product, we confirm that in this case the notion of Jónsson absorption coincides with the usual absorption. We also show that several open questions about absorption in relational structures can be reduced to digraphs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|