ON META.NORMAL FORMS FOR ALGEBRAIC POWER SERIES IN NONCOMMUTING VARIABLES

1. Introiluction and preliminaries. The theory of formal power series in non-commuting variables was initiated around 1960 apart from some scattered work done earlier in connection with free groups. Such power series are applicable in a number of areas but, in particular, they have turned out to be an indispensable tool in automata and language theory. Their usefulness in the latter theories is due to the fact that, in a sense, they lead to the arithmetization of the theory. The purpose of this paper is to establish classes of normal forms for algebraic power series. The normal forms, as well as the definition of algebraic power series in general, are closely connected with the corresponding questions dealing with context-free grammars. In fact, one of the most important open problems concerns the possibility of extending the "terminally balanced " normal form beyond the Boolean semiring. (It is well known how the theory of power series over the Boolean semiring is isomorphic, in a well-defined sense, to language theory.) The reader is referred to [11] for motivation and background material, as wel