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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Barto, L.: The dichotomy for conservative constraint satisfaction problems revisited. In: 26th Annual IEEE Symposium on Logic in Computer Science—LICS 2011, pp. 301–310. IEEE Computer Soc., Los Alamitos, CA (2011)
Barto L.: Finitely related algebras in congruence distributive varieties have near unanimity terms. Canad. J. Math. 65, 3–21 (2013)
Barto, L.: Finitely related algebras in congruence modular varieties have few subpowers (2016). To appear in J. Eur. Math. Soc. (JEMS)
Barto L., Kazda A.: Deciding absorption. Internat. J. Algebra Comput. 26, 1033–1060 (2016)
Barto L., Kozik M.: Congruence distributivity implies bounded width. SIAM J. Comput. 39, 1531–1542 (2009)
Barto, L., Kozik, M.: Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem. Log. Methods Comput. Sci. 8 (2012)
Barto, L., Kozik, M.: Constraint satisfaction problems solvable by local consistency methods. J. ACM 61, 3:1–3:19 (2014)
Barto, L., Kozik, M., Niven, T.: The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell). SIAM J. Comput. 38, 1782–1802 (2008/09)
Barto L., Kozik M., Stanovský D.: Mal’tsev conditions, lack of absorption, and solvability. Algebra Universalis 74, 185–206 (2015)
Barto, L., Kozik, M., Willard, R.: Near unanimity constraints have bounded pathwidth duality. In: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 125–134. IEEE Computer Soc., Los Alamitos, CA (2012)
Bergman, C.: Universal Algebra: Fundamentals and Selected Topics. Pure and Applied Mathematics. Taylor and Francis (2011)
Bodnarčuk, V.G., Kalužnin, L.A., Kotov, V.N., Romov, B.A.: Galois theory for Post algebras. I, II. Kibernetika (Kiev) pp. 1–10 (1969)
Bulín J.: Decidability of absorption in relational structures of bounded width. Algebra Universalis 72, 15–28 (2014)
Burris, S.N., Sankappanavar, H.P.: A Course in Universal Algebra, Graduate Texts in Mathematics, vol. 78. Springer, New York (1981)
Geiger D.: Closed systems of functions and predicates. Pacific J. Math. 27, 95–100 (1968)
Kazda, A., Kozik, M., McKenzie, R., Moore, M.: Absorption and directed Jónsson terms (2015). To appear in: Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science, in Outstanding Contributions to Logic, Springer
Willard, R.: Testing expressibility is hard. In: Cohen, D. (ed.) Principles and Practice of Constraint Programming – CP 2010, Lecture Notes in Computer Science, vol. 6308, pp. 9–23. Springer, Berlin (2010)
Zhuk D.N.: The existence of a near-unanimity function is decidable. Algebra Universalis 71, 31–54 (2014)
Author information
Authors and Affiliations
Corresponding author
Additional information
Presented by R. Willard.
Both authors were supported by the Grant Agency of the Czech Republic, grant 13-01832S. The second author was also supported by the Polish National Science Centre (NCN) grant 2011/01/B/ST6/01006.
Rights and permissions
About this article
Cite this article
Barto, L., Bulín, J. Deciding absorption in relational structures. Algebra Univers. 78, 3–18 (2017). https://doi.org/10.1007/s00012-017-0440-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00012-017-0440-5