论文标题
小工具框架中的遍历，重新配置和可及性
Traversability, Reconfiguration, and Reachability in the Gadget Framework
论文作者
论文摘要
考虑一个遍历“小工具”图的代理，每个图都带有局部状态，该状态随着代理而随着每个遍历而变化。我们表征了通用遍历的复杂性，目的是至少一次遍历每个小工具，以供DAG小工具，一态小工具和可逆的确定性小工具。我们还研究了重新配置的复杂性，其目标是将小工具体系带到指定状态，证明许多情况下的情况，并在某些情况下表明重新配置可能严格难以实现（在其他情况下的目标），而在其他情况下，在某些情况下，在其他情况下，在其他情况下，与重新配置相比，可以实现难度。
Consider an agent traversing a graph of "gadgets", each with local state that changes with each traversal by the agent. We characterize the complexity of universal traversal, where the goal is to traverse every gadget at least once, for DAG gadgets, one-state gadgets, and reversible deterministic gadgets. We also study the complexity of reconfiguration, where the goal is to bring the system of gadgets to a specified state, proving many cases PSPACE-complete, and showing in some cases that reconfiguration can be strictly harder than reachability (where the goal is for the agent to reach a specified location), while in other cases, reachability is strictly harder than reconfiguration.
