Decidability of absorption in relation structures of bounded width

Abstrakt

The theory of absorption has proven to be a very useful tool in the algebraic approach to the constraint satisfaction problem and structure of finite algebras in general. This paper studies absorption in relational structures of bounded width.

In this case the notions of absorbing and Jonsson absorbing subuniverse coincide. As a consequence, it is decidable whether a given subset is an absorbing subuniverse.

Klíčová slova

• Decidability
• absorption
• relation
• structures
• bounded
• width