Presentation	2000/1/18 Liveness Problem of Time AC Net is Undecidable Atsushi OHTA, Kohkichi TSUJI,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	Petri net is a mathematical model for discrete event 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 enables zero testing is equivalent to Turing machine. Time Perti net and is one of the models with ability of zero testing. Authors have shown that reachability problem of time asymmetiric choice nets, a subclass of time Petri net, is undercidable. In this report, we show that liveness problem of time AC net is also undercidable.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	concurrent system / Petri net / Turing machine / zero test
Paper #	CST99-58
Date of Issue

Conference Information
Committee	CST
Conference Date	2000/1/18(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Concurrent System Technology (CST)
Language	JPN
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Liveness Problem of Time AC Net is Undecidable
Sub Title (in English)
Keyword(1)	concurrent system
Keyword(2)	Petri net
Keyword(3)	Turing machine
Keyword(4)	zero test
1st Author's Name	Atsushi OHTA
1st Author's Affiliation	Faculty of Information Science and Technology, Aichi Prefectural University()
2nd Author's Name	Kohkichi TSUJI
2nd Author's Affiliation	Faculty of Information Science and Technology, Aichi Prefectural University
Date	2000/1/18
Paper #	CST99-58
Volume (vol)	vol.99
Number (no)	539
Page	pp.pp.-
#Pages	6
Date of Issue