Система автоматов: композиция по графу связей
Автор: Бурдонов И.Б., Косачев А.С.
Журнал: Труды Института системного программирования РАН @trudy-isp-ran
Статья в выпуске: 1 т.28, 2016 года.
Бесплатный доступ
Статья посвящена проблеме моделирования и композиции составных систем. Компоненты системы моделируются конечными автоматами с несколькими входами и выходами, а взаимодействие между ними - обменом сообщениями по симплексным каналам связи. Система описывается ориентированным графом связей, вершина которого соответствует автомату компонента, а дуга - каналу связи, соединяющему выход одного автомата со входом другого автомата. Автомат в вершине графа в каждом состоянии может принимать несколько сообщений по своим входам (не более одного по каждому входу) и посылать несколько сообщений по своим выходам (не более одного по каждому выходу). Входы (выходы) автоматов, которые не соединяются с выходами (входами) автоматов, являются внешними, через них осуществляется связь системы с её окружением. Автоматы системы работают синхронно: на каждом такте каждый автомат выполняет один переход. Переход автомата, предъявляя требования к состоянию всех входов и выходов автомата (указываются сообщения на них), отдельно указывает ту часть входов и выходов, по которым сообщения соответственно принимаются и посылаются, соответственно. Синхронность взаимодействия автоматов означает, что для каждого соединения требования автоматов, связанных этим соединением, должны быть согласованы. Это даёт возможность описывать более широкий спектр поведений автомата. Например, приоритетный приём сообщений: если на входах автомата имеется несколько сообщений, автомат может принять сообщения с наивысшим приоритетом, не принимая остальные сообщения. Также это позволяет автомату выполнять приём сообщений независимо от того, удаётся или не удаётся одновременно послать некоторое сообщение на некоторый выход. Определяется композиция автоматов системы по графу связей и доказывается её ассоциативность. В заключение определяются направления дальнейших исследований.
Ориентированные графы, взаимодействующие автоматы, композиция автоматов, распределенные системы, сети
Короткий адрес: https://sciup.org/14916318
IDR: 14916318 | DOI: 10.15514/ISPRAS-2016-28(1)-8
Automata system: composition according to graph of links
The problem of modeling and composing of aggregate systems is considered. The system components are described with finite automata with multiple entries and exits. The communication between automata is described with message passing over simplex communication channels. The system is described with a directed graph of links. Each node of the graph corresponds to automaton of a component and an arc corresponds to a communication channel connecting exit of one automaton with entry of another automaton. Automaton of the graph node in each state can accept multiple messages from its entries (at most one message from each entry) and send multiple messages to its exits (at most one message to each exit). Entries (exits) of the automata not connected to exits (entries) of automata are considered to be external and used for communication between the system and its environment. The automata of the system operate synchronously: on each cycle each automaton performs one transition. A transition of an automaton imposes requirements on states of all its entries and exits (messages in them are specified) and explicitly specifies subset of entries and exits through which the messages are received or sent, respectively. Synchronous communication between automata means that for each link the requirements of the automata connected with this link must conform to each other. It makes possible to describe a wider spectrum of automata behavior. For example, a priority of message receiving: if there are multiple message in the automata entries, it can receive messages with the highest priority and discard the rest of the messages. It also makes possible for the automaton to receive messages regardless of ability to simultaneously send some message to some exit. A composition of the automata of the system according to the graph of links is defined and its associativity is proved. In conclusion, the directions of future research are described.
Список литературы Система автоматов: композиция по графу связей
- I. B. Burdonov, A. S. Kossatchev. Testirovanie sistemy avtomatov Trudy ISP RAN , Vol. 28 (Issue 1), 2016, pp. 103-130 DOI: 10.15514/ISPRAS-2016-28(1)-7
- Hoare C.A.R. Communicating Sequential Processes. Englewood Cliffs, NJ: Prentice Hall International, 1985.
- Milner R. Communication and Concurrency. Prentice-Hall, 1989.
- 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.
- Tretmans J. Test Generation with Inputs, Outputs and Repetitive Quiescence. In: Software-Concepts and Tools, Vol. 17, Issue 3, 1996.
- 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.
- 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.
- I. B. Burdonov, A. S. Kossatchev. Systems with Priorities: Conformance, Testing, and Composition. Programming and Computer Software, Vol. 35, No. 4, 2009, pp.198-211 DOI: 10.1134/S0361768809040045
- I. B. Burdonov, A. S. Kossatchev. Agreement between Conformance and Composition. Programming and Computer Software, Vol. 39, No. 6, 2013, pp. 269-278 DOI: 10.1134/S0361768813060029
