caa a22 4500 605516251 CHVBK 20210128100713.0 cr unu---uuuuu 210128e20151101xx s 000 0 eng 10.1007/s00165-015-0340-4 doi (NATIONALLICENCE)springer-10.1007/s00165-015-0340-4 Accelerating worst case execution time analysis of timed automata models with cyclic behaviour [Elektronische Daten] [Omar Al-Bataineh, Mark Reynolds, Tim French] The paper presents a new efficient algorithm for computing worst case execution time (WCET) of systems modelled as timed automata (TA). The algorithm uses a set of abstraction techniques that improve significantly the efficiency of WCET analysis of TA models with cyclic behaviour. We show that the proposed abstractions are exact with respect to the WCET problem in the sense that the WCET computed in the abstract model is equal to the one computed in the concrete model. We also compare our algorithm with the one implemented in the model checker UPPAAL which shows that when infinite cycles exist (i.e. cycles that can be run infinitely often), UPPAAL's algorithm may not terminate, and when largely repetitive finite cycles exist (i.e. cycles that can be run a large number of times but finite), UPPAAL's algorithm suffers from the state space explosion, thus leading to a low efficiency or resource exhaustion. British Computer Society, 2015 Worst-case execution time (WCET) nationallicence Timed automata nationallicence Model checking nationallicence Zone abstraction nationallicence Al-Bataineh Omar School of Computer Science and Software Engineering, University of Western Australia, Perth, Australia aut Reynolds Mark School of Computer Science and Software Engineering, University of Western Australia, Perth, Australia aut French Tim School of Computer Science and Software Engineering, University of Western Australia, Perth, Australia aut Formal Aspects of Computing Springer London 27/5-6(2015-11-01), 917-949 0934-5043 27:5-6<917 2015 27 165 https://doi.org/10.1007/s00165-015-0340-4 text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s00165-015-0340-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Al-Bataineh Omar School of Computer Science and Software Engineering, University of Western Australia, Perth, Australia aut NATIONALLICENCE 700 1- Reynolds Mark School of Computer Science and Software Engineering, University of Western Australia, Perth, Australia aut NATIONALLICENCE 700 1- French Tim School of Computer Science and Software Engineering, University of Western Australia, Perth, Australia aut NATIONALLICENCE 773 0- Formal Aspects of Computing Springer London 27/5-6(2015-11-01), 917-949 0934-5043 27:5-6<917 2015 27 165