Turing Machine Equivalence of Time Asymmetric Choice Nets (Special Section on Concurrent Systems Technology)

スポンサーリンク

概要

• 論文の詳細を見る

• Petri net is a mathematical model for concurrent systems. Petri net is known to have less modeling power than that of Turing machine. Lack of zero testing ability is the main reason of 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 of zero testing. It is of theoretical interest what structure enables zero testing. This paper shows that time asymmetric choice net can simulate register machines. The result implies reachability problem of this subclass of time Petri net is undecidable.

• 社団法人電子情報通信学会の論文
• 2000-11-25

著者

• Tsuji Kohkichi

  The Faculty Of Information Science And Technology Aichi Prefectural University

• OHTA Atsushi

  the Faculty of Information Science and Technology, Aichi Prefectural University

• Ohta Atsushi

  The Faculty Of Information Science And Technology Aichi Prefectural University

関連論文

• Turing Machine Equivalence of Time Asymmetric Choice Nets (Special Section on Concurrent Systems Technology)
• Polynomial Time Decidability of Monotone Liveness of Time Bounded AC/DC Nets(Special Section on Concurrent Systems Technology)

スポンサーリンク