On the number of operations in a clone
Authors:
Joel Berman and Andrzej Kisielewicz
Journal:
Proc. Amer. Math. Soc. 122 (1994), 359369
MSC:
Primary 08A40
MathSciNet review:
1198450
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: A clone C on a set A is a set of operations on A containing the projection operations and closed under composition. A combinatorial invariant of a clone is its sequence , where is the number of essentially nary operations in C. We investigate the links between this invariant and structural properties of clones. It has been conjectured that the sequence of a clone on a finite set is either eventually strictly increasing or is bounded above by a finite constant. We verify this conjecture for a large family of clones. A special role in our work is played by totally symmetric operations and totally symmetric clones. We show that every totally symmetric clone on a finite set has a bounded sequence and that it is decidable if a clone is totally symmetric.
 [B]
J. Berman, Lecture notes: Free spectra of finite algebras, manuscript, April, 1986.
 [B1]
Joel
Berman, On the combinatorics of free algebras, Lattices,
semigroups, and universal algebra (Lisbon, 1988) Plenum, New York, 1990,
pp. 13–19. MR 1085062
(91i:08012)
 [DDT]
Marc
Davio, JeanPierre
Deschamps, and André
Thayse, Discrete and switching functions, Georgi Publishing
Co., St.Saphorin; McGrawHill International Book Co., New
YorkAucklandBeirut, 1978. With a foreword by Raymond T. Yeh. MR 0497337
(58 #15709)
 [DK]
Józef
Dudek and Andrzej
Kisielewicz, Totally commutative semigroups, J. Austral. Math.
Soc. Ser. A 51 (1991), no. 3, 381–399. MR 1125441
(93d:20103)
 [G]
George
Grätzer, Composition of functions, Proc. Conf. on
Universal Algebra (Queen’s Univ., Kingston, Ont., 1969)
Queen’s Univ., Kingston, Ont., 1970, pp. 1–106. MR 0276161
(43 #1909)
 [GK]
G. Grätzer and A. Kisielewicz, A survey of some open problems on sequences and free spectra of algebras and varieties, Universal Algebra and Quasigroup Theory (A. Romanowska and J. D. H. Smith, eds.), Heldermann Verlag, Berlin, 1992, pp. 5788.
 [GP]
G.
Grätzer and J.
Płonka, On the number of polynomials of an idempotent
algebra. I, Pacific J. Math. 32 (1970),
697–709. MR 0256969
(41 #1624)
 [GPS]
G.
Grätzer, J.
Płonka, and A.
Sekanina, On the number of polynomials of a universal algebra.
I, Colloq. Math. 22 (1970), 9–11. MR 0294216
(45 #3289)
 [H]
Michael
A. Harrison, Introduction to switching and automata theory,
McGrawHill Book Co., New YorkTorontoLondon, 1965. MR 0186503
(32 #3963)
 [HM]
David
Hobby and Ralph
McKenzie, The structure of finite algebras, Contemporary
Mathematics, vol. 76, American Mathematical Society, Providence, RI,
1988. MR
958685 (89m:08001)
 [Ki]
A.
Kisielewicz, The 𝑝_{𝑛}sequences of idempotent
algebras are strictly increasing, Algebra Universalis
13 (1981), no. 2, 233–250. MR 631559
(83i:08001), http://dx.doi.org/10.1007/BF02483837
 [Ki1]
Andrzej
Kisielewicz, The 𝑝_{𝑛}sequences of idempotent
algebras are strictly increasing. II, Algebra Universalis
28 (1991), no. 4, 453–458. MR 1128383
(92m:08010), http://dx.doi.org/10.1007/BF01195856
 [Ko]
K.
M. Koh, Idempotent algebras with one essentially binary
polynomial, Nanyang Univ. J. Part III 6 (1972),
18–27 (English, with Chinese summary). MR 0419333
(54 #7355)
 [LL]
Samuel
C. Lee and Edward
T. Lee, On multivalued symmetric functions, IEEE Trans.
Computers C21 (1972), 312–317. MR 0321350
(47 #9883)
 [MMT]
Ralph
N. McKenzie, George
F. McNulty, and Walter
F. Taylor, Algebras, lattices, varieties. Vol. I, The
Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole
Advanced Books & Software, Monterey, CA, 1987. MR 883644
(88e:08001)
 [P]
Emil
L. Post, The TwoValued Iterative Systems of Mathematical
Logic, Annals of Mathematics Studies, no. 5, Princeton University
Press, Princeton, N. J., 1941. MR 0004195
(2,337a)
 [R]
I. Rosenberg, Completeness properties of multiplevalued logic algebras, Computer Science and MultipleValued Logic, Theory and Applications, NorthHolland, Amsterdam, 1977, pp. 144186.
 [S]
Ágnes
Szendrei, Clones in universal algebra, Séminaire de
Mathématiques Supérieures [Seminar on Higher Mathematics],
vol. 99, Presses de l’Université de Montréal,
Montreal, QC, 1986. MR 859550
(87m:08005)
 [SM]
I. Stojmenović and M. Miyakawa, Symmetric functions in manyvalued logics, Note on MultipleValued Logic in Japan 6 (1986), 126.
 [T]
Walter
Taylor, Equational logic, Houston J. Math.
Survey (1979), iii+83. MR 546853
(80j:03042)
 [U]
K.
Urbanik, Remarks on symmetrical operations, Colloq. Math.
15 (1966), 1–9. MR 0194379
(33 #2589)
 [W]
Ingo
Wegener, The complexity of Boolean functions, WileyTeubner
Series in Computer Science, John Wiley & Sons, Ltd., Chichester; B. G.
Teubner, Stuttgart, 1987. MR 905473
(89b:03066)
 [B]
 J. Berman, Lecture notes: Free spectra of finite algebras, manuscript, April, 1986.
 [B1]
 , The combinatorics of free algebras, Lattices, Semigroups and Universal Algebra, Plenum Press, New York, 1990. MR 1085062 (91i:08012)
 [DDT]
 M. Davio, J.P. Deschamps, and A. Thayse, Discrete and switching functions, McGrawHill, New York, 1978. MR 0497337 (58:15709)
 [DK]
 J. Dudek and A. Kisielewicz, Totally commutative semigroups, J. Austral. Math. Soc. Ser. A 51 (1991), 381399. MR 1125441 (93d:20103)
 [G]
 G. Grätzer, Composition of functions, Proceedings of the Conference on Universal Algebra (October 1969), Queen's Papers in Pure and Appl. Math., no. 25, Queen's Univ., Kingston, ON, 1970. MR 0276161 (43:1909)
 [GK]
 G. Grätzer and A. Kisielewicz, A survey of some open problems on sequences and free spectra of algebras and varieties, Universal Algebra and Quasigroup Theory (A. Romanowska and J. D. H. Smith, eds.), Heldermann Verlag, Berlin, 1992, pp. 5788.
 [GP]
 G. Grätzer and J. Płonka, On the number of polynomials of an idempotent algebra. I, Pacific J. Math. 32 (1970), 697709. MR 0256969 (41:1624)
 [GPS]
 G. Grätzer, J. Płonka, and A. Sekanina, On the number of polynomials of a universal algebra. I, Colloq. Math. 22 (1970), 911. MR 0294216 (45:3289)
 [H]
 M. Harrison, Introduction to switching and automata theory, McGrawHill, New York, 1965. MR 0186503 (32:3963)
 [HM]
 D. Hobby and R. McKenzie, The structure of finite algebras, Contemp. Math., vol. 76, Amer. Math. Soc., Providence, RI, 1988. MR 958685 (89m:08001)
 [Ki]
 A. Kisielewicz, The sequences of idempotent algebras are strictly increasing, Algebra Universalis 13 (1981), 233250. MR 631559 (83i:08001)
 [Ki1]
 , The sequences of idempotent algebras are strictly increasing. II, Algebra Universalis 28 (1991), 453458. MR 1128383 (92m:08010)
 [Ko]
 K. M. Koh, Idempotent algebras with one essentially binary polynomial, Nanyang Univ. J. 6 (1972), 1827. MR 0419333 (54:7355)
 [LL]
 S. C. Lee and E. T. Lee, On multivalued symmetric functions, IEEE Trans. Comput. C21 (1972), 312317. MR 0321350 (47:9883)
 [MMT]
 R. McKenzie, G. McNulty, and W. Taylor, Algebras, lattices, varieties, Vol. I, Wadsworth, Belmont, CA, 1987. MR 883644 (88e:08001)
 [P]
 E. L. Post, The twovalued iterative systems of mathematical logic, Ann. of Math. Stud., no. 5, Princeton Univ. Press, Princeton, NJ, 1941. MR 0004195 (2:337a)
 [R]
 I. Rosenberg, Completeness properties of multiplevalued logic algebras, Computer Science and MultipleValued Logic, Theory and Applications, NorthHolland, Amsterdam, 1977, pp. 144186.
 [S]
 A. Szendrei, Clones in universal algebra, Université de Montréal Press, 1986. MR 859550 (87m:08005)
 [SM]
 I. Stojmenović and M. Miyakawa, Symmetric functions in manyvalued logics, Note on MultipleValued Logic in Japan 6 (1986), 126.
 [T]
 W. Taylor, Equational logic, Houston J. Math., Special Survey Issue, 1979. Abridged version in G. Grätzer, Universal algebra, 2nd ed., SpringerVerlag, Berlin and New York, 1979. MR 546853 (80j:03042)
 [U]
 K. Urbanik, Remarks on symmetrical operations, Colloq. Math. 15 (1966), 19. MR 0194379 (33:2589)
 [W]
 I. Wegner, The complexity of Boolean functions, Wiley, New York, 1987. MR 905473 (89b:03066)
Similar Articles
Retrieve articles in Proceedings of the American Mathematical Society
with MSC:
08A40
Retrieve articles in all journals
with MSC:
08A40
Additional Information
DOI:
http://dx.doi.org/10.1090/S00029939199411984509
PII:
S 00029939(1994)11984509
Article copyright:
© Copyright 1994
American Mathematical Society
