Safety Verification of Uncertain Max-Plus-Linear Systems

Aditya Putra Pratama, Subchan Subchan, Dieky Adzkiya


In this work, we discussed the verification of autonomous uncertain Max-Plus-Linear (uncertain MPL) systems with respect to safety property by using the reachability analysis approach. More precisely, given an uncertain MPL system, a nonempty set of initial conditions, a time horizon and an unsafe set, we want to determine whether the state can reach the unsafe set within the given time horizon. If the unsafe set is reachable, then the system is not safe. Otherwise, the system is safe. Our approach uses the piecewise affine representation of MPL systems to compute the reachable sets exactly.


Max-Plus Algebra; Reachability Analysis Approach; Safety Verification; Uncertain Systems

Full Text:



F. Baccelli, G. Cohen, G. J. Olsder, and J.-P. Quadrat, Synchronization and linearity: an algebra for discrete event systems. John Wiley & Sons Ltd, 1992.

B. Heidergott, G. J. Olsder, and J. Van der Woude, Max Plus at work: modeling and analysis of synchronized systems: a course on Max-Plus algebra and its applications. Princeton University Press, 2014.

D. Adzkiya, B. De Schutter, and A. Abate, “Finite abstractions of max-plus-linear systems.” IEEE Trans. Automat. Contr., vol. 58, no. 12, pp. 3039–3053, 2013.

D. Adzkiya, B. De Schutter, and A. Abate, “Computational techniques for reachability analysis of max-pluslinear systems,” Automatica, vol. 53, pp. 293–302, 2015.

R. M. F. Candido, L. Hardouin, M. Lhommeau, and R. S. Mendes, “Conditional reachability of uncertain max plus linear systems,” Automatica, vol. 94, pp. 426–435, 2018.

D. Adzkiya, Y. Zhang, and A. Abate, “Verisimpl 2: An open-source software for the verification of max-plus-linear systems,” Discrete Event Dynamic Systems, vol. 26, no. 1, pp. 109–145, 2016.

W. Heemels, B. De Schutter, and A. Bemporad, “Equivalence of hybrid dynamical models,” Automatica, vol. 37, no. 7, pp. 1085–1091, 2001.



  • There are currently no refbacks.

View My Stats

Creative Commons License
International Journal of Computing Science and Applied Mathematics by Department Mathematics ITS is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Based on a work at