Journal "Software Engineering"
a journal on theoretical and applied science and technology
ISSN 2220-3397
Journal "Software Engineering"
a journal on theoretical and applied science and technology
ISSN 2220-3397
Issue N12 2016 year
Graph learning or exploration tasks can be found in many applications. Among the most important ones we can name software or hardware verification and testing, network exploration, including exploration of big parts of Internet and GRIDs. In many cases system or network model is represented as a graph, which properties should be investigated. This paper is the second one in a series of works devoted to graph exploration by automata. In the first paper we consider graph exploration by a single automaton, in this one we consider directed graph exploration by several automata, which can move along its arcs and communicate through graph-independent network. All arcs outgoing from a vertex of the graph are numbered, such a graph is called an ordered one. To move through some arc from some vertex, an automaton should use this arcs number. In the modern technical environment the size of actively used systems and networks is growing, so does the size of graphs modeling those systems and networks. When graph exploration by a single automaton (a single machine) requires too large time or a graph cannot be stored in the memory of a single machine, such an exploration and further graph investigation become problematic. So, the task of parallel distributed graph exploration becomes actual. We formalize this task as a task of graph exploration by a set of automata (several machines, which total memory is sufficient to store the graph in it). Possible solutions of this task can differ depending on the memory size of automata used. As in the first paper, we consider robots, semi-robots and unbounded automata. A robot is a finite automaton with bounded memory. A semi-robot is an automaton, which memory size is bounded by some function of the graph size. An unbounded automaton can store the entire structure of the graph in its internal memory. In this paper we also present the results on non-deterministic graph exploration by a set of semi-robots. Non-deterministic graph can have several arcs with the same number outgoing from one vertex. Under some restrictions on such a graph, it can be explored by a set of automata. For unbounded nondeterministic case we consider so called A-traversal, which may not use every arc, but use every valid arc number in each vertex at least once. To have a A-traversal a directed graph should be bound in some specific sense. In the next paper we consider immobile automata fixed in graph vertices and communicating with messages sent along graph arcs.