Abstract
In the paper, we introduce a notion of a key relation, which is similar to the notion of a critical relation introduced by Keith A. Kearnes and Ágnes Szendrei. All clones on finite sets can be defined by only key relations. In addition, there is a nice description of all key relations on 2 elements. These are exactly the relations that can be defined as a disjunction of linear equations. In the paper, we show that in general, key relations do not have such a nice description. Nevertheless, we obtain a nice characterization of all key relations preserved by a weak near-unanimity function. This characterization is presented in the paper.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bulatov A., Jeavons P., Krokhin A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34, 720–742 (2005)
Bulatov, A., Valeriote, M.: Recent results on the algebraic approach to the csp. In: Creignou, N., Kolaitis, P., Vollmer, H. (eds.) Complexity of Constraints. Lecture Notes in Computer Science, vol. 5250, pp. 68–92. Springer, Berlin (2008)
Feder T., Vardi M.Y.: The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput. 28, 57–104 (1999)
Jeavons P., Cohen D., Cooper M.C.: Constraints, consistency and closure. Artif. Intell. 101, 251–265 (1998)
Kearnes, K.A., Szendrei, A.: Clones of algebras with parallelogram terms. Internat. J. Algebra Comput. 22, 1250005, 30 pp. (2012)
Lau D.: Bestimmung der ordnung maximaler klassen von funktionen der k-wertigen logik. Math. Logic Quart. 24, 79–96 (1978)
Lau, D.: Function algebras on finite sets. Springer (2006)
Maroti M., Mckenzie R.: Existence theorems for weakly symmetric operations. Algebra universalis 59, 463–489 (2008)
Post, E.L.: Determination of all closed systems of truth tables. Bull. Amer. Math. Soc. 26, p. 427 (1920)
Post E.L.: Two-Valued Iterative Systems of Mathematical Logic. Princeton Univ. Press, Princeton (1941)
Romov, B.A.: On the lattice of subalgebras of direct products of post algebras of finite degree. Mathematical Models of Complex Systems, IK AN UkrSSR, Kiev 65, 156–168 (2011) (Russian)
Rosenberg, I.: über die funktionale vollständigkeit in den mehrwertigen logiken. Rozpravy Československe Akad. Věd., Ser. Math. Nat. Sci. 80, 3–93 (1970)
Taymanov V.A.: On cartesian powers of P 2. Dokl. Akad. Nauk SSSR 270, 1327–1330 (1983)
Zhuk D.: The predicate method to construct the Post lattice. Discrete Mathematics and Applications 21, 329–344 (2011)
Zhuk D.: The cardinality of the set of all clones containing a given minimal clone on three elements. Algebra Universalis 68, 295–320 (2012)
Zhuk D.: The lattice of all clones of self-dual functions in three-valued logic. J. Mult.-Valued Logic Soft Comput. 24, 251–316 (2015)
Author information
Authors and Affiliations
Corresponding author
Additional information
Presented by A. Szendrei.
The research of the author is supported by grant RFFI 13-01-00684-a.
Rights and permissions
About this article
Cite this article
Zhuk, D.N. Key (critical) relations preserved by a weak near-unanimity function. Algebra Univers. 77, 191–235 (2017). https://doi.org/10.1007/s00012-017-0426-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00012-017-0426-3