Deciding absorption in relational structures

DOI10.1007/S00012-017-0440-5zbMATH Open1412.08004arXiv1601.06450OpenAlexW2964062224MaRDI QIDQ2407970FDOQ2407970

Jakub Bulín, Libor Barto

Publication date: 9 October 2017

Published in: Algebra Universalis (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

near unanimitycongruence distributivityfinitely related algebraabsorbing subalgebra[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=J%EF%BF%BD%EF%BF%BDnsson+absorbing+subalgebra&go=Go J��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)

Cites Work

• Title not available (Why is that?)
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• Finitely Related Algebras In Congruence Distributive Varieties Have Near Unanimity Terms
• Closed systems of functions and predicates
• Title not available (Why is that?)
• Title not available (Why is that?)
• The existence of a near-unanimity function is decidable
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• Congruence Distributivity Implies Bounded Width
• Mal'tsev conditions, lack of absorption, and solvability.
• Near Unanimity Constraints Have Bounded Pathwidth Duality
• Finitely related algebras in congruence modular varieties have few subpowers
• Deciding absorption
• Decidability of absorption in relational structures of bounded width.

Cited In (1)

• 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)