IEICE TRANSACTIONS on Fundamentals
Turing Machine Equivalence of Time Asymmetric Choice Nets
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.11 pp.2278-2281
- Publication Date
- 2000/11/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section LETTER (Special Section on Concurrent Systems Technology)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Atsushi OHTA, Kohkichi TSUJI, "Turing Machine Equivalence of Time Asymmetric Choice Nets" in IEICE TRANSACTIONS on Fundamentals,
vol. E83-A, no. 11, pp. 2278-2281, November 2000, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_11_2278/_p
Copy
@ARTICLE{e83-a_11_2278,
author={Atsushi OHTA, Kohkichi TSUJI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Turing Machine Equivalence of Time Asymmetric Choice Nets},
year={2000},
volume={E83-A},
number={11},
pages={2278-2281},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={November},}
Copy
TY - JOUR
TI - Turing Machine Equivalence of Time Asymmetric Choice Nets
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2278
EP - 2281
AU - Atsushi OHTA
AU - Kohkichi TSUJI
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2000
AB - 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.
ER -
English
