Newton series, coinductively: a comparative study of composition

Henning Basold, Helle Hansen, Jean Éric Pin, Jan Rutten

Research output: Contribution to journalArticleScientificpeer-review

36 Downloads (Pure)

Abstract

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.

Original languageEnglish
Pages (from-to)1-29
Number of pages29
JournalMathematical Structures in Computer Science
DOIs
Publication statusPublished - Jun 2017

Fingerprint Dive into the research topics of 'Newton series, coinductively: a comparative study of composition'. Together they form a unique fingerprint.

  • Cite this