Hostname: page-component-6898cfcb55-zsp5v Total loading time: 0 Render date: 2026-11-11T10:41:53.377Z Has data issue: false hasContentIssue false
  • English
  • Français

Newton series, coinductively: a comparative study of composition

Published online by Cambridge University Press:  07 June 2017

HENNING BASOLD,
HELLE HVID HANSEN,
JEAN-ÉRIC PIN and
JAN RUTTEN
HENNING BASOLD
Affiliation:
Radboud University Nijmegen, P.O. Box 9010, 6500GL Nijmegen, The Netherlands, and CWI Amsterdam, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands. Email: h.basold@cs.ru.nl
HELLE HVID HANSEN
Affiliation:
Delft University of Technology, P.O. Box 5015, 2600 GA Delft, The Netherlands. Email: h.h.hansen@tudelft.nl
JEAN-ÉRIC PIN
Affiliation:
Université Paris Denis Diderot and CNRS, 75205 Paris Cedex 13, France. Email: Jean-Eric.Pin@liafa.univ-paris-diderot.fr
JAN RUTTEN
Affiliation:
CWI Amsterdam, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands, and Radboud University Nijmegen, P.O. Box 9010, 6500GL Nijmegen, The Netherlands. Email: jjmmrutten@gmail.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

References

Barbosa, L. (2001). Components as Coalgebras. PhD thesis, Universidade do Minho, Braga, Portugal.Google Scholar
Bartels, F. (2004). On Generalised Coinduction and Probabilistic Specification Formats. PhD thesis, Vrije Universiteit, Amsterdam.Google Scholar
Basold, H., Hansen, H.H., Pin, J.-E. and Rutten, J.J.M.M. (2015). Newton series, coinductively. In: Leucker, M., Rueda, C. and Valencia, F.D. (eds.) Theoretical Aspects of Computing – ICTAC 2015, Lecture Notes in Computer Science, vol. 9399, Springer, 91–109.Google Scholar
Bergeron, F., Labelle, G. and Leroux, P. (1998). Combinatorial Species and Tree-like Structures, Encyclopedia of Mathematics and its Applications, vol. 67. Cambridge University Press.Google Scholar
Bergstra, J. and Klop, J.W. (1984). Process algebra for synchronous communication. Information and Control 60 (1) 109–137.Google Scholar
Berstel, J. and Reutenauer, C. (1988). Rational Series and their Languages, EATCS Monographs on Theoretical Computer Science, vol. 12, Springer-Verlag.Google Scholar
Bonchi, F. and Pous, D. (2015). Hacking nondeterminism with induction and coinduction. Communications of the ACM 58 (2) 87–95.Google Scholar
Burns, S.A. and Palmore, J.I. (1989). The newton transform: An operational method for constructing integral of dynamical systems. Physica D: Nonlinear Phenomena 37 (13) 83–90. ISSN .Google Scholar
Chen, K., Fox, R. and Lyndon, R. (1958). Free differential calculus, IV – The quotient groups of the lower series. Annals of Mathemathics. Second Series 68 (1) 81–95.Google Scholar
Comtet, L. (1974). Advanced Combinatorics, D. Reidel Publishing Company.Google Scholar
Conway, J.H. (1971). Regular Algebra and Finite Machines, Chapman and Hall.Google Scholar
Eilenberg, S. (1974). Automata, Languages and Machines (Vol. A). Pure and Applied Mathematics. Academic Press.Google Scholar
Graham, R.L., Knuth, D.E. and Patashnik, O. (1994). Concrete Mathematics, 2nd edition, Addison-Wesley.Google Scholar
Hansen, H.H., Kupke, C. and Rutten, J.J.M.M. (2014). Stream differential equations: Specification formats and solution methods. Report FM-1404, CWI. Available at: www.cwi.nl.Google Scholar
Lothaire, M. (1997). Combinatorics on Words, Cambridge Mathematical Library, Cambridge University Press.Google Scholar
Niqui, M. and Rutten, J.J.M.M. (2011). A proof of Moessner's theorem by coinduction. Higher-Order and Symbolic Computation 24 (3) 191–206.Google Scholar
Pavlović, D. and Escardó, M. (1998). Calculus in coinductive form. In: Proceedings of the 13th Annual IEEE Symposium on Logic in Computer Science, IEEE Computer Society Press, 408–417.Google Scholar
Pin, J.-E. (2015). Newton's forward difference equation for functions from words to words. In: Proceedings of the Evolving Computability – 11th Conference on Computability in Europe, CiE 2015, Bucharest, Romania, 71–82. Available at: http://dx.doi.org/10.1007/978-3-319-20028-6_8.Google Scholar
Pin, J.E. and Silva, P.V. (2014). A noncommutative extension of Mahler's theorem on interpolation series. European Journal of Combinatorics 36 564–578.Google Scholar
Rot, J. (2015). Enhanced Coinduction. Phd, University Leiden, Leiden.Google Scholar
Rot, J., Bonsangue, M.M. and Rutten, J.J.M.M. (2013). Coalgebraic bisimulation-up-to. In: SOFSEM, Lecture Notes in Computer Science, vol. 7741, Springer, 369–381.Google Scholar
Rutten, J.J.M.M. (2000). Universal coalgebra: A theory of systems. Theoretical Computer Science 249 (1) 3–80.Google Scholar
Rutten, J.J.M.M. (2003a). Coinductive counting with weighted automata. Journal of Automata, Languages and Combinatorics 8 (2) 319–352.Google Scholar
Rutten, J.J.M.M. (2003b). Behavioural differential equations: A coinductive calculus of streams, automata, and power series. Theoretical Computer Science 308 (1) 1–53.Google Scholar
Rutten, J.J.M.M. (2005). A coinductive calculus of streams. Mathematical Structures in Computer Science 15 93–147.Google Scholar
Scheid, F. (1968). Theory and Problems of Numerical Analysis (Schaum's outline series), McGraw-Hill.Google Scholar