Deciding absorption

DOI10.1142/S0218196716500430MaRDI QIDQ2821827zbMATH OpenFDO

Authors Libor Barto, Alexandr Kazda

Publication date 23 September 2016

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

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

zbMATH Keywords

absorbing subalgebracongruence distributivitycube termcube term blockerfew subpowersJónsson absorbing subalgebraJónsson termsnear unanimity term

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Congruence modularity, congruence distributivity (08B10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: We characterize absorption in finite idempotent algebras by means of J'onsson absorption and cube term blockers. As an application we show that it is decidable whether a given subset is an absorbing subuniverse of an algebra given by the tables of its basic operations.

Recommendations

• Deciding absorption in relational structures
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• Decidability of absorption in relational structures of bounded width.
• Absorption and directed Jónsson terms
• Absorption in universal algebra and CSP

Cites work

• A course in combinatorics.
• Algebras Whose Congruence Lattices are Distributive.
• Finitely related clones and algebras with cube terms.
• scientific article; zbMATH DE number 3751028 (Why is no real title available?)
• ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
• Robust satisfiability of constraint satisfaction problems
• Universal algebra. Fundamentals and selected topics
• Varieties with few subalgebras of powers

Cited in

(4)

• Existence of cube terms in finite algebras
• Deciding absorption in relational structures
• Strong subalgebras and the constraint satisfaction problem
• Unifying the three algebraic approaches to the CSP via minimal Taylor algebras

This page was built for publication: Deciding absorption

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