Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-26T02:10:23.298Z Has data issue: false hasContentIssue false
  • English
  • Français

DECIDING SOME MALTSEV CONDITIONS IN FINITE IDEMPOTENT ALGEBRAS

Part of: Theory of computing Algebraic structures General logic

Published online by Cambridge University Press:  16 June 2020

ALEXANDR KAZDA Open the ORCID record for ALEXANDR KAZDA [Opens in a new window]  and
MATT VALERIOTE Open the ORCID record for MATT VALERIOTE [Opens in a new window]
ALEXANDR KAZDA
Affiliation:
DEPARTMENT OF ALGEBRA CHARLES UNIVERSITYPRAGUE, CZECH REPUBLICE-mail: [email protected]
MATT VALERIOTE
Affiliation:
DEPARTMENT OF MATHEMATICS & STATISTICS MCMASTER UNIVERSITY, HAMILTON ONTARIO, CANADAE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we investigate the computational complexity of deciding if the variety generated by a given finite idempotent algebra satisfies a special type of Maltsev condition that can be specified using a certain kind of finite labelled path. This class of Maltsev conditions includes several well known conditions, such as congruence permutability and having a sequence of n Jónsson terms, for some given n. We show that for such “path defined” Maltsev conditions, the decision problem is polynomial-time solvable.

Keywords

Maltsev conditionuniversal algebracomputational complexity

MSC classification

Primary: 68Q25: Analysis of algorithms and problem complexity
Secondary: 03B05: Classical propositional logic 08A40: Operations, polynomials, primal algebras
Type
Articles
Information
The Journal of Symbolic Logic , Volume 85 , Issue 2 , June 2020 , pp. 539 - 562
Copyright
© The Association for Symbolic Logic 2020

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

Barto, L. and Kozik, M., Constraint satisfaction problems solvable by local consistency methods . Journal of the ACM, vol. 61 (2014), no. 1, pp. 3–19.CrossRefGoogle Scholar
Barto, L., Krokhin, A., and Willard, R., Polymorphisms, and how to use them , The Constraint Satisfaction Problem: Complexity and Approximability, (Krokhin, A. and Zivny, S., editors), Dagstuhl Follow- Ups, vol. 7, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2017, pp. 1–44.Google Scholar
Barto, L., Opršal, J., and Pinsker, M., The wonderland of reflections . Israel Journal of Mathematics, vol. 223 (2018), no. 1, pp. 363–398.CrossRefGoogle Scholar
Bergman, C., Universal Algebra: Fundamentals and Selected Topics, Pure and Applied Mathematics, vol. 301, CRC Press, Boca Raton, FL, 2012.Google Scholar
Burris, S. and Sankappanavar, H. P., A course in universal algebra , Graduate Texts in Mathematics, vol. 78, Springer-Verlag, New York; Berlin, 1981.CrossRefGoogle Scholar
Chen, H. and Larose, B., Asking the metaquestions in constraint tractability . ACM Transactions on Computation Theory, vol. 9 (2017), no. 3, pp. 11:1–11:27.CrossRefGoogle Scholar
Day, A., A characterization of modularity for congruence lattices of algebras . Canadian Mathematical Bulletin, vol. 12 (1969), pp. 167–173.CrossRefGoogle Scholar
Freese, R., Kiss, E., and Valeriote, M., Universal algebra calculator, 2011, Available at www.uacalc.org.Google Scholar
Freese, R. and Valeriote, M. A., On the complexity of some Maltsev conditions . International Journal of Algebra and Computation, vol. 19 (2009), no. 1, pp. 41–77.10.1142/S0218196709004956CrossRefGoogle Scholar
García, O. C. and Taylor, W., The lattice of interpretability types of varieties . Memoirs of the American Mathematical Society, vol. 50 (1984), no. 305.CrossRefGoogle Scholar
Gumm, H. P., Geometrical methods in congruence modular algebras . Memoirs of the American Mathematical Society, vol. 45 (1983), no. 286.CrossRefGoogle Scholar
Hagemann, J. and Mitschke, A., On n-permutable congruences . Algebra Universalis, vol. 3 (1973), pp. 8–12.CrossRefGoogle Scholar
Hobby, D. and McKenzie, R., The structure of finite algebras , Contemporary Mathematics, vol. 76, American Mathematical Society, Providence, RI, revised in 1996, 1988.Google Scholar
Horowitz, J., Computational complexity of various Mal’cev conditions . International Journal of Algebra and Computation, vol. 23 (2013), no. 6, pp. 1521–1531.CrossRefGoogle Scholar
Jónsson, B., Algebras whose congruence lattices are distributive . Mathematica Scandinavica, vol. 21 (1967), pp. 110–121.CrossRefGoogle Scholar
Kazda, A., Kozik, M., McKenzie, R., and Moore, M., Absorption and Directed Jónsson Terms , Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science (Czelakowski, J., editor), Springer International Publishing, Cham, 2018, pp. 203–220.Google Scholar
Kazda, A., Opršal, J., Valeriote, M., and Zhuk, D., Deciding the existence of minority terms . Canadian Mathematical Bulletin, vol. 63 (2020), no. 3, pp. 577–591.CrossRefGoogle Scholar
Kearnes, K. A. and Kiss, E. W., The shape of congruence lattices . Memoirs of the American Mathematical Society, vol. 222 (2013), no. 1046.Google Scholar
Maĺcev, A. I., On the general theory of algebraic systems . Matematicheskii Sbornik. N.S., vol. 35 (1954), no. 77, pp. 3–20.Google Scholar
McKenzie, R. N., McNulty, G. F., and Taylor, W. F., Algebras, lattices, varieties , The Wadsworth & Brooks/Cole Mathematics Series, vol. 1, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1987.Google Scholar
Valeriote, M. and Willard, R., Idempotent n-permutable varieties . Bulletin of the London Mathematical Society, vol. 46 (2014), no. 4, pp. 870–880.CrossRefGoogle Scholar