14-18 juin 2021 Virtuelle (France)
SMT-Based Bounded Model Checking of Max-Plus Linear Systems
Muhammad Syifa'ul Mufid  1@  , Andrea Micheli  2@  , Alessandro Abate  1@  , Alessandro Cimatti  2@  
1 : Department of Computer Science, University of Oxford
Oxford -  Royaume-Uni
2 : Fondazione Bruno Kessler
Trento -  Italie

Max-Plus Linear (MPL) systems are an algebraic formalism with practical applications in transportation networks, manufacturing and biological systems. MPL systems can be naturally modeled as infinite-state transition systems, and exhibit interesting structural properties (e.g. periodicity or steady-state), for which analysis methods have been recently proposed. In this talk, we tackle the open problem of specifying and analyzing user-defined temporal properties for MPL systems. We propose Time-Difference LTL (TDLTL), a logic that encompasses the delays between the discrete-time events governed by an MPL system, and characterizes the problem of model checking TDLTL over MPL. We propose a family of specialized algorithms leveraging the periodic behaviour of an MPL system. We prove soundness and completeness, showing that the transient and cyclicity of the MPL system induce a completeness threshold for the verification problem. The algorithms are cast in the setting of SMT-based verification of infinite-state transition systems over the reals, with variants depending on the computation of the bound, and on the unrolling of the transition relation. Our comprehensive experiments show that the proposed techniques can be applied to MPL systems of large dimensions and on general TDLTL formulae, with remarkable performance gains against a dedicated abstraction-based technique and a translation to the nuXmv symbolic model checker.


Personnes connectées : 38 Vie privée
Chargement...