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] 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 $ {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
  • [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

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