BSU Bulletin. Mathematics, Informatics
Bibliographic description:
, CONSTRUCTION OF SYSTEMS WITH COMPLEX BEHAVIOR ON THE PRINCIPLES OF SYNTAX-ORIENTED CONTROL // BSU Bulletin. Mathematics, Informatics. - 2020. №2. . - С. 15-35.
Title:
CONSTRUCTION OF SYSTEMS WITH COMPLEX BEHAVIOR ON THE PRINCIPLES OF SYNTAX-ORIENTED CONTROL
Financing:
Codes:
Annotation:
Systems with complex behavior include event-driven software systems,
called reactive systems in the academic literature, that is, systems that react to the
same input action in different ways depending on their state and history. It is convenient to describe such systems using special language tools, both graphic and text. The
article presents a technique for automated construction of systems with complex
behavior using the developed language CIAO (Cooperative Interaction of Automata
Objects), which allows formally specifying the required behavior based on an informal description of a responsive system. Further according to this specification a software system is generated in the C ++ programming language. Both graphical and
textual notations are provided for the CIAO language. Graphic notation is based on
an extended notation of state machine diagrams and component diagrams of the unified modeling language UML, which proved their worth in describing the behavior of
event-driven systems. The text syntax of the CIAO language is described by a context-free grammar in regular form. The text syntax of the CIAO language is described by context-free grammar in regular form. Automatically generated C++ code
allows using both library and any hand-written external functions. As an example, we
have proposed an original solution to D. Knuth’s problem of a responsive elevator
control system.
called reactive systems in the academic literature, that is, systems that react to the
same input action in different ways depending on their state and history. It is convenient to describe such systems using special language tools, both graphic and text. The
article presents a technique for automated construction of systems with complex
behavior using the developed language CIAO (Cooperative Interaction of Automata
Objects), which allows formally specifying the required behavior based on an informal description of a responsive system. Further according to this specification a software system is generated in the C ++ programming language. Both graphical and
textual notations are provided for the CIAO language. Graphic notation is based on
an extended notation of state machine diagrams and component diagrams of the unified modeling language UML, which proved their worth in describing the behavior of
event-driven systems. The text syntax of the CIAO language is described by a context-free grammar in regular form. The text syntax of the CIAO language is described by context-free grammar in regular form. Automatically generated C++ code
allows using both library and any hand-written external functions. As an example, we
have proposed an original solution to D. Knuth’s problem of a responsive elevator
control system.
Keywords:
state-transition graph; syntactic flow-chart; finite state transition graph, context-free grammar in regular form.
List of references:
1. Fedor A. Novikov, Ludmila N. Fedorchenko, Vladimir I. Vorobiev, Roza R. Fatkieva, and Dmitriy K. Levonevskiy. 2017. Attribute-Based Approach of Defining the Secure Behavior of Automata Objects. Proceedings of SIN 2017 Conference (SIN 2017). Jennifer B. Sartor, Theo D’Hondt, and Wolfgang De Meuter (Eds.). ACM, New York, USA, Art. 4, 6 p. DOI: https://doi.org/10.1145/3136825.3136887.
2. Novikov F. A., Afanasyeva I. V. Kooperativnoe vzaimodeistvie avtomatnykh obyektov [Cooperative interaction of automata objects // Informatsionnoupravlyayushchie sistemy]. Informatsionno-upravlyayuschie sistemy. 2016. No. 6. Pp. 50–63. DOI: 10.15217/issn1684-8853.2016.6.50.
3. Harel D. Statecharts: a Visual Formalism for Complex Systems. Science of Computer Programming. 1987. V. 8. Pp. 231–274. https://doi.org/10.1016/0167-6423(87)90035-9.
4. Harel D., Naamad A. The STATEMATE semantics of statecharts. ACM Transactions on Software Engineering and Methodology (TOSEM). 1996. V. 5. No. 4. Pp. 293–333. https://doi.org/10.1145/235321.235322.
5. Selic B., Gullekson G., Ward P. T. Real-Time Object-Oriented Modeling. John Wiley & Sons, 1994. 525 p.
6. Gomaa H. Designing Concurrent, Distributed, and Real-Time Applications with UML. Addison-Wesley Professional, 2000. 816 p.
7. Gomaa H. Real-Time Software Design for Embedded Systems. Cambridge, 2016. https://doi.org/10.1017/CBO9781139644532.
8. Polikarpova N. I., Shalyto A. A. Avtomatnoe programmirovanie [Automatic Programming]. St. Petersburg: Piter Publ., 2011. 176 p.
9. Novikov F. A., Tikhonova U. N. Avtomatnyy metod opredeleniya problemnoorientirovannykh yazykov (Chast 3) [An Automatic Method for Definition of ObjectOriented Language (Part 3)]. Informatsionno-upravliaiuschie sistemy — Information and Control Systems. 2010. No. 3. Pp. 29–37.
10. Fedorchenko L., Baranov S. Equivalent Transformations and Regularization in Context–Free Grammars. Cybernetics and Information Technologies. 2015. V. 14. No. 4. Pp. 29–44. https://doi.org/10.1515/cait-2014-0003.
11. Novikov F. A., Ivanov D. Yu. Modelirovanie na UML. Teoriya, praktika, videokurs [UML Modeling. Theory, Practice, Video Course]. St. Petersburg: Nauka i Tekhnika, 2010. 640 p.
12. Afanasyeva I. V. Metod proektirovaniya i realizatsii parallelnykh reagiruyushchikh sistem [Method of Design and Implementation of Concurrent Reactive Systems]. Cand. Engineering Sci. Diss. St. Petersburg. 2018. 137 p.
13. Knuth D. E. The Art of Computer Programming: Fundamental Algorithms. 3rd ed. Addison-Wesley Professional, 1998. V. 1. 652 p.
14. Novikov F., Fedorchenko L., Vorobiev V., Fatkieva R., Levonevskiy D. Attribute-based approach of defining the secure behavior of automata objects. Proceedings of the 10th International Conference on Security of Information and Networks (SIN'17). ACM, NY, USA, 2017. Pp. 67–72. https://doi.org/10.1145/3136825.3136887.
15. Novikov F. A., Afanasyeva I. V. Kooperativnoe vzaimodeystvie avtomatnykh obyektov [Cooperative Interaction of Automata Objects]. Informatsionnoupravliaiuschie sistemy — Information and Control Systems. 2016. No. 6. Pp. 50–63. https://doi.org/10.15217/issn1684-8853.2016.6.50.
16. Meyer B. Object-Oriented Software Construction. 2nd ed. Prentice-Hall, 1997. 1296 p.
17. Nesteruk D. Design Patterns in .NET: Reusable Approaches in C# and F# for Object-Oriented Software Design. Apress. 2019. 376 p. https://doi.org/10.1007/978-1-4842-4366-4.
18. Yourdon E. Modern Structured Analysis. Englewood Cliffs, NJ: Prentice Hall, 1989. 672 p.
19. Martynenko B. K. Sintaksicheski upravlyaemaya obrabotka dannykh [SyntaxDirected Data Processing]. St. Petersburg: St. Petersburg Univ. Publ., 2004. 316 p.
20. Fedorchenko L. N., Afanasyeva I. V. Metod opisaniya sistem so slozhnym povedeniem na printsipakh obobshchennykh avtomatov [A Method for Describing Systems with Complex Behavior Based on the Principles of Generalized Automata]. Vestnik Buryatskogo gosudarstvennogo universiteta. Matematika, informatika. 2018. No. 4. Pp. 22–36. https://doi.org/10.18101/2304-5728-2018-4-22-36.
2. Novikov F. A., Afanasyeva I. V. Kooperativnoe vzaimodeistvie avtomatnykh obyektov [Cooperative interaction of automata objects // Informatsionnoupravlyayushchie sistemy]. Informatsionno-upravlyayuschie sistemy. 2016. No. 6. Pp. 50–63. DOI: 10.15217/issn1684-8853.2016.6.50.
3. Harel D. Statecharts: a Visual Formalism for Complex Systems. Science of Computer Programming. 1987. V. 8. Pp. 231–274. https://doi.org/10.1016/0167-6423(87)90035-9.
4. Harel D., Naamad A. The STATEMATE semantics of statecharts. ACM Transactions on Software Engineering and Methodology (TOSEM). 1996. V. 5. No. 4. Pp. 293–333. https://doi.org/10.1145/235321.235322.
5. Selic B., Gullekson G., Ward P. T. Real-Time Object-Oriented Modeling. John Wiley & Sons, 1994. 525 p.
6. Gomaa H. Designing Concurrent, Distributed, and Real-Time Applications with UML. Addison-Wesley Professional, 2000. 816 p.
7. Gomaa H. Real-Time Software Design for Embedded Systems. Cambridge, 2016. https://doi.org/10.1017/CBO9781139644532.
8. Polikarpova N. I., Shalyto A. A. Avtomatnoe programmirovanie [Automatic Programming]. St. Petersburg: Piter Publ., 2011. 176 p.
9. Novikov F. A., Tikhonova U. N. Avtomatnyy metod opredeleniya problemnoorientirovannykh yazykov (Chast 3) [An Automatic Method for Definition of ObjectOriented Language (Part 3)]. Informatsionno-upravliaiuschie sistemy — Information and Control Systems. 2010. No. 3. Pp. 29–37.
10. Fedorchenko L., Baranov S. Equivalent Transformations and Regularization in Context–Free Grammars. Cybernetics and Information Technologies. 2015. V. 14. No. 4. Pp. 29–44. https://doi.org/10.1515/cait-2014-0003.
11. Novikov F. A., Ivanov D. Yu. Modelirovanie na UML. Teoriya, praktika, videokurs [UML Modeling. Theory, Practice, Video Course]. St. Petersburg: Nauka i Tekhnika, 2010. 640 p.
12. Afanasyeva I. V. Metod proektirovaniya i realizatsii parallelnykh reagiruyushchikh sistem [Method of Design and Implementation of Concurrent Reactive Systems]. Cand. Engineering Sci. Diss. St. Petersburg. 2018. 137 p.
13. Knuth D. E. The Art of Computer Programming: Fundamental Algorithms. 3rd ed. Addison-Wesley Professional, 1998. V. 1. 652 p.
14. Novikov F., Fedorchenko L., Vorobiev V., Fatkieva R., Levonevskiy D. Attribute-based approach of defining the secure behavior of automata objects. Proceedings of the 10th International Conference on Security of Information and Networks (SIN'17). ACM, NY, USA, 2017. Pp. 67–72. https://doi.org/10.1145/3136825.3136887.
15. Novikov F. A., Afanasyeva I. V. Kooperativnoe vzaimodeystvie avtomatnykh obyektov [Cooperative Interaction of Automata Objects]. Informatsionnoupravliaiuschie sistemy — Information and Control Systems. 2016. No. 6. Pp. 50–63. https://doi.org/10.15217/issn1684-8853.2016.6.50.
16. Meyer B. Object-Oriented Software Construction. 2nd ed. Prentice-Hall, 1997. 1296 p.
17. Nesteruk D. Design Patterns in .NET: Reusable Approaches in C# and F# for Object-Oriented Software Design. Apress. 2019. 376 p. https://doi.org/10.1007/978-1-4842-4366-4.
18. Yourdon E. Modern Structured Analysis. Englewood Cliffs, NJ: Prentice Hall, 1989. 672 p.
19. Martynenko B. K. Sintaksicheski upravlyaemaya obrabotka dannykh [SyntaxDirected Data Processing]. St. Petersburg: St. Petersburg Univ. Publ., 2004. 316 p.
20. Fedorchenko L. N., Afanasyeva I. V. Metod opisaniya sistem so slozhnym povedeniem na printsipakh obobshchennykh avtomatov [A Method for Describing Systems with Complex Behavior Based on the Principles of Generalized Automata]. Vestnik Buryatskogo gosudarstvennogo universiteta. Matematika, informatika. 2018. No. 4. Pp. 22–36. https://doi.org/10.18101/2304-5728-2018-4-22-36.
Article.pdf