TY - JOUR
T1 - Newton series, coinductively
T2 - a comparative study of composition
AU - Basold, Henning
AU - Hansen, Helle
AU - Pin, Jean Éric
AU - Rutten, Jan
PY - 2017
Y1 - 2017
N2 - We present a comparative study of four product operators on weighted languages: (i) the convolution, (ii) the shuffle, (iii) the infiltration 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.
AB - We present a comparative study of four product operators on weighted languages: (i) the convolution, (ii) the shuffle, (iii) the infiltration 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.
UR - http://resolver.tudelft.nl/uuid:58298d28-37bd-4b94-bf2d-1bf59a86e23e
UR - http://www.scopus.com/inward/record.url?scp=85020305083&partnerID=8YFLogxK
U2 - 10.1017/S0960129517000159
DO - 10.1017/S0960129517000159
M3 - Article
AN - SCOPUS:85020305083
SN - 0960-1295
SP - 1
EP - 29
JO - Mathematical Structures in Computer Science
JF - Mathematical Structures in Computer Science
ER -