Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Coherence Spaces and Uniform Continuity Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

Algebra, Coalgebra, and Minimization in Polynomial Differential Equations

verfasst von : Michele Boreale

Erschienen in: Foundations of Software Science and Computation Structures

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

We consider reasoning and minimization in systems of polynomial ordinary differential equations (odes). The ring of multivariate polynomials is employed as a syntax for denoting system behaviours. We endow polynomials with a transition system structure based on the concept of Lie derivative, thus inducing a notion of https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-54458-7_5/445779_1_En_5_IEq1_HTML.gif -bisimulation. Two states (variables) are proven https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-54458-7_5/445779_1_En_5_IEq2_HTML.gif -bisimilar if and only if they correspond to the same solution in the odes system. We then characterize https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-54458-7_5/445779_1_En_5_IEq3_HTML.gif -bisimilarity algebraically, in terms of certain ideals in the polynomial ring that are invariant under Lie-derivation. This characterization allows us to develop a complete algorithm, based on building an ascending chain of ideals, for computing the largest https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-54458-7_5/445779_1_En_5_IEq4_HTML.gif -bisimulation containing all valid identities that are instances of a user-specified template. A specific largest https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-54458-7_5/445779_1_En_5_IEq5_HTML.gif -bisimulation can be used to build a reduced system of odes, equivalent to the original one, but minimal among all those obtainable by linear aggregation of the original equations.

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 Almost Every Simply Typed -Term Has a Long -Reduction Sequence
Nächstes Kapitel Equational Theories of Abnormal Termination Based on Kleene Algebra
Fußnoten
1
Vector means column vector, unless otherwise specified.
 
2
Equivalently, \({{\mathcal {A}}}\) is the set of power series \(f(t)=\sum _{j\ge 0}a_j t^j\) with a positive radius of convergence.
 
3
Existence of a morphism is not guaranteed, though. In this sense, \(C_{\mathrm {an}}\) is not final.
 
4
Differently from Sankaranarayanan et al. we do not allow linear expressions with a constant term, such as \(2+5a_1 +42a_2-3a_3\). This minor syntactic restriction does not practically affect the expressiveness of the resulting polynomial templates.
 
5
E.g., if for \(\pi =a_1x+a_2y+a_3x+a_4w\) and \({{\mathbf {x}}}_0=(0,0,1,1)^T\), \(\pi [v]({{\mathbf {x}}}_0)=0\) is resolved by the substitution \([a_3\mapsto -a_4]\).
 
6
The restriction that linear expressions in templates do not contain constant terms is crucial here.
 
7
Python code available at http://​local.​disia.​unifi.​it/​boreale/​papers/​DoubleChain.​py. Reported execution times relative to the pypy interpreter under Windows 8 on a core i5 machine.
 
8
At least for linear vector fields, the resulting weighted automaton is finite.
 
9
Checked with the Erode tool by the same authors [14].
 
