Preview

Труды Института системного программирования РАН

Расширенный поиск

Система автоматов: композиция по графу связей

https://doi.org/10.15514/ISPRAS-2016-28(1)-8

Полный текст:

Аннотация

Статья посвящена проблеме моделирования и композиции составных систем. Компоненты системы моделируются конечными автоматами с несколькими входами и выходами, а взаимодействие между ними - обменом сообщениями по симплексным каналам связи. Система описывается ориентированным графом связей, вершина которого соответствует автомату компонента, а дуга - каналу связи, соединяющему выход одного автомата со входом другого автомата. Автомат в вершине графа в каждом состоянии может принимать несколько сообщений по своим входам (не более одного по каждому входу) и посылать несколько сообщений по своим выходам (не более одного по каждому выходу). Входы (выходы) автоматов, которые не соединяются с выходами (входами) автоматов, являются внешними, через них осуществляется связь системы с её окружением. Автоматы системы работают синхронно: на каждом такте каждый автомат выполняет один переход. Переход автомата, предъявляя требования к состоянию всех входов и выходов автомата (указываются сообщения на них), отдельно указывает ту часть входов и выходов, по которым сообщения соответственно принимаются и посылаются, соответственно. Синхронность взаимодействия автоматов означает, что для каждого соединения требования автоматов, связанных этим соединением, должны быть согласованы. Это даёт возможность описывать более широкий спектр поведений автомата. Например, приоритетный приём сообщений: если на входах автомата имеется несколько сообщений, автомат может принять сообщения с наивысшим приоритетом, не принимая остальные сообщения. Также это позволяет автомату выполнять приём сообщений независимо от того, удаётся или не удаётся одновременно послать некоторое сообщение на некоторый выход. Определяется композиция автоматов системы по графу связей и доказывается её ассоциативность. В заключение определяются направления дальнейших исследований.

Об авторах

И. Б. Бурдонов
Институт системного программирования РАН
Россия


А. С. Косачев
Институт системного программирования РАН
Россия


Список литературы

1. И.Б.Бурдонов, А.С.Косачев. Тестирование системы автоматов. Труды ИСП РАН, том 28(1), 2016 г.

2. Hoare C.A.R. Communicating Sequential Processes. Englewood Cliffs, NJ: Prentice Hall International, 1985.

3. Milner R. Communication and Concurrency. Prentice-Hall, 1989.

4. Langerak R. A testing theory for LOTOS using deadlock detection. In E.Brinksma, G.Scollo, and C.A.Vissers, editors, Protocol Specification, Testing, and Verification IX, pages 87–98. North-Holland, 1990.

5. Tretmans J. Test Generation with Inputs, Outputs and Repetitive Quiescence. In: Software-Concepts and Tools, Vol. 17, Issue 3, 1996.

6. van der Bijl M., Rensink A., Tretmans J. Compositional testing with ioco. In Formal Approaches to Software Testing: Third International Workshop, FATES 2003, Montreal, Quebec, Canada, October 6th, 2003. Editors: Alexandre Petrenko, Andreas Ulrich ISBN: 3-540-20894-1. LNCS volume 2931, Springer, pp. 86-100.

7. Petrenko A., Yevtushenko N., Huo J.L. Testing Transition Systems with Input and Output Testers. Proc. IFIP TC6/WG6.1 15th Int. Conf. Testing of Communicating Systems, TestCom’2003, pp. 129-145. Sophia Antipolis, France, May 26-29, 2003.

8. И.Б.Бурдонов, А.С.Косачев. Системы с приоритетами: конформность, тестирование, композиция. "Программирование", 2009, №4, стр. 24-40.

9. И.Б.Бурдонов, А.С.Косачев. Согласование конформности и композиции. Программирование, №6, 2013, стр. 3-15.


Для цитирования:


Бурдонов И.Б., Косачев А.С. Система автоматов: композиция по графу связей. Труды Института системного программирования РАН. 2016;28(1):131-150. https://doi.org/10.15514/ISPRAS-2016-28(1)-8

For citation:


Burdonov I.B., Kossatchev A.S. Automata system: composition according to graph of links. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2016;28(1):131-150. (In Russ.) https://doi.org/10.15514/ISPRAS-2016-28(1)-8

Просмотров: 10


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)