Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



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 $ {p_n}$-sequence $ \langle {p_0}(C),{p_1}(C), \ldots \rangle $, where $ {p_n}(C)$ 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 $ {p_n}$-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 $ {p_n}$-sequence and that it is decidable if a clone is totally symmetric.

References [Enhancements On Off] (What's this?)

  • [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 $ {p_n}$-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 $ {p_n}$-sequences of idempotent algebras are strictly increasing, Algebra Universalis 13 (1981), 233-250. MR 631559 (83i:08001)
  • [Ki1] -, The $ {p_n}$-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)

Similar Articles

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

Retrieve articles in all journals with MSC: 08A40

Additional Information

Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society