Literatur
1.
Antoulas, A.C.: Approximation of Large-scale Dynamical Systems. SIAM, Philadelphia (2005)CrossRefMATH
2.
Arnold, V.I.: Ordinary Differential Equations. The MIT Press, Cambridge (1978). ISBN 0-262-51018-9
3.
4.
Blinov, M.L., Faeder, J.R., Goldstein, B., Hlavacek, W.S.: BioNet-Gen: software for rule-based modeling of signal transduction based on the interactions of molecular domains. Bioinformatics 20(17), 3289–3291 (2004)CrossRef
5.
Bonchi, F., Bonsangue, M.M., Boreale, M., Rutten, J.J.M.M., Silva, A.: A coalgebraic perspective on linear weighted automata. Inf. Comput. 211, 77–105 (2012)MathSciNetCrossRefMATH
6.
7.
8.
9.
Cachera, D., Jensen, T., Jobin, A., Kirchner, F.: Inference of polynomial invariants for imperative programs: a farewell to Gröbner bases. In: Miné, A., Schmidt, D. (eds.) SAS 2012. LNCS, vol. 7460, pp. 58–74. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-33125-1_​7 CrossRef
10.
11.
Cardelli, L., Tribastone, M., Tschaikowski, M., Vandin, A.: Symbolic computation of differential equivalences. In: POPL (2016)
12.
Cardelli, L., Tribastone, M., Tschaikowski, M., Vandin, A.: Efficient syntax-driven lumping of differential equations. In: Chechik, M., Raskin, J.-F. (eds.) TACAS 2016. LNCS, vol. 9636, pp. 93–111. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49674-9_​6 CrossRef
13.
Cardelli, L., Tribastone, M., Tschaikowski, M., Vandin, A., Networks, comparing chemical reaction : a categorical and algorithmic perspective. In: LICS (2016, to appear)
14.
15.
Ciocchetta, F., Hillston, J.: Bio-PEPA: a framework for the modelling and analysis of biological systems. Theor. Comput. Sci. 410(33–34), 3065–3084 (2009)MathSciNetCrossRefMATH
16.
Cox, D., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms An Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics. Springer, New York (2007)MATH
17.
Fliess, M., Reutenauer, C.: Theorie de Picard-Vessiot des Systèmes Reguliers. Colloque Nat. CNRS-RCP567, Belle-ile sept. in Outils et Modèles Mathématiques pour l’Automatique l’Analyse des systèmes et le tratement du signal. CNRS, 1983 (1982)
18.
19.
Li, G., Rabitz, H., Tóth, J.: A general analysis of exact nonlinear lumping in chemical kinetics. Chem. Eng. Sci. 49(3), 343–361 (1994)CrossRef
20.
21.
Okino, M.S., Mavrovouniotis, M.L.: Simplification of mathematical models of chemical reaction systems. Chem. Rev. 2(98), 391–408 (1998)CrossRef
22.
23.
Platzer, A.: Logics of dynamical systems. In: LICS, pp. 13–24. IEEE (2012)
24.
Rodríguez-Carbonell, E., Kapur, D.: Generating all polynomial invariants in simple loops. J. Symb. Comput. 42(4), 443–476 (2007)MathSciNetCrossRefMATH
25.
Rutten, J.J.M.M.: Behavioural differential equations: a coinductive calculus of streams, automata, and power series. Theor. Comput. Sci. 308(1–3), 1–53 (2003)MathSciNetCrossRefMATH
26.
Sangiorgi, D.: Beyond bisimulation: the “up-to” techniques. In: Boer, F.S., Bonsangue, M.M., Graf, S., Roever, W.-P. (eds.) FMCO 2005. LNCS, vol. 4111, pp. 161–171. Springer, Heidelberg (2006). doi:10.​1007/​11804192_​8 CrossRef
27.
Sankaranarayanan, S., Sipma, H., Manna, Z.: Non-linear loop invariant generation using Gröbner bases. In: POPL (2004)
28.
Sankaranarayanan, S.: Automatic invariant generation for hybrid systems using ideal fixed points. In: HSCC 2010, pp. 221–230 (2010)
29.
30.
Tóth, J., Li, G., Rabitz, H., Tomlin, A.S.: The effect of lumping and expanding on kinetic differential equations. SIAM J. Appl. Math. 57(6), 1531–1556 (1997)MathSciNetCrossRefMATH
31.
Tribastone, M., Gilmore, S., Hillston, J.: Scalable differential analysis of process algebra models. IEEE Trans. Softw. Eng. 38(1), 205–219 (2012)CrossRef
32.
Metadaten
Titel
Algebra, Coalgebra, and Minimization in Polynomial Differential Equations
verfasst von
Michele Boreale
Copyright-Jahr
2017
Verlag
Springer Berlin Heidelberg
Buch
Foundations of Software Science and Computation Structures

Print ISBN: 978-3-662-54457-0

Electronic ISBN: 978-3-662-54458-7

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-662-54458-7_5

Premium Partner

    Bildnachweise