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.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The lack of formal semantics for the UML creates many ambiguity problems, especially when real-time systems are specified. The paper proposes an approach to a formal definition of UML statecharts. Main features of the UML statecharts are described, and next, a transformation of the UML statecharts into LOTOS is defined.
Statecharts are widely used in system modelling and specification. They might also be used for performance analysis at early stages of system developing. In order to find performance metrices analytically, it is often assumed that models possess Markovian properties. The paper introduces a notion of Markovian statecharts that enables analytical evaluation of system performance. Our Markovian statecharts are driven by UML statecharts. The Markovian statecharts can model delays caused by: activities, which may be performed within system's states, activities initiated during passing between states. We define semantics of Markovian statecharts following an algebraic approach based on the Statecharts Process Algebra. Next, we present how Markovian processes ca be derived from Markovian statecharts.
PL
Mapy stanów stosuje się powszechnie w specyfikacji i modelowaniu systemów informatycznych. Można je wykorzystywać we wczesnych fazach tworzenia systemów do analizy ich wydajności. Często, w celu analitycznego wyliczania metryk wydajnościowych, zakłada się, że badany model posiada markowowskie własności. Artykuł wprowadza pojęcie markowowskich map stanów wzorowanych na mapach stanów z języka UML (United Modelling Language). Wprowadzone Markowowskie mapy stanów modelują dwa mechanizmy map stanów UML: opóźnienia powodowane przez aktywności wykonywane w czasie przebywania w stanie oraz opóźnienia powodowane przez aktywności inicjowane podczas przechodzenia pomiędzy stanami. W pierwszej części, w oparciu o algebrę procesów, artykuł przedstawia formalną operacyjną semantykę markowowskich map stanów. W drugiej części artykuł przedstawia transformację markowowskich map stanów procesy Markova.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.