Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-25T23:39:46.432Z 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: [email protected]
HELLE HVID HANSEN
Affiliation:
Delft University of Technology, P.O. Box 5015, 2600 GA Delft, The Netherlands. Email: [email protected]
JEAN-ÉRIC PIN
Affiliation:
Université Paris Denis Diderot and CNRS, 75205 Paris Cedex 13, France. Email: [email protected]
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: [email protected]
Get access Rights & Permissions [Opens in a new window]

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.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 29 , Special Issue 1: Special Issue: Best Papers Presented at ICTAC 2015 , January 2019 , pp. 38 - 66
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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