On the number of operations in a clone

Authors:
Joel Berman and Andrzej Kisielewicz

Journal:
Proc. Amer. Math. Soc. **122** (1994), 359-369

MSC:
Primary 08A40

MathSciNet review:
1198450

Full-text 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 *n*-ary 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****[DDT]**Marc Davio, Jean-Pierre Deschamps, and André Thayse,*Discrete and switching functions*, Georgi Publishing Co., St.-Saphorin; McGraw-Hill International Book Co., New York-Auckland-Beirut, 1978. With a foreword by Raymond T. Yeh. MR**0497337****[DK]**Józef Dudek and Andrzej Kisielewicz,*Totally commutative semigroups*, J. Austral. Math. Soc. Ser. A**51**(1991), no. 3, 381–399. MR**1125441****[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****[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. 57-88.**[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****[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****[H]**Michael A. Harrison,*Introduction to switching and automata theory*, McGraw-Hill Book Co., New York-Toronto-London, 1965. MR**0186503****[HM]**David Hobby and Ralph McKenzie,*The structure of finite algebras*, Contemporary Mathematics, vol. 76, American Mathematical Society, Providence, RI, 1988. MR**958685****[Ki]**A. Kisielewicz,*The 𝑝_{𝑛}-sequences of idempotent algebras are strictly increasing*, Algebra Universalis**13**(1981), no. 2, 233–250. MR**631559**, 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**, 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****[LL]**Samuel C. Lee and Edward T. Lee,*On multivalued symmetric functions*, IEEE Trans. Computers**C-21**(1972), 312–317. MR**0321350****[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****[P]**Emil L. Post,*The Two-Valued Iterative Systems of Mathematical Logic*, Annals of Mathematics Studies, no. 5, Princeton University Press, Princeton, N. J., 1941. MR**0004195****[R]**I. Rosenberg,*Completeness properties of multiple-valued logic algebras*, Computer Science and Multiple-Valued Logic, Theory and Applications, North-Holland, Amsterdam, 1977, pp. 144-186.**[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****[SM]**I. Stojmenović and M. Miyakawa,*Symmetric functions in many-valued logics*, Note on Multiple-Valued Logic in Japan**6**(1986), 1-26.**[T]**Walter Taylor,*Equational logic*, Houston J. Math.**Survey**(1979), iii+83. MR**546853****[U]**K. Urbanik,*Remarks on symmetrical operations*, Colloq. Math.**15**(1966), 1–9. MR**0194379****[W]**Ingo Wegener,*The complexity of Boolean functions*, Wiley-Teubner Series in Computer Science, John Wiley & Sons, Ltd., Chichester; B. G. Teubner, Stuttgart, 1987. MR**905473**

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/S0002-9939-1994-1198450-9

Article copyright:
© Copyright 1994
American Mathematical Society