Deciding absorption in relational structures

DOI10.1007/S00012-017-0440-5MaRDI QIDQ2407970zbMATH OpenOpenAlexFDO

Authors Libor Barto, Jakub Bulín

Publication date 9 October 2017

Published in Algebra Universalis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.06450

zbMATH Keywords

near unanimitycongruence distributivityfinitely related algebraabsorbing subalgebraJónsson absorbing subalgebra

Mathematics Subject Classification ID

Structure theory of algebraic structures (08A05) Equational logic, Mal'tsev conditions (08B05) Congruence modularity, congruence distributivity (08B10) Applications of universal algebra in computer science (08A70)

Abstract: We prove that for finite, finitely related algebras the concepts of an absorbing subuniverse and a J'onsson absorbing subuniverse coincide. Consequently, it is decidable whether a given subset is an absorbing subuniverse of the polymorphism algebra of a given relational structure.

Recommendations

• Decidability of absorption in relational structures of bounded width.
• Relational structures and dependence spaces
• On a power of relational structures
• scientific article; zbMATH DE number 2209441
• scientific article; zbMATH DE number 3938547
• scientific article; zbMATH DE number 3978448
• scientific article; zbMATH DE number 6135973
• Relational decomposition through partial functional dependencies
• Relational decomposition

Cites work

• scientific article; zbMATH DE number 3751028 (Why is no real title available?)
• scientific article; zbMATH DE number 3336786 (Why is no real title available?)
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• Closed systems of functions and predicates
• Congruence distributivity implies bounded width
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Decidability of absorption in relational structures of bounded width.
• Deciding absorption
• Finitely related algebras in congruence distributive varieties have near unanimity terms
• Finitely related algebras in congruence modular varieties have few subpowers
• Mal'tsev conditions, lack of absorption, and solvability.
• Near unanimity constraints have bounded pathwidth duality
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The existence of a near-unanimity function is decidable
• Universal algebra. Fundamentals and selected topics

Cited in

(2)

• Deciding absorption
• Not all nilpotent monoids are finitely related

This page was built for publication: Deciding absorption in relational structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2407970)