Space-time deterministic graph rewriting

我们研究非终止图重写模型，其局部规则是非确定性应用的，但却享有一种强形式的确定性，即时空确定性。当然，在终止计算的情况下，异步规则应用引入的混乱可能对最终结果无关紧要，因为协同作用会产生唯一的正常形式。然而，在非终止计算的情况下，协同性是一个非常弱的属性，而（几乎）同步的规则应用总是首选，例如在模拟动力系统时。在这里，我们提供了足够的条件，使异步局部规则应用共同产生图的时空展开中的良好确定事件，无论它们的应用顺序如何。我们的第一个例子是动力系统的异步模拟。我们的第二个例子涉及到时间膨胀，类似于广义相对论。

论文研究的问题是如何在非终止的计算中保持空间时间确定性，尽管采用了非确定性的本地规则应用。这是否是一个新问题？

论文提供了足够的条件，使得异步本地规则应用会合作产生空间时间展开图中的良确定事件，而不管它们的应用顺序。这个方案的关键思路是什么？相比当前领域的研究，这篇论文的思路有什么新意？

实验包括两个例子：一个是动力系统的异步模拟，另一个是类似于广义相对论的时间膨胀。论文提供了足够的条件，使得异步本地规则应用会合作产生良确定事件。然而，这篇论文的贡献主要在于提供了一种新的方法来解决异步本地规则应用的空间时间确定性问题。

最近的相关研究包括异步图重写系统的一些方面，如异步规则应用，图的收缩和收敛等。相关论文包括《Asynchronous Graph Rewriting: Application to the Simulation of Biological Systems》和《Asynchronous Graph Rewriting with Control: Termination and Confluence》等。