In: IEICE Trans. on Fundamentals in Electronics, Communications and Computers, Vol. E83-A, No. 11, pages 2278-2281. 2000.
Abstract: A Petri net is a mathematical model for concurrent systems. A Petri net is known to have less modeling power than that of Turing machines. Lack of zero testing ability is the main reason for this fact. Indeed, every extended Petri net model that can perform zero testing is equivalent to Turing machine. Time Petri net is one of the models with ability to zero testing. It is of theoretical interest what structure enable zero testing. This paper shows that time asymmetric choice can simulate register machines. The result implies that the reachability problem of this class of time Petri nets is undecidable.
Keywords: Turing machines, asymmetric choice nets, time Petri nets.