Finding minimum and maximum termination time of timed automata models with cyclic behaviour

详细信息    查看全文

• 作者：Omar Al-Bataineh^a ; ^{omar.ibrahim@ntu.edu.sg} ; Mark Reynolds^b ; Tim French^b
• 关键词：Worst-case execution time ; Model checking ; Timed automata
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：22 February 2017
• 年：2017
• 卷：665
• 期：Complete
• 页码：87-104
• 全文大小：672 K
• 卷排序：665

文摘

The paper presents a novel algorithm for computing worst case execution time (WCET) or maximum termination time of real-time systems using the timed automata (TA) model checking technology. The algorithm can work on any arbitrary diagonal-free TA and can handle more cases than previously existing algorithms for WCET computation, as it can handle cycles in TA and decide whether they lead to an infinite WCET. We show soundness of the proposed algorithm and study its complexity. To our knowledge, this is the first model checking algorithm that addresses comprehensively the WCET problem of systems with cyclic behaviour. In [7] Behrmann et al. provide an algorithm for computing the minimum cost/time of reaching a goal state in priced timed automata (PTA). The algorithm has been implemented in the well-known model checking tool UPPAAL to compute the minimum time for termination of an automaton. However, we show that in certain circumstances, when infinite cycles exist, the algorithm implemented in UPPAAL may not terminate, and we provide examples which UPPAAL fails to verify.