The Reduced Automata Technique for Graph Exploration Space Lower Bounds
The Reduced Automata Technique for Graph Exploration Space Lower Bounds
复制标题
图探索空间下界的简化自动机技术
DOI：
10.1007/11685654_1
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
S. Tixeuil
中科院分区：
文献类型：
--
作者：
P. Fraigniaud;D. Ilcinkas;S. Rajsbaum;S. Tixeuil
我们考虑的任务，探索图与匿名节点的一组非合作机器人，建模为有限自动机。为了完成探索，图的每条边必须由至少一个机器人遍历。在本文中，机器人没有先验知识的拓扑图，也没有其大小，我们感兴趣的是在内存量的机器人需要完成的探索，我们介绍了所谓的reduced自动机技术，我们展示了如何使用这种技术，推导出几个空间下界的探索。非正式地说，简化自动机技术包括将机器人简化为更简单的形式，保留其在某些图上的“核心”行为。使用这种技术，我们首先证明任何q ≥ 1个非合作机器人的集合都需要内存位来探索所有n个节点图。证明意味着，对于任何一组qK-状态机器人，存在一个大小为O（qK）的图，该组机器人中没有机器人可以探索，这改进了Rollik（1980）的O（KO（q））界。我们的主要结果是后一个结果的应用，concerningterminatinggraph探索与一个机器人，即，其中机器人在完成探索之后被请求停止。对于这个任务，机器人提供了一个鹅卵石，它可以用来标记节点（没有这样的标记，即使终止探索循环也无法实现）。我们证明，终止探索需要Ω（logn）位的内存为机器人实现这一任务的alln节点图。
We consider the task of exploring graphs with anonymous nodes by a team of non-cooperative robots, modeled as finite automata. For exploration to be completed, each edge of the graph has to be traversed by at least one robot. In this paper, the robots have no a priori knowledge of the topology of the graph, nor of its size, and we are interested in the amount of memory the robots need to accomplish exploration, We introduce the so-calledreduced automata technique, and we show how to use this technique for deriving several space lower bounds for exploration. Informally speaking, the reduced automata technique consists in reducing a robot to a simpler form that preserves its “core” behavior on some graphs. Using this technique, we first show that any set ofq≥ 1 non-cooperative robots, requiresmemory bits to explore alln-node graphs. The proof implies that, for any set ofqK-state robots, there exists a graph of sizeO(qK) that no robot of this set can explore, which improves theO(KO(q)) bound by Rollik (1980). Our main result is an application of this latter result, concerningterminatinggraph exploration with one robot, i.e., in which the robot is requested to stop after completing exploration. For this task, the robot is provided with a pebble, that it can use to mark nodes (without such a marker, even terminating exploration of cycles cannot be achieved). We prove that terminating exploration requires Ω(logn) bits of memory for a robot achieving this task in alln-node graphs.