Universal Construction on
Self-Timed Cellular Autornata


Yousuko Takada 1 , Teijiro Isokawa 1 , Ferdinand Peper 2,1 , and Nobuyuki Matsui 1

1Division of Computer Engineering, University of Hyogo,
2167 Shosha,Himeji, Hyogo, 671-2201, Japan
takada@comp.eng.himeji-tech.ac.jp,{isokawa,matsui}@eng.u-hyogo.ac.jp
2 Nanotechnology Group,
National Institute of Information and Communications Technology,
588-2 Iwaoka, Iwaoka-cho, Nishi-ku, Kobe, 651-2401, Japan
peper@nict. go.jp

Abstract. Computation- and construction-universality in cellular automata(CA), first studied by von Neumann, has attracted steady research efforts, over the years, most employing synchronous CA. Asynchronous cellular automata(ACA),though of interest as most interactions in nature are asynchronous, have not been used for this task, other than by the indirect way of simulating a synchronous CA. In this paper, we propose a universal constructor on a self-timed cellular automaton (STCA), a particular type of ACA, in which cells are divided in four partitions, each with four states.

DOI: 10.1007/b102055