Abstract
This paper defines a computational problem, the edge-like problem, and proves that the problem is a decidable one when the input sets are finite. The edge-like problem is relevant to the field of universal algebra as it is a common generalization of several problems currently of interest in that field, and this paper proves that several of these problems are decidable.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Barto L., Kozik M.: Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem. Logical Methods in Computer Science 8, 1–26 (2012)
Berman, J., Idziak, P., Marković, P., McKenzie, R., Valeriote, M., Willard, R.: Varieties with few subalgebras of powers. Trans. Amer. Math. Soc. 362, 1445–1473 (2010)
Bulìn, J.: Decidability of absorption in relational structures of bounded width. Algebra Universalis 72, 15–28 (2014)
Dalmau, V.: A new tractable class of constraint satisfaction problems. Ann. Math. Artif. Intell. 44, 61–85 (2005)
Hobby, D., McKenzie, R.: The structure of finite algebras, Contemporary Mathematics, vol. 76. American Mathematical Society, Providence (1988)
Kiss, E.W., Kearnes, K.: The Shape of Congruence Lattices, Mem. Amer. Math. Soc., vol. 222 (2013)
Kozik, M., Krokhin, A., Maròti, M., Valeriote, M., Willard, R.: On maltsev conditions associated with omitting certain types of local structures. (2010, preprint)
Marković, P., Maròti, M., McKenzie, R.: Finitely related clones and algebras with cube terms. Order 29, 345–359 (2012)
Maròti, M.: The existence of a near-unanimity term in a finite algebra is decidable. J. Symbolic Logic 74, 1001–1014 (2009)
Maròti, M., McKenzie, R.: Existence theorems for weakly symmetric operations. Algebra Universalis 59, 463–489 (2008)
Valeriote, M.: Private communication (2011)
Author information
Authors and Affiliations
Corresponding author
Additional information
Presented by R. Freese.
Rights and permissions
About this article
Cite this article
Horowitz, J. Testing for edge terms is decidable. Algebra Univers. 73, 321–334 (2015). https://doi.org/10.1007/s00012-015-0325-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00012-015-0325-4