Skip to main content
SpringerLink
Log in

Testing for edge terms is decidable

  • Published:
Algebra universalis Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Barto L., Kozik M.: Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem. Logical Methods in Computer Science 8, 1–26 (2012)

    Article  MathSciNet  Google Scholar 

  2. 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)

  3. Bulìn, J.: Decidability of absorption in relational structures of bounded width. Algebra Universalis 72, 15–28 (2014)

  4. Dalmau, V.: A new tractable class of constraint satisfaction problems. Ann. Math. Artif. Intell. 44, 61–85 (2005)

  5. Hobby, D., McKenzie, R.: The structure of finite algebras, Contemporary Mathematics, vol. 76. American Mathematical Society, Providence (1988)

  6. Kiss, E.W., Kearnes, K.: The Shape of Congruence Lattices, Mem. Amer. Math. Soc., vol. 222 (2013)

  7. Kozik, M., Krokhin, A., Maròti, M., Valeriote, M., Willard, R.: On maltsev conditions associated with omitting certain types of local structures. (2010, preprint)

  8. Marković, P., Maròti, M., McKenzie, R.: Finitely related clones and algebras with cube terms. Order 29, 345–359 (2012)

  9. Maròti, M.: The existence of a near-unanimity term in a finite algebra is decidable. J. Symbolic Logic 74, 1001–1014 (2009)

  10. Maròti, M., McKenzie, R.: Existence theorems for weakly symmetric operations. Algebra Universalis 59, 463–489 (2008)

  11. Valeriote, M.: Private communication (2011)

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Ryerson University, 350 Victoria St., Toronto, ON, M5B2K3, Canada

    Jonah Horowitz

Authors
  1. Jonah Horowitz
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jonah Horowitz.

Additional information

Presented by R. Freese.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00012-015-0325-4

2010 Mathematics Subject Classification

Key words and phrases

Search

Navigation