For each clone C on a set A there is an associated equivalence relation analogous to Green's R-relation, which relates two operations on A if and only if each one is a substitution instance of the other using operations from C. We study the maximal and submaximal clones on a three-element set and determine which of them have only finitely many relative R-classes.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgaa_1160,
author = {Erkko Lehtonen and \'Agnes Szendrei},
title = {The submaximal clones on the three-element set with finitely many relative R-classes},
journal = {Discussiones Mathematicae - General Algebra and Applications},
volume = {30},
year = {2010},
pages = {7-33},
zbl = {1244.08001},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgaa_1160}
}
Erkko Lehtonen; Ágnes Szendrei. The submaximal clones on the three-element set with finitely many relative R-classes. Discussiones Mathematicae - General Algebra and Applications, Tome 30 (2010) pp. 7-33. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgaa_1160/
[000] [1] G.A. Burle, The classes of k-valued logics containing all one-variable functions, Diskretnyi Analiz 10 (1967), 3-7. | Zbl 0147.25304
[001] [2] J. Demetrovics and J. Bagyinszki, The lattice of linear classes in prime-valued logics, in: J.L. Kulikowski, M. Michalewicz, S.V. Yablonskii, Yu.I. Zhuravlev (eds.), Discrete Mathematics (Warsaw, 1977), Banach Center Publ. 7, PWN, Warsaw (1982), pp. 105-123. | Zbl 0538.03020
[002] [3] A. Feigelson and L. Hellerstein, The forbidden projections of unate functions, Discrete Appl. Math. 77 (1997), 221-236. doi: 10.1016/S0166-218X(96)00136-9 | Zbl 0882.94030
[003] [4] M.A. Harrison, On the classification of Boolean functions by the general linear and affine groups, J. Soc. Indust. Appl. Math. 12 (2) (1964), 285-299. doi: 10.1137/0112026 | Zbl 0134.25802
[004] [5] J. Henno, Green's equivalences in Menger systems, Tartu Riikl. Ül. Toimetised 277 (1971), 37-46.
[005] [6] D. Lau, Submaximale Klassen von P₃, Elektron. Informationsverarb. Kybernet. 18 (1982), 227-243.
[006] [7] D. Lau, Function Algebras on Finite Sets, Springer-Verlag, Berlin, Heidelberg 2006. | Zbl 1105.08001
[007] [8] E. Lehtonen, Descending chains and antichains of the unary, linear, and monotone subfunction relations, Order 23 (2006), 129-142. doi: 10.1007/s11083-006-9036-y | Zbl 1124.08002
[008] [9] E. Lehtonen and Á. Szendrei, Equivalence of operations with respect to discriminator clones, Discrete Math. 309 (2009), 673-685. doi: 10.1016/j.disc.2008.01.003 | Zbl 1168.08003
[009] [10] E. Lehtonen and Á. Szendrei, Clones with finitely many relative R-classes, arXiv:0905.1611. | Zbl 1217.08002
[010] [11] H. Machida, On closed sets of three-value monotone logical functions, in: B. Csákány, I. Rosenberg (eds.), Finite Algebra and Multiple-Valued Logic (Szeged, 1979), Colloq. Math. Soc. János Bolyai 28, North-Holland, Amsterdam (1981), pp. 441-467.
[011] [12] S.S. Marchenkov, J. Demetrovics and L. Hannák, Closed classes of self-dual functions in P₃, Metody Diskret. Anal. 34 (1980), 38-73. | Zbl 0469.03046
[012] [13] N. Pippenger, Galois theory for minors of finite functions, Discrete Math. 254 (2002), 405-419. doi: 10.1016/S0012-365X(01)00297-7 | Zbl 1010.06012
[013] [14] R. Pöschel and L.A. Kalužnin, Funktionen- und Relationenalgebren: Ein Kapitel der diskreten Mathematik, Birkhäuser, Basel, Stuttgart 1979.
[014] [15] I.G. Rosenberg, Über die funktionale Vollständigkeit in den mehrwertigen Logiken, Rozpravy Československé Akad. Věd, Řada Mat. Přírod. Věd 80 (1970), 3-93. | Zbl 0199.30201
[015] [16] J. Słupecki, Kryterium pełności wielowartościowych systemów logiki zdań, C.R. Séanc. Soc. Sci. Varsovie, Cl. III 32 (1939), 102-109. English translation: A criterion of fullness of many-valued systems of propositional logic, Studia Logica 30 (1972), 153-157. doi: 10.1007/BF02120845
[016] [17] Á. Szendrei, Clones in Universal Algebra, Séminaire de mathématiques supérieures 99, Les Presses de l'Université de Montréal, Montréal 1986.
[017] [18] C. Wang, Boolean minors, Discrete Math. 141 (1995), 237-258. doi: 10.1016/0012-365X(93)E0191-6 | Zbl 0837.68081
[018] [19] C. Wang and A.C. Williams, The threshold order of a Boolean function, Discrete Appl. Math. 31 (1991), 51-69. doi: 10.1016/0166-218X(91)90032-R | Zbl 0728.94015
[019] [20] S.V. Yablonsky, Functional constructions in a k-valued logic, Trudy Mat. Inst. Steklov. 51 (1958), 5-142.
[020] [21] I.E. Zverovich, Characterizations of closed classes of Boolean functions in terms of forbidden subfunctions and Post classes, Discrete Appl. Math. 149 (2005), 200-218. doi: 10.1016/j.dam.2004.06.028 | Zbl 1086.06015