This paper presents a series of interrelated results on classes of formal power series that are generated by various types of weighted finite automata. In the early 1960s, Schützenberger initiated the idea of studying rational languages in terms of matrices over semirings. Several studies in this area, including Kuich and Salomaa’s book [1], are, curiously, not cited by the authors. A possible explanation for this is the authors’ concentration on and . This paper is a valuable contribution to the linear algebra approach to formal languages.

Although the authors’ stated goal is to provide a unified account of this field (which is largely achieved) for use in grammatical inference research, there are numerous main results and technical propositions that are useful for other formal language investigations. A distinguishing feature of the exposition is the frequent employment of genuinely illustrative examples. Both its design and content lead me to recommend this paper to a wide range of theorists.

The paper contains several tables and summaries that the interested reader can consult directly, so I will not attempt to present them here. It should be noted that the terminology in this field is not entirely standard. For example, weighted finite automata, as defined by Kuich and Salomaa [1], are referred to as multiplicity automata in this paper, with other automata being variants of the classical stochastic automaton, dating back to Rabin and Paz in the 1960s.

Several results concerning equivalence/inequivalence are established. Considerable space is devoted to the residual formal series u^{-1} ... p of a stochastic formal series p. This is defined by (recall we work over at least u^{-1} ... p(w) = p(uw)/p(u&Sgr;^*), where, as usual, &Sgr; is a finite alphabet. The residual can be thought of as a normalization with regard to u for p in terms of the weight assigned by p to all words u&Sgr;^*. The algebraic significance of the residual is brought out in terms of finite generation results. There are also decidability results, both positive and negative, which are in part associated with finite generation. In the same spirit, some PTIME automaton representability algorithms and one PSPACE completeness theorem are given.

Fatou results are also presented. Several of these deal with when a series with all of its coefficients in (the positive sub-semiring of ) can be generated by matrices in .

Finally, I can’t resist mentioning one of the technical results in the paper that undoubtedly will find use in other applications:

Lemma 1: Let f : be a linear mapping and let such that converges to u. Then u .