Abstract

An algorithm of traversal (retrieval of full information on the structure) of an a priori unknown directed graph by an unbounded set of finite automata that interact through the exchange of messages and can move along the arcs of the graph according to their direction is described. Under the assumption that the execution time of basic operations and the transmission time of individual messages are bounded, the total operating time of the algorithm is bounded, at worst, by O(m + nd), where n is the number of vertices of the graph, m is the number of its arcs, and d is the diameter of the graph; moreover, this estimate is unimprovable. The full proofs of the propositions formulated in this paper have been published in [6].