nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Tropical Abstractions of Max-Plus Linear Systems

verfasst von : Muhammad Syifa’ul Mufid, Dieky Adzkiya, Alessandro Abate

Erschienen in: Formal Modeling and Analysis of Timed Systems

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

This paper describes the development of finite abstractions of Max-Plus-Linear (MPL) systems using tropical operations. The idea of tropical abstraction is inspired by the fact that an MPL system is a discrete-event model updating its state with operations in the tropical algebra. The abstract model is a finite-state transition system: we show that the abstract states can be generated by operations on the tropical algebra, and that the generation of transitions can be established by tropical multiplications of matrices. The complexity of the algorithms based on tropical algebra is discussed and their performance is tested on a numerical benchmark against an existing alternative abstraction approach.

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 Safe Over- and Under-Approximation of Reachable Sets for Autonomous Dynamical Systems

A permutation \(\alpha \) is called maximal if \(\bigotimes _{i=1}^n A(i,\alpha (i))=\text {per}(A)\), where \(\text {per}(A)\) is the permanent of A [6, 17].

\(\hat{R}\) is the collection of non-empty \(R_g\). We use small letter \(\hat{r}_i\) for sake of simplicity.

Adzkiya, D.: Finite abstractions of max-plus-linear systems: theory and algorithms. Ph.D. thesis, Delft University of Technology (2014)

Adzkiya, D., Abate, A.: VeriSiMPL: verification via biSimulations of MPL models. In: Joshi, K., Siegle, M., Stoelinga, M., D’Argenio, P.R. (eds.) QEST 2013. LNCS, vol. 8054, pp. 274–277. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40196-1_22CrossRef

Adzkiya, D., De Schutter, B., Abate, A.: Finite abstractions of max-plus-linear systems. IEEE Trans. Autom. Control 58(12), 3039–3053 (2013)MathSciNetCrossRef

Adzkiya, D., De Schutter, B., Abate, A.: Computational techniques for reachability analysis of max-plus-linear systems. Automatica 53, 293–302 (2015)MathSciNetCrossRef

Baccelli, F., Cohen, G., Olsder, G.J., Quadrat, J.-P.: Synchronization and Linearity: An Algebra for Discrete Event Systems. Wiley, Hoboken (1992)MATH

Butkovič, P.: Max-algebra: the linear algebra of combinatorics? Linear Algebra Appl. 367, 313–335 (2003)MathSciNetCrossRef

Dill, D.L.: Timing assumptions and verification of finite-state concurrent systems. In: Sifakis, J. (ed.) CAV 1989. LNCS, vol. 407, pp. 197–212. Springer, Heidelberg (1990). https://doi.org/10.1007/3-540-52148-8_17CrossRef

Floyd, R.W.: Algorithm 97: shortest path. Commun. ACM 5(6), 345 (1962)CrossRef

Heemels, W., De Schutter, B., Bemporad, A.: Equivalence of hybrid dynamical models. Automatica 37(7), 1085–1091 (2001)CrossRef

10.

Heidergott, B., Olsder, G.J., Van der Woude, J.: Max Plus at Work: Modeling and Analysis of Synchronized Systems: A Course on Max-Plus Algebra and Its Applications. Princeton University Press, Princeton (2014)

11.

Itenberg, I., Mikhalkin, G., Shustin, E.I.: Tropical Algebraic Geometry, vol. 35. Springer, Basel (2009). https://doi.org/10.1007/978-3-0346-0048-4CrossRefMATH

12.

Lu, Q., Madsen, M., Milata, M., Ravn, S., Fahrenberg, U., Larsen, K.G.: Reachability analysis for timed automata using max-plus algebra. J. Logic Algebraic Program. 81(3), 298–313 (2012)MathSciNetCrossRef

13.

Mufid, M.S., Adzkiya, D., Abate, A.: Tropical abstractions of max-plus-linear systems (2018). arXiv:1806.04604

14.

Péron, M., Halbwachs, N.: An abstract domain extending difference-bound matrices with disequality constraints. In: Cook, B., Podelski, A. (eds.) VMCAI 2007. LNCS, vol. 4349, pp. 268–282. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-69738-1_20CrossRefMATH

15.

Pin, J.-E.: Tropical semirings. Idempotency, pp. 50–69 (1998)

16.

Richards, A.: University of Oxford Advanced Research Computing (2015). Zenodo. https://doi.org/10.5281/zenodo.22558

17.

Sergeev, S.: Max-plus definite matrix closures and their eigenspaces. Linear Algebra Appl. 421(2–3), 182–201 (2007)MathSciNetCrossRef

Titel: Tropical Abstractions of Max-Plus Linear Systems
verfasst von: Muhammad Syifa’ul Mufid
Dieky Adzkiya
Alessandro Abate
Verlag: Springer International Publishing
Buch: Formal Modeling and Analysis of Timed Systems
Print ISBN: 978-3-030-00150-6

Electronic ISBN: 978-3-030-00151-3

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-00151-3_16

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"