The search functionality is under construction.

The search functionality is under construction.

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

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.

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 -