We introduce an algebraic approach to the foundations of data mining. Our approach is based upon two algebras of functions defined over a common state space X and a pairing between them. One algebra is an algebra of state space observations, and the other is an algebra of labeled sets of states. We interpret H as the algebraic encoding of the data and the pairing as the misclassification rate when the classifier f is applied to the set of states X. We give a realization theorem giving conditions on formal series of data sets built from D that imply there is a realization involving a state space X, a classifier f /spl isin/ R and a set of labeled states /spl chi/ /spl isin/ R/sub 0/ that yield this series.

The algorithms derived by Grossmann and Larson (1989) are further developed for rewriting expressions involving differential operators. The differential operators involved arise in the local analysis of nonlinear dynamical systems. These algorithms are extended in two different directions: the algorithms are generalized so that they apply to differential operators on groups and the data structures and algorithms are developed to compute symbolically the action of differential operators on functions. Both of these generalizations are needed for applications.

The effective parallel symbolic computation of operators under composition is discussed. Examples include differential operators under composition and vector fields under the Lie bracket. Data structures consisting of formal linear combinations of rooted labeled trees are discussed. A multiplication on rooted labeled trees is defined, thereby making the set of these data structures into an associative algebra. An algebra homomorphism is defined from the original algebra of operators into this algebra of trees. An algebra homomorphism from the algebra of trees into the algebra of differential operators is then described. The cancellation which occurs when noncommuting operators are expressed in terms of commuting ones occurs naturally when the operators are represented using this data structure. This leads to an algorithm which, for operators which are derivations, speeds up the computation exponentially in the degree of the operator. It is shown that the algebra of trees leads naturally to a parallel version of the algorithm.

Solovay and Strassen [SIAM J. Comput., 6 (1977), pp. 84–85] propose a primality test based on the fact that for primes $p > 2$ we have $(a/ p) \equiv a^{(p - 1)/2} (\bmod p)$, where $(a / p)$ is the Jacobi symbol. We prove here that the strong pseudoprime test is better, in the sense that it never takes more time nor is less effective, and sometimes is quicker or more effective. We also discuss the probability of error in the strong pseudoprime test, and show that it is never greater than $\tfrac{1}{4}$.

Under a virtual storage operating system, the time spent by a list processing language on garbage collection varies in a complex manner with the amount of memory allocated. This dependence is investigated and strategies for minimizing the time spent on garbage collection are given.

Two algorithms for computing the multiplication table of a 2-group are described and discussed. One of the algorithms works in an element-by-element fashion; the other works in terms of subgroups generated by initial subsequences of the given sequence of generators. Estimates of computation times are given which show that the second algorithm is much more efficient than the first. It is also shown how the second algorithm can be modified to make it more useful, without using significantly more time.