nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Newton Series, Coinductively

verfasst von : Henning Basold, Helle Hvid Hansen, Jean-Éric Pin, Jan Rutten

Erschienen in: Theoretical Aspects of Computing - ICTAC 2015

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel On Probabilistic Distributed Strategies

Nächstes Kapitel Quotienting the Delay Monad by Weak Bisimilarity

Barbosa, L.: Components as coalgebras. Ph.D. thesis, Universidade do Minho, Braga, Portugal (2001)

Bergstra, J., Klop, J.W.: Process algebra for synchronous communication. Inf. Control 60(1), 109–137 (1984)MathSciNetCrossRefMATH

Berstel, J., Reutenauer, C.: Rational Series and Their Languages. EATCS Monographs on Theoretical Computer Science, vol. 12. Springer, Heidelberg (1988)CrossRefMATH

Bonchi, F., Pous, D.: Hacking nondeterminism with induction and coinduction. Commun. ACM 58(2), 87–95 (2015)CrossRef

Burns, S.A., Palmore, J.I.: The newton transform: an operational method for constructing integral of dynamical systems. Physica D Nonlinear Phenom. 37(1–3), 83–90 (1989)MathSciNetCrossRefMATH

Chen, K., Fox, R., Lyndon, R.: Free differential calculus, IV - the quotient groups of the lower series. Ann. Math. Second Ser. 68(1), 81–95 (1958)MathSciNetCrossRefMATH

Conway, J.: Regular Algebra and Finite Machines. Chapman and Hall, London (1971)MATH

Eilenberg, S.: Automata, Languages and Machines. Pure and Applied Mathematics, vol. A. Academic Press, London (1974)

Graham, R., Knuth, D., Patashnik, O.: Concrete Mathematics, 2nd edn. Addison-Wesley, Reading (1994) MATH

10.

Hansen, H.H., Kupke, C., Rutten, J.: Stream differential equations: specification formats and solution methods. Report FM-1404, CWI (2014). www.cwi.nl

11.

Lothaire, M.: Combinatorics on Words. Cambridge Mathematical Library. Cambridge University Press, Cambridge (1997) CrossRefMATH

12.

Pavlovic, D., Escardó, M.: Calculus in coinductive form. In: Proceedings of the 13th Annual IEEE Symposium on Logic in Computer Science, pp. 408–417. IEEE Computer Society Press (1998)

13.

Pin, J.É.: Newton’s forward difference equation for functions from words to words. In: Beckmann, A., Mitrana, V., Soskova, M. (eds.) CiE 2015. LNCS, vol. 9136, pp. 71–82. Springer, Heidelberg (2015)CrossRef

14.

Pin, J.E., Silva, P.V.: A noncommutative extension of Mahler’s theorem on interpolation series. Eur. J. Comb. 36, 564–578 (2014)MathSciNetCrossRefMATH

15.

Rot, J., Bonsangue, M., Rutten, J.: Coalgebraic bisimulation-Up-To. In: van Emde Boas, P., Groen, F.C.A., Italiano, G.F., Nawrocki, J., Sack, H. (eds.) SOFSEM 2013. LNCS, vol. 7741, pp. 369–381. Springer, Heidelberg (2013) CrossRef

16.

Rutten, J.: Universal coalgebra: a theory of systems. Theor. Comput. Sci. 249(1), 3–80 (2000). Fundamental StudyMathSciNetCrossRefMATH

17.

Rutten, J.: Behavioural differential equations: a coinductive calculus of streams, automata, and power series. Theor. Comput. Sci. 308(1), 1–53 (2003). Fundamental StudyMathSciNetCrossRefMATH

18.

Rutten, J.: A coinductive calculus of streams. Math. Struct. Comput. Sci. 15, 93–147 (2005)MathSciNetCrossRefMATH

19.

Scheid, F.: Theory and Problems Of Numerical Analysis. Schaum’s outline series. McGraw-Hill, New York (1968) MATH

Titel: Newton Series, Coinductively
verfasst von: Henning Basold
Helle Hvid Hansen
Jean-Éric Pin
Jan Rutten
Verlag: Springer International Publishing
Buch: Theoretical Aspects of Computing - ICTAC 2015
Print ISBN: 978-3-319-25149-3

Electronic ISBN: 978-3-319-25150-9

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-25150-9_7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"