Journal "Software Engineering"

a journal on theoretical and applied science and technology

ISSN 2220-3397

**Issue N1 2017 year**

DOI: 10.17587/prin.8.16-25

Graph Learning by Group of Motionless Automata

Graph learning or exploration tasks can be found in many applications, in particular, in exploration of networks, including Internet parts or GRIDs. For example, we can consider a WEB-page as a vertex, and each hyperlink as a directed arc. In this case an exploration of hypertext structure can be performed by executable agent tied with the vertices and communicating with each other by messages sent along the arcs. This paper is third in a series of works devoted to graph exploration by automata. In the first and second papers we consider graph exploration tasks performed by automata moving along graph arcs. In the first paper we consider a single automaton, in the second one — several automata, which can communicate by messages sent through a network independent of the graph. In this paper we consider automata that are immobile and fixed in the graph vertices and communicate only by messages sent along directed graph arcs. In the paper we investigate static and dynamic graph cases, and two tasks for each of the cases. While a static graph remains the same in the process of exploration, a dynamic graph can change — its arcs can appear and disappear, and they can change their ends. The first task considered is the graph exploration task, which is performed to learn its structure. The second task considered is parallel computation on the graph, more specifically, computation of some function of a multiset of values stored in graph vertices.

Keywords: directed graph, ordered graph, numerated graph, unknown graph, dynamic graph, graph learning, parallel computations, automaton, semirobot, automata group

pp. 16–25

Bourdonov I. B., Kossatchev A. S. Graph Learning by Group of Motionless Automata, Programmnaya Ingeneria, 2017, vol. 8, no. 1, pp. 16—25.