Polynomial hyperforms. (English) Zbl 0558.08003

Let V be a variety of algebras of type \(\Phi\), and let C be the set of operations obtainable by composition from the elements of \(\Phi\) and projections. C becomes a graded algebra with composition as a multi-ary operation. The author defines an n-ary clone term \(t=t(x_ 1,...,x_ n)\) as follows: the expression \(x_ i\) is an n-ary clone term for \(1\leq i\leq n\), if p is an m-ary operation symbol and \(t_ 1,...,t_ m\) are n- ary clone terms then the expression \(p(t_ 1,...,t_ m)\) is an n-ary clone term. By replacing each \(x_ i\) by the i-th projection and regarding the other operation symbols as variables, t may be thought of as a term in the first-order language of the theory of clones. An n-ary hyperform \(h=h(x_ 1,...,x_ n)\) is an n-ary clone term in which no operation symbol appears more than once. h is said to hold in a variety V if the sentence \[ \forall p\exists p_ 1,...,p_ k (p(x_ 1,...,x_ n)=h(x_ 1,...,x_ n)) \] holds in the clone of V, where \(p_ 1,...,p_ k\) are the opertion symbols appearing in h. Thus a hyperform is a sort of normal form for clone terms, bearing approximately the same relationship to ordinary normal forms that hyperidentities bear to ordinary identities. An example is the hyperform \(p_ 1(p_ 2(x_ 1,x_ 2),x_ 3)\) which holds in the theory of abelian groups, since any ternary polynomial can be formed by multiplying an appropriate polynomial in the first two variables by a power of the third variable. Of particular interest are hyperforms called compressions, designated \(c_{m,k,n}\) for \(0<m<k<n\) and defined as follows: \[ c_{m,k,n}=p_ 0(p_ 1(x_ 1,...,x_ k),p_ 2(x_ 1,...,x_ k),...,p_ m(x_ 1,...,x_ k),x_{k+1},x_{k+2},...,x_ n). \] The author now defines two hierarchies on varieties which will be linked with hyperforms in the first theorem. If V is a variety and X is a set, let \(F_ v(X)\) denote the V-free algebra generated by the elements of X. A variety V will be said to have the k-generation property if the following holds for any disjoint infinite sets X and Y: for any element b in \(F_ v(X\cup Y)\) there is a subset S of \(F_ v(X)\) of size at most k such that b is generated by \(S\cup F_ v(Y)\). The variety of abelian groups, for example, has the 1-generation property.
The second hierarchy is obtained by regarding a polynomial in an algebra as a value to be computed by a machine, which inputs the variables of the polynomial and acts on them by applying operations from the clone of the algebra. The machine involved is a slightly bizarre combination of simplicity and sophistication which we call a one-pass parallel processor. It has a finite number of registers \(r_ 1,...,r_ k\) each of which can hold an element of an algebra (in particular, of \(F_ v(X))\). The machine can be programmed to perform a fixed series of steps, each of which is either an input step or an operation step. The output of the program is defined to be the content of register \(r_ 1\) after the last step of the program. Each program thus defines a polynomial in its input arguments; the program is then said to compute that polynomial in parallel space k. This paper studies these concepts.
Reviewer: R.-A.Alo


08A40 Operations and polynomials in algebraic structures, primal algebras
20N15 \(n\)-ary systems \((n\ge 3)\)
68Q70 Algebraic theory of languages and automata
03G25 Other algebras related to logic
08B20 Free algebras
Full Text: DOI


[1] Trevor Evans,Properties of algebras almost equivalent to identities, J. London Math. Soc.35 (1962), 53-59. · Zbl 0109.01004
[2] GeorgeGratzer,Universal Algebra, Van Nostrand (1968).
[3] L. Klukovits,Hamiltonian varieties of universal algebras, Acta Sci. Math.37 (1975), 11-15. · Zbl 0285.08004
[4] Peter Winkler,Classification of algebraic structures by work space, Algebra Universalis11 (1980), 320-333. · Zbl 0455.08003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.