Direction-Reversible Self-Timed Cellular Automata for Delay-Insensitive Circuits
Daniel Morrison and Irek Ulidowski
We introduce a new Self-Timed Cellular Automaton capable of simulating reversible delay-insensitive circuits. In addition to a number of reversibility and determinism properties, our STCA exhibits direction-reversibility, where reversing the direction of a signal and running a circuit forwards is equivalent to running the circuit in reverse. We define also several extensions of the STCA which allow us to realise three larger classes of delay-insensitive circuits, including parallel circuits. We then show which of the reversibility, determinism and direction-reversibility properties hold for these classes of circuits.
Keywords: Delay-insensitive circuit, reversibility, direction-reversibility, asynchronous cellular automata, computational universality