A Subalgebra Intersection Property for Congruence Distributive Varieties

Valeriote, Matthew A.

Canadian journal of mathematics, Tome 61 (2009) no. 2, pp. 451-464

Résumé

We prove that if a finite algebra $\mathbf{A}$ generates a congruence distributive variety, then the subalgebras of the powers of $\mathbf{A}$ satisfy a certain kind of intersection property that fails for finite idempotent algebras that locally exhibit affine or unary behaviour. We demonstrate a connection between this property and the constraint satisfaction problem.

Détail

DOI : 10.4153/CJM-2009-023-2

Mots-clés : 08B10, 68Q25, 08B05, congruence distributive, constraint satisfaction problem, tame congruence theory, Jónsson terms, Mal’cev condition

Bibliographie

[1] [1] A Baker, K. and Pixley, A. F., Polynomial interpolation and the Chinese remainder theorem for algebraic systems. Math. Z. 143(1975), no. 2, 165–174, Google Scholar

[2] [2] Berman, J. D., Kiss, E. W., Pröhle, P., and Szendrei, á., The set of types of a finitely generated variety. Discrete Math. 112(1993)no. 1-3, 1–20. Google Scholar

[3] [3] Bulatov, A., A graph of a relational structure and constraint satisfaction problems. In: Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science, 2004, IEEE, 2004. pp. 448–457. Google Scholar

[4] [4] Bulatov, A. and Jeavons, P., Algebraic structures in combinatorial problems. Technical Report MATH-AL-4-2001, Technische Universität Dresden, Germany, 2001. Google Scholar

[5] [5] Bulatov, A., Jeavons, P., and Krokhin, A., Classifying the complexity of constraints using finite algebras. SIAMJ. Comput. 34(2005), no 3, 720–742. Google Scholar

[6] [6] Burris, S. and Sankappanavar, H. P.. A course in universal algebra. Graduate Texts in Mathematics 78, Springer-Verlag, New York, 1981. Google Scholar

[7] [7] Clasen, M. and Valeriote, M., Tame congruence theory. In: Lectures on algebraic model theory, Fields Inst. Monogr. 15, American Mathematical Society, Providence, RI, 2002, pp. 67–111. Google Scholar

[8] [8] Feder, T. and Vardi, M. Y., The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. Comput. 28(1999), no. 1, 57–104. Google Scholar

[9] [9] Freese, R. S. and Valeriote, M. A., On the complexity of some Maltsev conditions. Internat. J. Algebra Comput., to appear. Google Scholar

[10] [10] Hobby, D. and Mc Kenzie, R. , The structure of finite algebras, Contemporary Mathematics 76, American Mathematical Society, Providence, RI, 1988. Google Scholar

[11] [11] Jeavons, P., On the algebraic structure of combinatorial problems. Theoret. Comput. Sci. 200(1998), no. 1-2, 185–204. Google Scholar

[12] [12] Jeavons, P., Cohen, D., and Cooper, M. C., Constraints, consistency and closure. Artificial Intelligence 101(1998), no. 1-2, 251–265. Google Scholar

[13] [13] Kiss, E. W. and Pröhle, P., Problems and results in tame congruence theory. A survey of the ‘88 Budapest Workshop. Algebra Universalis 29(1992), no. 2, 151–171. Google Scholar

[14] [14] Kiss, E. W. and Valeriote, M. A.. On tractability and congruence distributivity. In: Proceedings of the 21st Annual IEEE Symposium on Logic in Computer Science, 2006, IEEE, 2006, pp. 221–230. Google Scholar

[15] [15] Larose, B. and Zádori, L., Bounded width problems and algebras. Algebra Universalis 56(2007), no. 3-4, 439–466. Google Scholar

[16] [16] Mc Kenzie, R., Mc Nulty, G., and Taylor, W., Algebras, Lattices, Varieties Volume 1. Wadsworth and Brooks/Cole, Monterey, CA, 1987. Google Scholar

[17] [17] Szendrei, á., A survey on strictly simple algebras and minimal varieties. In: Universal algebra and quasigroup theory (Jadwisin, 1989), Res. Exp. Math. 19, Heldermann, Berlin, 1992, pp. 209–239. Google Scholar

[18] [18] Valeriote, M. A., Finite simple abelian algebras are strictly simple. Proc. Amer. Math. Soc. 108(1990), no. 1, 49–57. Google Scholar