Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-25T00:59:10.894Z Has data issue: false hasContentIssue false
  • English
  • Français

A Subalgebra Intersection Property for Congruence Distributive Varieties

Published online by Cambridge University Press:  20 November 2018

Matthew A. Valeriote
Matthew A. Valeriote*
Affiliation:
Department of Mathematics and Statistics, McMaster University, Hamilton, ON, L8S 4K1, [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Keywords

08B1068Q2508B05congruence distributiveconstraint satisfaction problemtame congruence theoryJónsson termsMal’cev condition
Type
Research Article
Information
Canadian Journal of Mathematics , Volume 61 , Issue 2 , 01 April 2009 , pp. 451 - 464
Copyright
Copyright © Canadian Mathematical Society 2009

References

[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] 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] 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] 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] 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] Burris, S. and Sankappanavar, H. P.. A course in universal algebra. Graduate Texts in Mathematics 78, Springer-Verlag, New York, 1981.Google Scholar
[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] 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] Freese, R. S. and Valeriote, M. A., On the complexity of some Maltsev conditions. Internat. J. Algebra Comput., to appear.Google Scholar
[10] Hobby, D. and Mc Kenzie, R. , The structure of finite algebras, Contemporary Mathematics 76, American Mathematical Society, Providence, RI, 1988.Google Scholar
[11] Jeavons, P., On the algebraic structure of combinatorial problems. Theoret. Comput. Sci. 200(1998), no. 1-2, 185–204.Google Scholar
[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] 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] 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] Larose, B. and Zádori, L., Bounded width problems and algebras. Algebra Universalis 56(2007), no. 3-4, 439–466.Google Scholar
[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] 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] Valeriote, M. A., Finite simple abelian algebras are strictly simple. Proc. Amer. Math. Soc. 108(1990), no. 1, 49–57.Google Scholar