Affiliations: [a] Chair of Computer Engineering, Technical University of Wrocław, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland. jan.magott@pwr.wroc.pl | [b] Department of Multimedia Systems and Artificial Intelligence, Koszalin University of Technology, ul. Sniadeckich 2, 75-453 Koszalin, Poland. pawel.skrobanek@tu.koszalin.pl
Correspondence:
[*]
Address for correspondence: Department of Multimedia Systems and Artificial Intelligence, Koszalin University of Technology, ul. Sniadeckich 2, 75-453 Koszalin, Poland.
Abstract: Time aspects play an essential role in real-time systems. One of the most often used techniques of designing real-time systems is the timed statecharts (TSCs) technique. In this paper, new timed statecharts based on UML notation are introduced. The main difference between the UML statecharts and the TSCs presented in the paper is the pair of minimal and maximal execution times assigned to states of the TSCs. Additionally, any interaction can be characterized by its minimal and maximal duration time. Moreover, the paper presents semantics for TSCs, emphasizing time aspects rather than variable valuation. The minimal and maximal execution time problem (MMETP) for TSCs is defined and the computational complexity of the MMETP is studied. It is proven in this paper that there is a limit between such TSCs for which there exists a polynomial algorithm for MMETP and such TSCs for which MMETP remains NP-hard. The mentioned limit is located between the AND state with any number of XOR states that are expressed by simple paths without guards and the AND state with two XOR states with no limitations. Since the MMETP is NP-hard, it is reasonable to use structural reductions of TSCs. A Theorem that is the theoretical foundation of a program loop reduction is proven.
