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

DOI:
https://doi.org/10.1090/S0002-9939-1994-1198450-9

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]**-,*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*, McGraw-Hill, New York, 1978. MR**0497337 (58:15709)****[DK]**J. Dudek and A. Kisielewicz,*Totally commutative semigroups*, J. Austral. Math. Soc. Ser. A**51**(1991), 381-399. 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. 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 (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]**M. Harrison,*Introduction to switching and automata theory*, McGraw-Hill, 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), 233-250. MR**631559 (83i:08001)****[Ki1]**-,*The*-*sequences of idempotent algebras are strictly increasing*. II, Algebra Universalis**28**(1991), 453-458. MR**1128383 (92m:08010)****[Ko]**K. M. Koh,*Idempotent algebras with one essentially binary polynomial*, Nanyang Univ. J.**6**(1972), 18-27. MR**0419333 (54:7355)****[LL]**S. C. Lee and E. T. Lee,*On multivalued symmetric functions*, IEEE Trans. Comput.**C-21**(1972), 312-317. 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 two-valued 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 multiple-valued logic algebras*, Computer Science and Multiple-Valued Logic, Theory and Applications, North-Holland, Amsterdam, 1977, pp. 144-186.**[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 many-valued logics*, Note on Multiple-Valued Logic in Japan**6**(1986), 1-26.**[T]**W. Taylor,*Equational logic*, Houston J. Math., Special Survey Issue, 1979. Abridged version in G. Grätzer,*Universal algebra*, 2nd ed., Springer-Verlag, Berlin and New York, 1979. MR**546853 (80j:03042)****[U]**K. Urbanik,*Remarks on symmetrical operations*, Colloq. Math.**15**(1966), 1-9. MR**0194379 (33:2589)****[W]**I. Wegner,*The complexity of Boolean functions*, Wiley, New York, 1987. MR**905473 (89b:03066)**

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
08A40

Retrieve articles in all journals with MSC: 08A40

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1994-1198450-9

Article copyright:
© Copyright 1994
American Mathematical Society