Reversible structures

Abstract

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.