Newton series,
coinductively: a comparative study of composition
Henning Basold, Helle Hvid Hansen, Jean-Éric Pin, Jan Rutten
Résumé :
Nous présentons une étude comparative de quatre opérateurs de produits sur
les langages: la convolution, le mélange, le produit d'infiltration et le
produit de Hadamard. Exploitant le fait que l'ensemble des langages est une
coalgèbre finale, nous utilisons la coinduction pour prouver qu'un
opérateur du calcul classique des différences, la transformée de Newton,
généralise des suites infinies aux langages pondérés. Nous montrons que la
transformée de Newton est un isomorphisme d'anneau qui transforme le
produit de Hadamard de deux langages pondérés dans leur produit
d'infiltration, et nous développons diverses représentations pour la
transformation de Newton d'un langage, ainsi que des règles de calcul
concrètes pour les calculer.
Abstract :
We present a comparative study of four product operators on weighted
languages: (i) the convolution, (ii) the shuffle product, (iii) the
infiltration product, and (iv) the Hadamard product. Exploiting the fact
that the set of weighted languages is a final coalgebra, we use coinduction
to prove that an operator of the classical difference calculus, the Newton
transform, generalises from infinite sequences to weighted languages. We
show that the Newton transform is an isomorphism of rings that transforms
the Hadamard product of two weighted languages into their infiltration
product, and we develop various representations for the Newton transform of
a language, together with concrete calculation rules for computing them.