No Access

Deciding absorption

Libor Barto

Department of Algebra, Charles University, Sokolovská 83, 186 00 Praha 8, Czech Republic

E-mail Address: libor.barto@gmail.com

Search for more papers by this author

and

Alexandr Kazda

Institute of Science and Technology Austria, Am Campus 1, 3400, Klosterneuburg, Austria

E-mail Address: alex.kazda@gmail.com

Search for more papers by this author

https://doi.org/10.1142/S0218196716500430Cited by:4 (Source: Crossref)

Abstract

We characterize absorption in finite idempotent algebras by means of Jónsson 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.

Communicated by K. Kearnes

Keywords:

AMSC: 08A70, 08B10

References

1. K. A. Baker and A. F. Pixley, Polynomial interpolation and the Chinese remainder theorem for algebraic systems, Math. Zeit. 143 (1975) 165–174. Crossref, Web of Science, Google Scholar
2. L. Barto, The dichotomy for conservative constraint satisfaction problems revisited, in 26th Annual IEEE Symp. on Logic in Computer Science (LICS) (IEEE, 2011), pp. 301–310. Google Scholar
3. L. Barto and J. Bulín, Deciding absorption in relational structures, in preparation. Google Scholar
4. L. Barto and M. Kozik, Congruence distributivity implies bounded width, SIAM J. Comput. 39(4) (2009) 1531–1542. Crossref, Web of Science, Google Scholar
5. L. Barto and M. Kozik, Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem, Logical Methods Comput. Sci. 8(1) (2012). Crossref, Web of Science, Google Scholar
6. L. Barto and M. Kozik, Robust satisfiability of constraint satisfaction problems, in Proc. 44th Symp. on Theory of Computing (2012) 931–940. Google Scholar
7. L. Barto and M. Kozik, Constraint satisfaction problems solvable by local consistency methods, J. ACM 61 (2014) 3:1–3:19. Crossref, Web of Science, Google Scholar
8. L. Barto, M. Kozik and D. Stanovský, Mal’tsev conditions, lack of absorption, and solvability, Algebra Universalis 74(1–2) (2015) 185–206. Crossref, Web of Science, Google Scholar
9. C. Bergman, Universal Algebra: Fundamentals and Selected Topics, 1st edn. (Chapman & Hall/CRC Press, Boca Raton, New York, Abingdon, 2011). Crossref, Google Scholar
10. J. Berman, P. Idziak, P. Markovic, R. McKenzie, M. Valeriote and R. Willard, Varieties with few subalgebras of powers, Trans. Amer. Math. Soc. 362 (2010) 1445–1473. Crossref, Web of Science, Google Scholar
11. S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, Graduate Texts in Mathematics (Springer, New York, 1981). Crossref, Google Scholar
12. B. Jónsson, Algebras whose congruence lattices are distributive, Math. Scand. 21 (1967) 110–121. Crossref, Google Scholar
13. A. Kazda, M. Kozik, R. McKenzie and M. Moore, Absorption and directed Jónsson terms, in Don Pigozzi on Abstract Algebraic Logic, Universal Algebra and Computer Science, Outstanding Contributions to Logic (accepted). Google Scholar
14. A. Kazda and D. Zhuk, Arities and decision procedures for cube terms, manuscript. Google Scholar
15. K. A. Kearnes and A. Szendrei, Clones of algebras with parallelogram terms, Internat. J. Algebra Comput. 22(1) (2012) 1250005. Link, Web of Science, Google Scholar
16. P. Marković, M. Maróti and R. McKenzie, Finitely related clones and algebras with cube terms, Order 29(2) (2012) 345–359. Crossref, Google Scholar
17. P. Marković and R. McKenzie, Few subpowers, congruence distributivity and near-unanimity terms, Algebra Universalis 58 (2008) 119–128(10). Crossref, Web of Science, Google Scholar
18. M. Maróti, The existence of a near-unanimity term in a finite algebra is decidable, J. Symbolic Logic 74 (2009) 1001–1014. Crossref, Web of Science, Google Scholar
19. M. A. Valeriote and R. Freese, On the complexity of some Maltsev conditions, Internat. J. Algebra Comput. 19(2) (2009) 451–464. Google Scholar
20. J. H. van Lint and R. M. Wilson, A Course in Combinatorics, 2nd edn. (Cambridge University Press, 2001). Crossref, Google Scholar