Generalized model of automata system | Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitelnaja tehnika i informatika – Tomsk State University Journal of Control and Computer Science. 2016. № 4(37). DOI: 10.17223/19988605/37/10

Generalized model of automata system

The problem of modeling and composing of aggregate systems is considered. The system components are described by 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 an oriented graph of links. Each node of the graph corresponds to the automaton of a component and an arc corresponds to a communication channel connecting an output of one automaton with input of another automaton. An automaton of the graph node in each state can accept multiple messages from its entries (at most one message from each input) and send multiple messages to its outputs (at most one message to each output). Inputs (outputs) of the automata not connected to outputs (inputs) of other automata are considered to be external and are used for communication between the system and its environment. The automata of the system operate synchronously: on each step each automaton performs one transition. A transition of an automaton imposes requirements on states of all its inputs and outputs (messages in them are specified) and explicitly specifies subset of inputs and outputs 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 at the automata inputs, 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 output. A composition of the automata of the system according to the graph of links is defined and its associativity is proved. In conclusion, the problems of testing of aggregate systems are described.

Download file

Counter downloads: 207

Keywords

ориентированные графы, взаимодействующие автоматы, композиция автоматов, детерминизм, сети, directed graph, communicating automata, automata composition, determinism, networks

Authors

Name	Organization	E-mail
Burdonov Igor B.	Institute for System Programming of the Russian Academy of Sciences	igor@ispras.ru
Kossatchev Alexander S.	Institute for System Programming of the Russian Academy of Sciences	kos@ispras.ru

Всего: 2

References

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

Бурдонов И.Б., Косачев А.С. Система автоматов: композиция по графу связей // Труды ИСП РАН. 2016. T. 28 (1).

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

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 // Protocol Specification, Testing, and Verification IX / eds. by E. Brinksma, G. Scollo, C.A. Vissers. North-Holland, 1990. Р. 87-98.

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

van der Bijl M., Rensink A., Tretmans J. Compositional testing with ioco // Formal Approaches to Software Testing: Third Interna tional Workshop, FATES 2003, Montreal, Quebec, Canada, October 6th, 2003 / eds. by Alexandre Petrenko, Andreas Ulrich. LNCS Springer, 2003. V. 2931. Р. 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. Sophia Antipolis, France, 2003. May 26-29. Р. 129-145.

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

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

Revised Working Draft on "Framework: Formal Methods in Conformance Testing". JTC1/SC21/WG1/Project 54/1, ISO Interim Meeting, ITU-T on. Paris, 1995.

Bourdonov I.B., Kossatchev A.S., Kuliamin V.V. Conformance theory of the systems with Refused Inputs and Forbidden Actions. M. : Nauka, 2008. 412 p. (in Russian)

Bourdonov I. Conformance theory (functional testing on formal model base). LAP LAMBERT Academic Publishing. Saarbrucken, Germany, 2011. 428 p. (in Russian)

Bourdonov I.B., Kossatchev A.S. Specification Completion for IOCO // Programming and Computer Software. 2011. V. 37 (1). P. 1-14.

Kamkin A.S., Chupilko M.M. Survey of modern technologies of simulation-based verification of hardware // Programming and Computer Software. 2011. V. 37 (3). P. 147-152.