The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
A rede de Petri é um modelo matemático para sistemas concorrentes. Sabe-se que a rede de Petri tem menos poder de modelagem do que a máquina de Turing. A falta de capacidade de teste zero é a principal razão deste fato. Na verdade, todo modelo de rede de Petri estendido que pode realizar zero testes é equivalente à máquina de Turing. A rede Time Petri é um dos modelos com capacidade de teste zero. É de interesse teórico qual estrutura permite teste zero. Este artigo mostra que a rede de escolha assimétrica no tempo pode simular máquinas de registro. O resultado implica que o problema de alcançabilidade desta subclasse de tempo da rede de Petri é indecidível.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -