



























We construct a time-optimal quasi-solution of the firing mob synchronisation problem over finite, connected, and undirected multigraphs whose maximum degrees are uniformly bounded by a constant. It is only a quasi-solution because its number of states depends on the graph or, from another perspective, does not depend on the graph but is countably infinite. To construct this quasi-solution we introduce signal machines over continuum representations of such multigraphs and construct a signal machine whose discretisation is a cellular automaton that quasi-solves the problem. This automaton uses a time-optimal solution of the firing squad synchronisation problem in dimension one with one general at one end to synchronise edges, and freezes and thaws the synchronisation of edges in such a way that all edges synchronise at the same time.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。