Semantics and Execution Time of New Timed Statecharts

• Autorzy: Magott J. , Skrobanek P.

Identyfikatory

DOI

10.3233/FI-2016-1414

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

real-time systems; performance evaluation; statecharts; computational complexity; UML

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 147, nr 4
• Strony: 387--414
• Opis fizyczny: Bibliogr. 25 poz., rys.

Twórcy

autor

Magott J.

• Chair of Computer Engineering, Technical University of Wrocław, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland

autor

Skrobanek P.

• Department of Multimedia Systems and Artificial Intelligence, Koszalin University of Technology, ul. Sniadeckich 2, 75-453 Koszalin, Poland

Bibliografia

• [1] Merlin P, Farber D. Recoverability of communication protocols, implication of a theoretical approach. IEEE Transactions on Communications. 1976;24(9):1036–1043.
• [2] Alur R, Dill DL. A Theory of Timed Automata. Theoretical Computer Science. 1994;126(2):183–235. doi:10.1016/0304-3975(94)90010-8.
• [3] Kesten Y, Pnueli A. Timed and Hybrid Statecharts and Their Textual Representation. In: Formal Techniques in Real-Time and Fault-Tolerant Systems, Second International Symposium, Nijmegen, The Netherlands, January 8-10, 1992, Proceedings; 1992. p. 591–620. Available from: http://dx.doi.org/10.1007/3-540-55092-5_32. doi:10.1007/3-540-55092-5_32.
• [4] Penczek W, Pólrola A. Specification and Model Checking of Temporal Properties in Time Petri Nets and Timed Automata. In: Applications and Theory of Petri Nets 2004, 25th International Conference, ICATPN 2004, Bologna, Italy, June 21-25, 2004, Proceedings; 2004. p. 37–76. Available from: http://dx.doi.org/10.1007/978-3-540-27793-4_4. doi:10.1007/978-3-540-27793-4_4.
• [5] OMG. OMG Unified Modeling Language (OMG UML), Superstructure, V2.1.2; 2011. Available from: http://www.omg.org/spec/UML/2.1.2/Superstructure/PDF.
• [6] Niewiadomski A, Penczek W, Szreter M. In: Pnueli A, Virbitskaite I, Voronkov A, editors. Towards Checking Parametric Reachability for UML State Machines. Berlin, Heidelberg: Springer Berlin Heidelberg; 2010. p. 319–330. Available from: http://dx.doi.org/10.1007/978-3-642-11486-1_27. doi:10.1007/978-3-642-11486-1_27.
• [7] Niewiadomski A, Penczek W, Szreter M. A New Approach to Model Checking of UML State Machines. Fundam Inform. 2009;93(1-3):289–303. Available from: http://dx.doi.org/10.3233/FI-2009-0103. doi:10.3233/FI-2009-0103.
• [8] Magott J, Skrobanek P. Timing analysis of safety properties using fault trees with time dependencies and timed state-charts. Reliability Engineering and Systems Safety. 2012;97:14–26.
• [9] Ramamoorthy CV, Ho GS. Performance Evaluation of Asynchronous Concurrent Systems Using Petri Nets. IEEE Transactions on Software Engineering. 1980 Sept;SE-6(5):440–449. doi:10.1109/TSE.1980.230492.
• [10] Ramchandani C. Analysis of asynchronous concurrent systems by timed Petri nets. MIT, Cambridge, MA, USA; 1974.
• [11] Magott J. New NP - complete problems in performance evaluation of concurrent systems using Petri nets. IEEE Transactions on Software Engineering. 1987;SE-13(5):578–581.
• [12] Garey MR, Johnson DS. Computers and Intractability, A Guide to the Theory of NP-completeness. New York: W.H. Freeman and Co.; 1979.
• [13] Graf S, Ober I, Ober I. A real-time profile for UML. STTT, Software Tools for Technology Transfer. 2006 apr;8(2):113–127.
• [14] Knapp A, Merz S, Rauh C. Model Checking - Timed UML State Machines and Collaborations. In: Proceedings of the 7th International Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems: Co-sponsored by IFIP WG 2.2. FTRTFT ’02. London, UK, UK: Springer-Verlag; 2002. p. 395–416. Available from: http://dl.acm.org/citation.cfm?id=646847.707098.
• [15] Commoner FG, Holt AN, Even S, Pnueli A. Marked directed graphs. Journal of Computer and System Sciences. 1971;5:511–523.
• [16] Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms, Second Edition. Cambridge, Massachusetts: The MIT Press; 2001. ISBN-13: 978-0262032933, 10: 0262032937.
• [17] David A, Möller MO, Yi W. Verification of UML Statecharts with Real-Time Extensions. Uppsala University; 2003. 2003-009. Available from: http://www.it.uu.se/research/reports/2003-009/.
• [18] Clarke EM, Grumberg O, Peled DA. Model Checking. Cambridge, Massachusetts: The MIT Press; 1999. ISBN: 0-262-03270-8.
• [19] Jahanian F, Mok A. Safety Analysis of Timing Properties in Real-Time Systems. IEEE Transactions on Software Engineering. 1986;SE-12(9):890–904. doi:10.1109/TSE.1986.6313045.
• [20] Beizer B. The Architecture and Engineering of Digital Computer Complexes. New York: Plenum; 1971. Available from: https://books.google.pl/books?id=y8UmAAAAMAAJ.
• [21] Trivedi KS. Probability and Statistics with Reliability, Queueing and Computer Science Applications. 1st ed. Prentice-Hall; 1982.
• [22] Smith CU. Performance Engineering of Software Systems. 1st ed. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc.; 1990. ISBN: 0201537699.
• [23] Smith CU, Williams LG. Performance Solutions: A Practical Guide to Creating Responsive, Scalable Software. Redwood City, CA, USA: Addison Wesley Longman Publishing Co., Inc.; 2002. ISBN: 0-201-72229-1.
• [24] Kopetz H, Bauer G. The time-triggered architecture. Proceedings of the IEEE. 2003;91(1):112–126. doi:10.1109/JPROC.2002.805821.
• [25] Kopetz H, Grunsteidl G. TTP-A time-triggered protocol for fault-tolerant real-time systems. In: Fault-Tolerant Computing, 1993. FTCS-23. Digest of Papers., The Twenty-Third International Symposium on. IEEE; 1993. p. 524–533. doi: 10.1109/FTCS.1993.627355.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).