時間つきACネットの活性問題の非可解性
スポンサーリンク
概要
- 論文の詳細を見る
ペトリネットはコンカレントシステムのモデルの一つである。ペトリネットのモデル化能力はチューリング機械のそれよりも真に小さいことが知られている。その原因は(非有界な)プレースのゼロテストができないことにある。一方, ゼロテストを可能とする拡張を行うことによってペトリネットはチューリング機械と等価になることが知られている。Merlinの時間ペトリネットはゼロテストを可能とすることが知られている。筆者らは時間ペトリネットのサブクラスである時間つき非対称選択(AC)ネットについて, 可達問題が非可解であることを示した。本報告では時間つきACネットの活性問題もまた非可解であることを示す。
- 2000-01-18
論文 | ランダム
- グローバル戦略とインターネット
- ハイテクばんざい! 肢体不自由者とパソコン--パソコン入力のための支援
- 誘導機形ベアリングレスモータの半径方向力制御に最適な二次抵抗設定値
- 欧米における通信政策の新動向
- 視線移動を考慮した頸髄損傷者用ペン型ポインティングデバイス(次世代ヒューマンインタフェース・インタラクション)