The behavior of corresponding deterministic and nondeterministic devices may be markedly different, and problems that are decidable for deterministic devices are frequently undecidable for nondeterministic devices. A nondeterministic process may also be viewed as a deterministic process with multiple possible outcomes. This notion is essentially a representation of formal power series (as in chapter 8 of Eilenberg [1]), but avoids much of the formalism of analysis. The author successfully develops the thesis that nondeterminism with multiplicities resembles determinism more closely than it does nondeterminism.

Four problems that may be considered as morphisms of free monoids are examined in each of three variants. A deterministic problem results when the codomain of the morphism is a free monoid; nondeterminism arises by mapping to the monoid of finite subsets of a free monoid; and mapping to a monoid of formal polynomials yields multiplicities. One problem considered is the Ehrenfeucht Problem of determining whether a test set exists for each language that would establish the equivalence of two arbitrary morphisms on that language. First posed in 1973, this question has been found to be true for the deterministic case and false for the nondeterministic case (with finite substitutions). The new result presented here shows that each regular language possesses a test set with respect to morphisms with multiplicities. Whether this result is also true for languages in general remains an open problem.

The author suggests, with some justification, that nondeterminism with multiplicities has many results that parallel determinism, and one example is given (deciding whether two multitape automata are equivalent) in which the study of multiplicity has led to the solution of a deterministic problem in automata theory. The paper includes a convenient table summarizing the present state of knowledge with respect to the problems under consideration, and provides a handy collection of references to work in the field.