Reachability Analysis for Timed Automata using Max-Plus Algebra

Studenteropgave: Speciale (inkl. HD afgangsprojekt)

  • Qi Lu
  • Michael Madsen
  • Martin Milata
  • Søren Ravn
1. semester, Datalogi, Kandidat (Kandidatuddannelse)
In this report, we elaborate on the idea of using max-plus polyhedra as a data structure for the clock space in reachability analysis of timed automata. Drawing inspiration from the extensive work that has been done on difference bound matrices, as well as previous work on max-plus polyhedra in other areas, we have developed the remainder of the algorithms needed to perform forward and backward reachability analysis using max-plus polyhedra. Furthermore, we give proofs that the algorithms are correct according to the definition of the operations. Finally, to show that the approach works in practice and theory alike, we create a proof-of-concept implementation on top of the model checker opaal.
Udgivelsesdato17 jan. 2011
Antal sider34
ID: 44108382