Proceedings of ISP RAS


Graph learning by a set of automata.

Igor Burdonov, Alexander Kosachev.

Abstract

Graph learning by automata is a basic task in many applications. Among these applications are verification and testing of software and hardware systems, network exploration including Internet and GRID basing on formal models. The system or network model, in the final analysis, is a transition graph with properties to be examined. In the recent years the size of the systems and networks in everyday use and, consequently, the size of their models and graphs to be learned grows constantly. Problems arise when graph exploration by a single automaton (computer) either requires a lot of time, or a lot of computer memory, or both. Therefore, there is a task of parallel and distributed graph exploration. This task is formalized as graph learning by a set of automata (a set of computers with sufficient total memory working in parallel). This paper covers the solution of this task. First of all the behavior of the automaton on the graph is formalized. Then the algorithm of the graph learning is described in detail. The estimation of the algorithm is O(m+nD). Some ways of possible optimization is discussed.

Keywords

graph learning, traversal of an unknown graph, finite automaton (state machine), extended finite state machine, communicating automata, parallel processing, distributed systems, testing

Edition

Proceedings of the Institute for System Programming, vol. 26, issue 2, 2014, pp. 43-86.

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

DOI: 10.15514/ISPRAS-2014-26(2)-2

Full text of the paper in pdf (in Russian) Back to the contents of the volume