A master thesis from Aalborg University
Reachability Analysis for Timed Automata using Max-Plus Algebra
Author(s)
Term
1. term
Education
Publication year
2011
Submitted on
2011-01-14
Pages
34 pages
Abstract
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.
Documents
Colophon: This page is part of the AAU Student Projects portal, which is run by Aalborg University. Here, you can find and download publicly available bachelor's theses and master's projects from across the university dating from 2008 onwards. Student projects from before 2008 are available in printed form at Aalborg University Library.
If you have any questions about AAU Student Projects or the research registration, dissemination and analysis at Aalborg University, please feel free to contact the VBN team. You can also find more information in the AAU Student Projects FAQs.