Object Oriented Design of Software Tool for Finite Abstractions of Max-Plus-Linear Systems using Unified Modeling Language

Muhammadun Muhammadun, Dieky Adzkiya, Imam Mukhlash


Max-Plus-Linear (MPL) systems are a class of discrete-event systems with a continuous state space characterizing the timing of the underlying sequential discrete events. There is a formal approach to analyze these systems based on finite abstractions. The abstraction algorithms have been in MATLAB using list data structure and in JAVA using tree data structure. The MATLAB implementation requires long computational time, whereas the JAVA one requires larger memory allocation. In this work, we discuss an object oriented design in C++ using tree data structure without recursive functions in the hope of improving the results obtained by the two previous implementations.


Finite abstractions; max-plus-linear systems; object oriented design; unified modeling language

Full Text:



F. Baccelli, G. Cohen, G. Olsder, and J.-P. Quadrat, Synchronization and Linearity, An Algebra for Discrete Event Systems. John Wiley and Sons, 1992.

B. Heidergott, G. 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, 2006.

B. Roset, H. Nijmeijer, J. van Eekelen, E. Lefeber, and J. Rooda, “Event driven manufacturing systems as time domain control systems,” in Proc. 44th IEEE Conf. Decision and Control and European Control Conf. (CDC-ECC’05), Dec. 2005, pp. 446–451.

J. van Eekelen, E. Lefeber, and J. Rooda, “Coupling event domain and time domain models of manufacturing systems,” in Proc. 45th IEEE Conf. Decision and Control (CDC’06), Dec. 2006, pp. 6068–6073.

C. A. Brackley, D. S. Broomhead, M. C. Romano, and M. Thiel, “A maxplus model of ribosome dynamics during mRNA translation,” Journal of Theoretical Biology, vol. 303, no. 0, pp. 128–140, Jun. 2012.

S. Gaubert and R. Katz, “Reachability and invariance problems in maxplus algebra,” in Positive Systems, ser. Lecture Notes in Control and Information Science, L. Benvenuti, A. De Santis, and L. Farina, Eds. Springer, Heidelberg, Apr. 2003, vol. 294, ch. 4, pp. 15–22.

R. D. Katz, “Max-plus (A;B)-invariant spaces and control of timed discrete-event systems,” IEEE Trans. Autom. Control, vol. 52, no. 2, pp. 229–241, Feb. 2007.

B. De Schutter, “On the ultimate behavior of the sequence of consecutive powers of a matrix in the max-plus algebra,” Linear Algebra and its Applications, vol. 307, no. 1-3, pp. 103–117, Mar. 2000.

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

C. Baier and J.-P. Katoen, Principles of Model Checking. The MIT Press, 2008.

D. Adzkiya and A. Abate, “VeriSiMPL: Verification via biSimulations of MPL models,” in Proc. 10th Int. Conf. Quantitative Evaluation of Systems (QEST’13), ser. Lecture Notes in Computer Science, K. Joshi, M. Siegle, M. Stoelinga, and P. D’Argenio, Eds., vol. 8054. Springer, Heidelberg, Sep. 2013, pp. 253–256. [Online]. Available: http://sourceforge.net/projects/verisimpl/

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, “On the equivalence of classes of hybrid dynamical models,” in Proc. 40th IEEE Conf. Decision and Control, vol. 1, 2001, pp. 364–369.

D. Dill, “Timing assumptions and verification of finite-state concurrent systems,” in Automatic Verification Methods for Finite State Systems, ser. Lecture Notes in Computer Science, J. Sifakis, Ed. Springer, Heidelberg, 1990, vol. 407, ch. 17, pp. 197–212.

DOI: http://dx.doi.org/10.12962/j24775401.v3i1.2119


  • 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 http://iptek.its.ac.id/index.php/ijcsam.