Synchronous to asynchronous transformation of polyautomata

摘要

A model (called the polyautomaton) of a general digital system is defined and the following problem is investigated: Given a synchronous polyautomaton P, construct (or transform P into) an asynchronous polyautomaton which preserves the capability for parallel computation of P. Two solutions to the problem are shown. Several computation-universal asynchronous cellular automata are obtained by means of the transformation from the computation-universal synchronous cellular automata.