The Problems of Transition Predicates Construction in Hierarchical Concurrent Controllers

• Autorzy: Łabiak G.
• Języki publikacji: EN

Abstrakty

EN

The paper presents a problem of a transition predicates construction in hierarchical concurrent state oriented notation. The notation, called statechart diagrams or state machine, serves as a very convenient formalism for specification of a complex behavior of the embedded systems control unit. The controller specified in this way is discrete, deterministic and synchronous system which operates on binary values and can be implemented in programmable devices as a digital circuit. Well designed controller has conflict-free transitions and its concurrent transitions should be independent. In order to meet this requirements transition predicates must be pairwise both orthogonal and non-implicative. Computational complexities of the problems is equal to classic clique problem. The paper also suggests some statecharts syntactic structures solving these problems.

Słowa kluczowe

EN

binary control system; statechart diagrams; hierarchy;concurrency; conflicting transitions; Boolean predicates; computational complexity; compatibility classes; clique problem

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2012
• Tom: Vol. 58, No. 4
• Strony: 411--418
• Opis fizyczny: Bibliogr. 20 poz.

Twórcy

autor

Łabiak G.

• Computer Engineering & Electronics Department, University of Zielona Góra, Licealna 9, 65-417 Zielona Góra, Poland

Bibliografia

• [1] D. D. Gajski, S. Abdi, A. Gerstlauer, and G. Schirner, Embedded System Design Modeling, Synthesis and Verification, Springer, 2009.
• [2] OMG Unified Modeling Language TM (OMG UML), Superstructure. Version 2.3, Object Management Group, OMG, 250 First Avenue, Needham, MA 02494, U.S.A., May 2010. [Online]. Available: http://www.omg.org/spec/UML/2.3/.
• [3] D. D. Gajski, F. Vahid, S. Narayan, and J. Gong, Specification and Design of Embedded Systems. Englewood Cliffs, New Jersey: Prentice Hall, 1994.
• [4] D. Harel, „Statecharts: A Visual Formalism for Complex Systems”, Science of Computer Programming, vol. 8, pp. 231-274, 1987.
• [5] M. Adamski, „Parallel Controller Implementation using Standard PLD Software” in FPGAs, W. Moore and W. Luk, Eds. Abingdon EE & CS Books, Oct. 1991, pp. 296-304.
• [6] D. Drusinsky and D. Harel, „Using Statecharts for Hardware Description and Synthesis”. IEEE Transaction on Coputer-Aided Design, vol. 8, no. 7, pp. 798-807, Jul. 1989.
• [7] D. Drusinsky-Yoresh, „A State Assignment Procedure for Single-Block Implementation of State Chart.” IEEE Transaction on Coputer-Aided Design, vol. 10, no. 12, pp. 1569-1576, Dec. 1991.
• [8] S. Ramesh, „Efficient Translation of Statecharts to Hardware Circuits” in Proceedings of Twelfth International Conference on VLSI Design, Jan. 1999, pp. 384-389.
• [9] STATEMATE Magnum Code Generation Guide., I-Logix Inc., 3 Riverside Drive, Andover, MA 01810 U.S.A., 2001.
• [10] K. Buchenrieder, A. Pyttel, and C. Veith, „Mapping statechart models onto an FPGA-based ASIP architecture” in Proc. EURO-DAC'96, Sep. 1996, pp. 184-189.
• [11] G. Łabiak, „From UML statecharts to FPGA - the HiCoS approach”, in Proceedings of Forum on Specification & Design Languages : FDL'03, Frankfurt am Main, Sep. 2003, pp. 354-363.
• [12] HiCos, „HiCoS Homepage”, http://www.uz.zgora.pl/?glabiak, 2004. [Online]. Available: http://www.uz.zgora.pl/?glabiak
• [13] G. Łabiak, „Transition orthogonality in statechart diagrams and inconsistencies in binary control system”, Przegląd Elektrotechniczny, no. 9, pp. 130-133, 2010.
• [14] D. Harel and A. Naamad, „The STATEMATE Semantics of Statecharts”, ACM Trans. Soft. Eng. Method., vol. 5, no. 4, Oct. 1996.
• [15] G. Łabiak, „Symbolic States Exploration of UML Statecharts for Hardware Description”, in Design of Embedded Control Systems, M. A. Adamski, A. Karatkevich, and M. Węgrzyn, Eds. Springer, 2005, pp. 73-83.
• [16] A. Maggiolo-Schettini and M. Merro, Priorities in Statecharts., ser. LNCS. Springer-Verlag, 1997, vol. 1192, pp. 404-429.
• [17] G. Bazydło, „Behavioural synthesis of reconfigurable controllers based on UML state machine model”, Pomiary, Automatyka, Kontrola, no. 7, pp. 508-510, 2009, in Polish.
• [18] J. W. Moon and L. Moser, „On cliques in graphs”, Israel Journal of Mathematics, vol. 3, no. 1, pp. 23-28, March 1965.
• [19] A. Grasselli, „A note on the derivation of maximal compatibility classes”, Calcolo, vol. 2, no. 2, pp. 165-176, June 1966.
• [20] W. MathWorld, „Wolfram MathWorld”, http://mathworld.wolfram.com, 2010. [Online]. Available: http://mathworld.wolfram.com/HasseDiagram.html.