Abstraction and verification of autonomous max-plus-linear systems

D. Adzkiya, B. De Schutter, and A. Abate, "Abstraction and verification of autonomous max-plus-linear systems," Proceedings of the 2012 American Control Conference, Montréal, Canada, pp. 721-726, June 2012.

This work investigates the use of finite abstractions for the verification of autonomous Max-Plus-Linear (MPL) models. Abstractions are characterized as finite-state labeled transition systems (LTS) and are obtained by first partitioning the state space of the MPL and associating states of the LTS to the partitions, then by defining relations among the vertices of the LTS, corresponding to dynamical transitions between the MPL state partitions, and finally by labeling the LTS edges according to one-step time properties of the events of the MPL model. In order to establish formal equivalences, the finite LTS abstraction is proven to either simulate or to bisimulate the original MPL model, the difference depending on its determinism. The computational performance of the abstraction procedure is tested on a benchmark. The work then studies properties of the original MPL model by verifying equivalent specifications on the finite LTS abstraction.

 * Corresponding technical report: pdf file (155 KB)
      Note: More information on the pdf file format mentioned above can be found here.

Bibtex entry:

        author={D. Adzkiya and B. {D}e Schutter and A. Abate},
        title={Abstraction and verification of autonomous max-plus-linear systems},
        booktitle={Proceedings of the 2012 American Control Conference},
        address={Montr\'eal, Canada},

Go to the publications overview page.

This page is maintained by Bart De Schutter. Last update: March 21, 2022.