| 講演名 | 2000/1/18 時間つきACネットの活性問題の非可解性 太田 淳, 辻 孝吉, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | ペトリネットはコンカレントシステムのモデルの一つである。ペトリネットのモデル化能力はチューリング機械のそれよりも真に小さいことが知られている。その原因は(非有界な)プレースのゼロテストができないことにある。一方, ゼロテストを可能とする拡張を行うことによってペトリネットはチューリング機械と等価になることが知られている。Merlinの時間ペトリネットはゼロテストを可能とすることが知られている。筆者らは時間ペトリネットのサブクラスである時間つき非対称選択(AC)ネットについて, 可達問題が非可解であることを示した。本報告では時間つきACネットの活性問題もまた非可解であることを示す。 |
| 抄録(英) | 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. |
| キーワード(和) | コンカレントシステム / ペトリネット / チューリング機械 / ゼロテスト |
| キーワード(英) | concurrent system / Petri net / Turing machine / zero test |
| 資料番号 | CST99-58 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CST |
|---|---|
| 開催期間 | 2000/1/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Concurrent System Technology (CST) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 時間つきACネットの活性問題の非可解性 |
| サブタイトル（和） | |
| タイトル（英） | Liveness Problem of Time AC Net is Undecidable |
| サブタイトル（和） | |
| キーワード(1)（和/英） | コンカレントシステム / concurrent system |
| キーワード(2)（和/英） | ペトリネット / Petri net |
| キーワード(3)（和/英） | チューリング機械 / Turing machine |
| キーワード(4)（和/英） | ゼロテスト / zero test |
| 第 1 著者 氏名（和/英） | 太田 淳 / Atsushi OHTA |
| 第 1 著者 所属（和/英） | 愛知県立大学情報科学部 Faculty of Information Science and Technology, Aichi Prefectural University |
| 第 2 著者 氏名（和/英） | 辻 孝吉 / Kohkichi TSUJI |
| 第 2 著者 所属（和/英） | 愛知県立大学情報科学部 Faculty of Information Science and Technology, Aichi Prefectural University |
| 発表年月日 | 2000/1/18 |
| 資料番号 | CST99-58 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 539 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |