Reversible structures
Reversible structures
复制标题
可逆结构
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
C. Laneve
中科院分区：
文献类型：
--
作者：
L. Cardelli;C. Laneve
可逆结构是可以向前和向后进展的计算单元。我们研究弱相干结构，主要是由DNA电路的启发，并可能在这些系统中编译，并证明了标准化定理。当单元有唯一的id时，标准化定理可以以一种形式得到加强，这种形式承载了可达性的二次算法，这是一个对于泛型结构是EXPSPACE完全的问题。然后，我们定义了一个编译的并发演算-异步RCCS -DNA通过可逆的结构，从而产生一个细粒度的实现到化学的过去的记忆。
Reversible structures are computational units that may progress forward and backward. We study weak coherent structures that are primarily inspired by DNA circuits and may be compiled in these systems and demonstrate a standardization theorem. When units have unique id, the standardization theorem may be strengthened in a form that bears a quadratic algorithm for reachability, a problem that is EXPSPACE-complete for generic structures. We then define a compilation of a concurrent calculus -- the asynchronous RCCS -- to DNA via reversible structures, thus yielding a finegrain implementation of memories of the past into chemistry.