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
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