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
I. B. Bourdonov,, A. S. Kossatchev,, Institute for System Programming RAS, Moscow, 109004, Russian Federation
Corresponding author: Bourdonov Igor B., Leading Researcher, Institute for System Programming RAS, 109004, Moscow, Russian Federation, E-mail:
Received on August 01, 2016
Accepted on October 19, 2016

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
For citation:
Bourdonov I. B., Kossatchev A. S. Graph Learning by Group of Motionless Automata, Programmnaya Ingeneria, 2017, vol. 8, no. 1, pp. 16—25.