Skip to Main Content

Proceedings of the American Mathematical Society

Published by the American Mathematical Society since 1950, Proceedings of the American Mathematical Society is devoted to shorter research articles in all areas of pure and applied mathematics.

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

The 2020 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

On the number of operations in a clone
HTML articles powered by AMS MathViewer

by Joel Berman and Andrzej Kisielewicz PDF
Proc. Amer. Math. Soc. 122 (1994), 359-369 Request permission

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
    J. Berman, Lecture notes: Free spectra of finite algebras, manuscript, April, 1986.
  • Joel Berman, On the combinatorics of free algebras, Lattices, semigroups, and universal algebra (Lisbon, 1988) Plenum, New York, 1990, pp. 13–19. MR 1085062
  • 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
  • Józef Dudek and Andrzej Kisielewicz, Totally commutative semigroups, J. Austral. Math. Soc. Ser. A 51 (1991), no. 3, 381–399. MR 1125441
  • 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
    • 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.
  • 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 256969
  • 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 294216, DOI 10.4064/cm-22-1-9-11
  • Michael A. Harrison, Introduction to switching and automata theory, McGraw-Hill Book Co., New York-Toronto-London, 1965. MR 0186503
  • David Hobby and Ralph McKenzie, The structure of finite algebras, Contemporary Mathematics, vol. 76, American Mathematical Society, Providence, RI, 1988. MR 958685, DOI 10.1090/conm/076
  • A. Kisielewicz, The $p_{n}$-sequences of idempotent algebras are strictly increasing, Algebra Universalis 13 (1981), no. 2, 233–250. MR 631559, DOI 10.1007/BF02483837
  • Andrzej Kisielewicz, The $p_n$-sequences of idempotent algebras are strictly increasing. II, Algebra Universalis 28 (1991), no. 4, 453–458. MR 1128383, DOI 10.1007/BF01195856
  • K. M. Koh, Idempotent algebras with one essentially binary polynomial, Nanyang Univ. J. Part III 6 (1972), 18–27 (English, with Chinese summary). MR 419333
  • Samuel C. Lee and Edward T. Lee, On multivalued symmetric functions, IEEE Trans. Comput. C-21 (1972), 312–317. MR 321350, DOI 10.1109/tc.1972.5008957
  • 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
  • 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
    • 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.
  • Á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
    • I. Stojmenović and M. Miyakawa, Symmetric functions in many-valued logics, Note on Multiple-Valued Logic in Japan 6 (1986), 1-26.
  • Walter Taylor, Equational logic, Houston J. Math. Survey (1979), iii+83. MR 546853
  • K. Urbanik, Remarks on symmetrical operations, Colloq. Math. 15 (1966), 1–9. MR 194379, DOI 10.4064/cm-15-1-1-9
  • 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
  • © Copyright 1994 American Mathematical Society
  • 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