Finitely Related Algebras in CongruenceDistributive Varieties Have Near UnanimityTerms

Barto, Libor

Canadian journal of mathematics, Tome 65 (2013) no. 1, pp. 3-21

Résumé

We show that every finite, finitely related algebra in a congruence distributive variety has a near unanimity term operation. As a consequence we solve the near unanimity problem for relational structures: it is decidable whether a given finite set of relations on a finite set admits a compatible near unanimity operation. This consequence also implies that it is decidable whether a given finite constraint language defines a constraint satisfaction problem of bounded strict width.

Détail

DOI : 10.4153/CJM-2011-087-3

Mots-clés : 08B05, 08B10, congruence distributive variety, Jόnsson operations, near unanimity operation, finitely related algebra, constraint satisfaction problem

Bibliographie

[1]Aichinger, E., Mayr, P., and McKenzie, R., On the number of finite algebraic structures.arxiv:1103.2265. Google Scholar

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

[3]Barto, L. and Kozik, M., Congruence distributivity implies bounded width. SIAM J. Comput. 39 (2009/10), no. 4, 1531–1542x. . Google Scholar | DOI

[4]Kozik, M. Constraint satisfaction problems of bounded width. In:2009 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), IEEE Computer Soc., Los Alamitos, CA, 2009, pp. 595–603. Google Scholar

[5] Berman, J.,Idziak, P., Marković, P., McKenzie, R., Valeriote, M., and Willard, R., Varieties with fewsubalgebras of powers. Trans. Amer. Math. Soc. 362(2010), no. 3, 1445–1473. Google Scholar | DOI

[6] Bodnarčuk, V. G., Kalužnin, L. A., Kotov, V. N., and Romov, B. A., Galois theory for Post algebras. I, II. (Russian), Kibernetika (Kiev) 1969, no. 3, 1–10; ibid. 1969, no. 5, 1-9. Google Scholar

[7]Bova, S., Chen, H., and Valeriote, M., Generic expression hardness results for primitive positive formula comparison. 38th International Colloquium on Automata, Languages and Programming (ICALP), Zürich, Switzerland, 2011. Google Scholar

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

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

[10]Davey, B. A., Monotone clones and congruence modularity. Order 6(1990), no. 4, 389–400. Google Scholar | DOI

[11 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 | DOI

[12] Freese, R. and Valeriote, M. A., On the complexity of some Maltsev conditions. Internat. J. Algebra Comput. 19(2009), no. 1,41–77. Google Scholar | DOI

[13] Geiger, D., Closed systems of functions and predicates.Pacific J. Math. 27(1968), 95–100. Google Scholar

[14] Idziakć, P., Markovi, P., McKenzie, R.,Valeriote, M., and Willard, R., Tractability and learnability arising from algebras with few subpowers. In: Proceedings of the Twenty-Second Annual IEEE Symposium on Logic in Computer Science (LICS 2007), IEEE Computer Society Press, 2007, pp. 213–222. Google Scholar

[15]Jeavons, P., Cohen, D., and Gyssens, M., Closure properties of constraints. J. ACM 44(1997), no. 4, 527–548. . Google Scholar | DOI

[16]Jónsson, B., Algebras whose congruence lattices are distributive. Math.Scand. 21(1968), 110–121. Google Scholar

[17] Kun, G. and Szabó, C., Order varieties and monotone retractions of finite posets. Order 18(2001), no. 1, 79–88. http://dx.doi.org/10.1023/A:1010681409599 Google Scholar

[18]Larose, B., Loten, C., and Zádori, L., A polynomial-time algorithm for near-unanimity graphs. J. Algorithms 55(2005), no. 2, 177–191. Google Scholar | DOI

[19] Larose, B. and Zádori, L., Algebraic properties and dismantlability of finite posets. Discrete Math. 163(1997), no. 1-3, 89–99. Google Scholar | DOI

[20] Marković, P. and McKenzie, R., Few subpowers, congruence distributivity and near-unanimity terms. Algebra Universalis 58(2008), no. 2, 119–128. Google Scholar | DOI

[21] Maróti, M., On the (un)decidability of a near-unanimity term. Algebra Universalis 57(2007), no. 2, 215–237. Google Scholar | DOI

[22]Maróti, M., The existence of a near-unanimity term in a finite algebra is decidable. J. Symbolic Logic 74(2009), no. 3, 1001–1014. Google Scholar | DOI

[23] Maróti, M. , Monotone clones, residual smallness and congruence distributivity. Bull. Austral. Math. Soc. 41(1990), no. 2, 283–300. Google Scholar | DOI

[24] L.Zádori, , Monotone Jónsson operations and near unanimity functions. Algebra Universalis 33 (1995), 216–236. Google Scholar | DOI