| 講演抄録／キーワード |
| 講演名 |
2004-11-04 15:45
プログラムネットの不活性について
○山田紘輔・山口真悟・葛 崎偉・田中 稔（山口大） |
| 抄録 |
（和） |
本稿はプログラムネットの不活性を議論する．まずプログラムネットの不活性の定義を与える．プログラムネットは任意の発火系列で発火可能にできないノードを持つとき，部分的不活性であると言う．我々は不活性問題を，与えられたプログラムネットが部分的不活性であるかどうかを判定する問題と定義する．我々はプログラムネットを4つのクラスに分類する：一般ネット，非循環ネット，SWITCH-lessネット，非循環SWITCH-lessネット．それから，各クラスに対して不活性問題の判定法を議論する．以下の結果が得られた：(1) 非循環SWITCH-lessネットは部分的不活性ではない．(2) SWITCH-lessネットに対しては，不活性問題は多項式時間で解くことができる．(3) 非循環ネットおよび一般ネットに対しては，不活性問題はおそらくNPに含まれないと考えられる． |
| （英） |
This paper discusses dead for program nets. We first give the definition of
dead for program nets. A program net is said to be partially dead if the net consists of nodes which never become firable in any possible firing sequence. We define dead problem as a problem to deciding whether a given program net is partially dead or not. We classify program nets into 4 classes: general, acyclic, SWITCH-less, and acyclic SWITCH-less nets. Then we discuss methods of solving dead problem for each class. The results are as follows: (1) Acyclic SWITCH-less nets are not partially dead. (2) For SWITCH-less nets, the dead problem can be solved in polynomial time. (3) For acyclic nets and general nets, the dead problem seems not to be included in NP class. |
| キーワード |
（和） |
データフロープログラム / プログラムネット / 不活性 / 判定アルゴリズム / 計算複雑さ / / / |
| （英） |
dataflow program / program net / dead / decision algorithm / computation complexity / / / |
| 文献情報 |
信学技報, vol. 104, 2004年11月. |
| 資料番号 |
|
| 発行日 |
2004-10-28 (CAS, CST) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|
|