On transductions of formal power series over complete semirings (Q1194315): Difference between revisions

The article is devoted to the generalization of rational and pushdown transduction of formal languages to formal power series with coefficients in a complete semiring. A characterization similar to Nivat's Theorem is given [\textit{W. Kuich} and \textit{A. Salomaa}, Semirings, automata, languages (Springer, New York, 1986; Zbl 0582.68002)]. Commutativity requirements for the coefficients are especially studied. The nonnegative or reals are considered as coefficients, that enables to deal with multiplicities and probabilities, respectively, in the same notational framework. The authors present the basis of rational power series and (finite) rational transductions, without reference to a particular semiring. (To our knowledge, this is the first paper to deal with transduction of formal power series in a purely axiomatic framework.) They also introduce concepts for handling infinite transducers. In particular, they deal with pushdown transductions of formal power series and morphism. (A similar result is well-known for rational transductions of formal languages and is often referred to as ``Nivat's Theorem''. Its generalization to regulated pushdown transducers was presented by the author [Theor. Comput. Sci. 97, 245-262 (1992; Zbl 0769.68101)]).