Skip to main content
SpringerLink
Log in

A quasi-Mal’cev condition with unexpected application

  • Published:
Algebra universalis Aims and scope Submit manuscript

Abstract

A quasi-Mal’cev condition for quasivarieties is established which in the case of locally finite quasivarieties forbids strongly abelian congruences and for varieties is equivalent to possessing a weak-difference term. We then look at two wellknown theorems concerning constraint satisfaction and the closure of finite digraphs under a Taylor operation.

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. Baker K.: Finite equational bases for finite algebras in a congruence-distributive equational class. Advances in Math. 24, 207–243 (1977)

    Article  MATH  MathSciNet  Google Scholar 

  2. Barto L., Kozik M.: Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem. Log. Methods Comput. Sci. 8, 207–243 (2012)

    Article  MathSciNet  Google Scholar 

  3. Bergman, C.: Universal Algebra: Fundamentals and Selected Topics. Pure and Applied Mathematics, CRC Press, Boca Raton (2012)

  4. Bulatov, A.: A graph of a relational structure and constraint satisfaction problems. Proc. of the 19th Annual IEEE Symp. on Logic in Comput. Sci., pp. 448–457, Turku (2004)

  5. Bulatov A.: H-coloring dichotomy revisited. Theoret. Comput. Sci. 349, 31–39 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  6. Bulatov, A.: Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Log. 12, paper 24 (2011)

  7. Bulatov, A., Jeavons, P., Krokhin, A.: Constraint satisfaction problems and finite algebras. Automata, languages and programming (Geneva, 2000), Lecture Notes in Comput. Sci., pp. 272–282. Springer, Berlin (2000)

  8. Bulatov, A., Jeavons, P., Krokhin, A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34, 720–742 (2005)

  9. Burris, S., Sankappanavar, H.P.: A Course in Universal Algebra. Graduate Texts in Mathematics, vol.78, Springer-Verlag, New York, 1981.

  10. Hell, P., Nes̆etr̆il, J.: On the complexity of H-coloring. J. Combin. Theory Ser. B 48, 92–110 (1990)

  11. Hobby, D., McKenzie, R.: The Structure of Finite Algebras. Contemporary Mathematics, vol. 76, American Mathematical Society, Providence (1988)

  12. Jeavons P., Cohen D.A., Cooper M.: Constraints, consistency and closure. Artificial Intelligence 101, 251–265 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  13. Jónsson B.: Algebras whose congruence lattices are distributive. Math. Scand. 21, 110–121 (1967)

    MATH  MathSciNet  Google Scholar 

  14. Kearnes, K., McKenzie, R.: Commutator theory for relatively modular quasivarieties. Trans. Amer. Math. Soc. 331, 465–502 (1992)

  15. Kearnes, K., Szendrei, Á.: The relationship between two commutators. Internat. J. Algebra and Comput. 9, 497–531 (1998)

  16. Kearnes, K., Willard, R.: Residually finite, congruence meet-semidistributive varieties of finite type have a finite residual bound. Proc. Amer. Math. Soc. 127, 2841–2850 (1999)

  17. Kun, G., Szegedy, M.: A new line of attack on the dichotomy conjecture [extended abstract]. Proceedings of the 2009 ACM International Symposium on Theory of Computing, pp. 725–734. ACM, New York (2009)

  18. Larose B.: Taylor operations of finite reflexive structures. Int. J. Math. Comput. Sci. 1, 1–21 (2006)

    MATH  MathSciNet  Google Scholar 

  19. Larose B., Tardif C.: A discrete homotopy theory for binary reflexive structures. Adv. Math. 189, 268–300 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  20. Maróti M., McKenzie R.: Finite basis problems and results for quasivarieties. Studia Logica 78, 293–320 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  21. Pigozzi D.: Finite basis theorems for relatively congruence distributive quasivarieties. Trans. Amer. Math. Soc. 310, 499–533 (1998)

    Article  MathSciNet  Google Scholar 

  22. Siggers M.H.: A new proof of the H-coloring dichotomy. SIAM J. Discrete Math. 23, 2204–2210 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  23. Siggers, M.H.: A strong Mal’cev condition for locally finite varieties omitting the unary type. Algebra Universalis 64, 15–20 (2010)

  24. Taylor W.: Varieties obeying homotopy laws. Canad. J. Math. 29, 498–527 (1977)

    Article  MATH  MathSciNet  Google Scholar 

  25. Willard R.: A finite basis theorem for residually finite, congruence meet-semidistributive varieties. J. Symbolic Logic 65, 187–200 (2000)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Pure Math Department, University of Waterloo, Ontario, N2L 3G1, Canada

    Alexander Wires

Authors
  1. Alexander Wires
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alexander Wires.

Additional information

Presented by K. Kearnes.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Wires, A. A quasi-Mal’cev condition with unexpected application. Algebra Univers. 73, 335–346 (2015). https://doi.org/10.1007/s00012-015-0322-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00012-015-0322-7

2010 Mathematics Subject Classification

Key words and phrases

Search

Navigation