Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-26T22:16:29.684Z Has data issue: false hasContentIssue false
  • English
  • Français

The existence of a near-unanimity term in a finite algebra is decidable

Published online by Cambridge University Press:  12 March 2014

Miklós Maróti
Miklós Maróti*
Affiliation:
Bolyai Institute, University of Szeged, Aradi Vértanúk Tere 1, H-6720 Szeged, Hungary, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove that it is decidable of a finite algebra whether it has a near-unanimity term operation, which settles a ten-year-old problem. As a consequence, it is decidable of a finite algebra in a congruence distributive variety whether it admits a natural duality.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 74 , Issue 3 , September 2009 , pp. 1001 - 1014
Copyright
Copyright © Association for Symbolic Logic 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Baker, K. A. and Pixley, A. F., Polynomial interpolation and the Chinese remainder theorem, Mathematische Zeitschrift, vol. 143 (1975), pp. 165–174.CrossRefGoogle Scholar
[2]Bulatov, A., Krokhin, A. A., and Jeavons, P., Constraint satisfaction problems and finite algebras, Lecture Notes in Computer Science, vol. 1853 (2000), pp. 272–282.CrossRefGoogle Scholar
[3]Davey, B. A., Heindorf, L., and McKenzie, R., Near unanimity: an obstacle to general duality theory, Algebra Universalis, vol. 33 (1995), pp. 428–439.CrossRefGoogle Scholar
[4]Davey, B. A. and Werner, H., Dualities and equivalences for varieties of algebras, Contributions to Lattice Theory {Szeged, 1980), Colloqium Mathematica Societatis Jànos Bolyai, vol. 33, North-Holland, Amsterdam, 1983, pp. 101–275.Google Scholar
[5]Feder, T. and Vardi, M. Y., The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory, SIAM Journal of Computing, vol. 28 (1998), no. 1, pp. 57–104.CrossRefGoogle Scholar
[6]Idziak, P. M., Marković, P., McKenzie, R., Valeriote, M., and Willard, R., Tractability and learnability arising from algebras with few subpowers, Proceedings of 22nd Logic in Computer Science, 2007, pp. 213–224.Google Scholar
[7]Jeavons, P., Cohen, D., and Cooper, M. C., Constraints, consistency and closure, Artificial Intelligence, vol. 101 (1998), pp. 251–265.CrossRefGoogle Scholar
[8]Lau, D., Function algebras on finite sets: Basic course on many-valued logic and clone theory, Monographs in Mathematics, Springer, Berlin Heidelberg, 2006.Google Scholar
[9]Lovász, L., Kneser's conjecture, chromatic numbers and homotopy, Journal of Combinatorial Theory, Series A, vol. 25 (1978), pp. 319–324.CrossRefGoogle Scholar
[10]Maróti, M., On the (un) decidability of a near-unanimity term, Algebra Universalis, vol. 57 (2007), no. 2, pp. 215–237.CrossRefGoogle Scholar
[11]Maróti, M. and McKenzie, R., Existence theorems for weakly symmetric operations, Algebra Universalis, vol. 59 (2008), no. 3-4, pp. 463–489.CrossRefGoogle Scholar
[12]McKenzie, R., Is the presence of a nu-term a decidable property of a finite algebra?, manuscript, 10 15, 1997.Google Scholar