Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-25T13:40:09.906Z Has data issue: false hasContentIssue false
  • English
  • Français

Finitely Related Algebras in CongruenceDistributive Varieties Have Near UnanimityTerms

Published online by Cambridge University Press:  20 November 2018

Libor Barto
Libor Barto*
Affiliation:
Department of Mathematics and Statistics, McMaster University, Hamilton, ON
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 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.

Keywords

08B0508B10congruence distributive varietyJόnsson operationsnear unanimity operationfinitely related algebraconstraint satisfaction problem
Type
Research Article
Information
Canadian Journal of Mathematics , Volume 65 , Issue 1 , 01 February 2013 , pp. 3 - 21
Copyright
Copyright © Canadian Mathematical Society 2013

References

[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. http://dx.doi.org/10.1007/BF01187059 Google Scholar
[3]Barto, L. and Kozik, M., Congruence distributivity implies bounded width. SIAM J. Comput. 39 (2009/10), no. 4, 1531–1542x. http://dx.doi.org/10.1137/080743238.Google Scholar
[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. http://dx.doi.org/10.1090/S0002-9947-09-04874-0 Google Scholar
[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. http://dx.doi.org/10.1137/S0097539700376676 Google Scholar
[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.http://dx.doi.org/10.1007/BF00346133 Google Scholar
[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. http://dx.doi.org/10.1137/S0097539794266766 Google Scholar
[12] Freese, R. and Valeriote, M. A., On the complexity of some Maltsev conditions. Internat. J. Algebra Comput. 19(2009), no. 1,41–77. http://dx.doi.org/10.1142/S0218196709004956 Google Scholar
[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. http://dx.doi.org/10.1145/263867.263489.Google Scholar
[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:1010681409599Google 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. http://dx.doi.org/10.1016/j.jalgor.2004.04.011 Google Scholar
[19] Larose, B. and Zádori, L., Algebraic properties and dismantlability of finite posets. Discrete Math. 163(1997), no. 1-3, 89–99. http://dx.doi.org/10.1016/0012-365X(95)00312-K Google Scholar
[20] Marković, P. and McKenzie, R., Few subpowers, congruence distributivity and near-unanimity terms. Algebra Universalis 58(2008), no. 2, 119–128. http://dx.doi.org/10.1007/s00012-008-2049-1 Google Scholar
[21] Maróti, M., On the (un)decidability of a near-unanimity term. Algebra Universalis 57(2007), no. 2, 215–237. http://dx.doi.org/10.1007/s00012-007-2037-x Google Scholar
[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. http://dx.doi.org/10.2178/jsl/1245158096 Google Scholar
[23] Maróti, M. , Monotone clones, residual smallness and congruence distributivity. Bull. Austral. Math. Soc. 41(1990), no. 2, 283–300. http://dx.doi.org/10.1017/S0004972700018104 Google Scholar
[24] L.Zádori, , Monotone Jónsson operations and near unanimity functions. Algebra Universalis 33 (1995), 216–236. http://dx.doi.org/10.1007/BF01190934 Google Scholar