Graph Learning by a Set of Automata. The Nondeterministic Case

Graph learning with automata is a basic task in many applications. Among such applications is formal model-based verification and testing of software and hardware systems, as well as network exploration including Internet and GRID. The model of a system or a network, in the final analysis, is reduced to an oriented graph of transitions with properties to be examined. In the recent years, the size of the real-life systems and networks and, consequently, the size of their graph models continuously grows. The problems arise when the graph learning by a single automaton (computer) either requires unacceptable long time, or the graph does not fit in the single computer memory, or both. Therefore, there is a task of parallel and distributed graph learning. This task is formalized as graph learning by a set of automata. The basis for such learning is graph traversal (traversing all its arcs accessible from the initial node). Automata can be generated in the initial node, move along the arcs of the graph according with their orientation and exchange messages through independent (of the graph) communication network. The total memory of the automata is used for storing the descriptions of the already traversed part of the graph. To move from node along an arc outgoing from it, the automaton should somehow identify this arc: indicate its number. In our paper "Graph learning by a set of automata" we proposed an algorithm of such traversal for deterministic graphs. The task is more complicated if the graph is nondeterministic. In such graph, to one arc number correspond, generally speaking, multiple arcs, one of which is chosen nondeterministically for traversal. To make the traversal possible, the following should be guaranteed: in unlimited number of experiments, each outgoing arc with the given number can be traversed. We call such nondeterminism fair. This paper covers the solution of the problem of traversal of fairly nondeterministic graphs.

nondeterministic graphs, graph learning, graph traversal, communicating automata, parallel processing, distributed systems, testing

1. R. Milner. A modal characterisation of observable machine-behaviour. In G. Astesiano & C. Bohm, editors: Proceedings CAAP 81, LNCS 112, Springer-Verlag, 1981, pp. 25-34.

2. van Glabbeek R.J. The linear time - branching time spectrum II; the semantics of sequential processes with silent moves. Proceedings CONCUR ’93, Hildesheim, Germany, August 1993 (E. Best, ed.), LNCS 715, Springer-Verlag, 1993, pp. 66-81.

3. Y. Afek and E. Gafni, Distributed Algorithms for Unidirectional Networks, SIAM J. Comput., Vol. 23, No. 6, 1994, pp. 1152-1178.

4. Bourdonov I.B., Kossatchev A.S., Petrenko A.K., Kuliamin V.V. The UniTesK Approach to Designing Test Suites. Programming and Computer Software, Vol. 29, No. 6, 2003, pp. 310-322.

5. Bourdonov I.B., Kossatchev A.S., Kuliamin V.V. Irredundant Algorithms for Traversing Directed Graphs: The Deterministic Case. Programming and Computer Software, Vol. 29, No. 5, 2003, pp. 245-258.

6. Bourdonov I.B., Kossatchev A.S., Kuliamin V.V. Irredundant Algorithms for Traversing Directed Graphs: The Nondeterministic Case. Programming and Computer Software, Vol. 30, No. 1, 2004, pp. 2-17.

7. Bourdonov I.B. Traversal of an Unknown Directed Graph by a Finite Robot. Programming and Computer Software, Vol. 30, No. 4, 2004, pp. 188-203.

8. Bourdonov I.B. Backtracking Problem in the Traversal of an Unknown Directed Graph by a Finite Robot. Programming and Computer Software, Vol. 30, No. 6, 2004, pp. 305-322.

9. Bourdonov I.B., Kossatchev A.S. Complete OpenState Testing of Limitedly Nondeterministic Systems. Programming and Computer Software, Vol. 35, No. 6, 2009, pp. 301-313.

10. Bourdonov I.B., Groshev S.G., Demakov A.V., Kamkin A.S., Kossatchev A.S, Sortov A.A. Parallel'noe testirovanie bol'shikh avtomatnykh modelej [Parallel testing of large automata models], Vestnik NNGU [Vestnik of UNN], №3920, 2011, pp. 187-193. (in Russian).

11. A. Demakov, A. Kamkin, A. Sortov. "High-Performance Testing: Parallelizing Functional Tests for Computer Systems Using Distributed Graph Exploration". Open Cirrus Summit 2011, Moscow.

12. Bourdonov I.B., Kossatchev A.S. Obkhod neizvestnogo grafa kollektivom avtomatov [Unknown graph traversing by automata group]. Trudy Mezhdunarodnoj superkomp'yuternoj konferentsii “Nauchnyj servis v seti Internet: vse grani parallelizma ”(21-26 sentyabrya 2009 g., g. Novorossijsk) [The proceeding of Russian Supercomputer conference ‘Scientific service of Internet’ (2013, Novorossijsk)] – Moscow, MSU publ., 2013, pp. 228-232. (in Russian).

13. Bourdonov I.B., Kossatchev A.S. Obhod neizvestnogo grafa kollektivom avtomatov [Unknown graph traversing by automata group]. Trudy ISP RAN [The proceeding of ISP RAS], Vol. 26-2, 2014, pp. 43-86 (in Russian).

14. Bourdonov I.B., Kossatchev A.S. Issledovanie grafa vzaimodejstvuyushhimi avtomatami. [ The graph learning by interacting automata] Novye informatsionnye tekhnologii v issledovanii slozhnykh struktur. Materialy 10-oj rossijskoj konferentsii s mezhdunarodnym uchastiem [New information technicks for complicated structure learning. The proceeding of 10-th Russian conference with international participation], Tomsk state university, 2014, pp. 47-48 (in Russian).

15. Bourdonov I.B., Kossatchev A.S. Parallel calculation on the graph. Programming and Computer Software, Vol. 41, No. 1, 2015 (in publication).