(Japanese|English) page is also available.
太田淳のホームページへ
論文
- NP-Hardness of Liveness Problem of Bounded Asymmetric Choice Net.
A. Ohta and K. Tsuji
Institute of Electronics, Information and Comunication Engineers Trans. Fundamentals, E85-A-5, pp.1071-1074, November 2002
This paper treats computational complexity of bounded asymmetric choice (AC) net. AC net is a subclass of Petri net that properly includes the class of well-known
extended free choice net. It is shown that satisfiability problem of Boolean expressions is polynomial time reducible to liveness problem of bounded AC nets. This implies that the problem is NP-hard.
-
Polynomial Time Decidability of Monotone Liveness of Time Bounded AC/DC Nets
A. Ohta and K. Tsuji:
Institute of Electronics, Information and Comunication Engineers Trans. Fundamentals, E84-A-11, pp.2865-2870, 2001年11月
Petri net is a mathematical model for concurrent systems.
Liveness is one of important properties of Petri net.
Liveness problem of general Petri net
is of exponential space complexity and subclasses are suggested with less
computational complexity.
It is well known that liveness problem of bounded (extended) free choice net
is solved in deterministic polynomial time.
This paper treats liveness problem of AC/DC nets.
AC/DC net is a subclass of Petri net that
exhibits no confusion (mixture of concurrency and conflict).
This class properly includes the class of free choice nets.
It is shown that every minimal siphon of an AC/DC net is trap
if and only if every strongly connected siphon is a trap.
This result shows that
monotone liveness of bounded AC/DC net is solved in deterministic
polynomial time.
It is shown that this result is true of bounded time AC/DC net
with static fair condition.
-
Turing Machine Equivalence of Time Asymmetric Choice Nets
A. Ohta and K. Tsuji:
Institute of Electronics, Information and Comunication Engineers Trans. Fundamentals, E83-A-11, , 2000年11月
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.
-
On Liveneess of Time POC Nets with the Static Fair Condition
A. Ohta and T. Hisamura:
Institute of Electronics, Information and Comunication Engineers Trans. Fundamentals, E82-A-8, pp.1648-1955, 1999年8月
Merlinの時間付きペトリネットの活性問題について時間を取り去った同一の構造を持つペトリネットとの関係を考察する。発火時間に制約をつけ、同時に発火可能となったトランジションはどちらも発火できる機会があるようにする。このとき、POCネットでは時間なしネットの活性が時間つきネットの活性のための十分条件であること、またDCネットでは時間なしネットと時間つきネットの活性が互いに等価であることを示す。
-
An Algebraic Criterion for State Machine Allocatable Nets
A. Ohta and T. Hisamura:
Institute of Electronics, Information and Comunication Engineers Trans. Fundamentals, E81-A-4, pp.626-627, 1998年4月
有界自由選択ネットの活性のための条件として知られている接続行列のランクに関する条件が、(自由選択ネットとは限らず一般の)ペトリネットがSMAネットであるための必要十分条件であることを線形代数の手法を用いて示した。
-
On Some Analysis Properties of Petri Net Systems under the Earliest Firing Rule
A. Ohta and T. Hisamura:
Institute of Electronics, Information and Comunication Engineers Trans. Fundamentals, E79-A-11, pp.1791-1796, 1996年11月
即時発火ペトリネットの一般のクラスの可達問題、
活性問題などの解析問題の非可解性について検討している。ついで、自由選択ネットを包含するサブクラスの一つである非同期選択ネットを取り上げ、その即時発火規則の下でのデッドロックフリー性問題、活性問題が通常の発火規則の下のそれぞれの問題と等価であることを示し、これらの問題が、可解であることを示している。また、即時発火規則の下での外部入力付き非同期選択ネットの可達問題のための十分条件の一つも導いている。
-
On Liveness of Subclasses of Petri Nets with Permission or Inhibitor Arcs.
A. Ohta, T. Ohba and T. Hisamura:
計測自動制御学会論文集31-10, pp.1722-1729, 1995年10月
抑止枝、許可枝を付加したペトリネットの活性が決定性多項式時間で検証できるサブクラスを考察している。まず、抑止枝または許可枝のついたマークグラフの場合を考察している。一般的な必要十分条件を導いた後、多項式時間で検証できる場合として、１つのプレースから抑止枝または許可枝が出ている場合、１つのトランジションへ抑止枝、許可枝が出ている場合であることを導いている。次に、状態機械を考察し、重み１の許可枝の場合に限って、マークグラフの場合と同様な条件をグラフの可達性、強連結成分への分解などを用いて導出している。
-
単一アーク自由発火ペトリネットの記述能力
太田淳、久村富持：
計測自動制御学会論文集30-10, pp.1269-1270, 1994年10月
発火可能なトランジションはすぐに発火させる自由発火規則を導入したペトリネットにおいて、挙動的にトランジションの間の競合が生じないペトリネットはチューリング機械と等価であることが知られている。しかし、この場合にはアークに２以上の重みが必要であるとされていた。本研究では、アークの重みをすべて１にした自由発火ペトリネットが、非有界なプレースのトークン数が０か否かをテストできることを示し、このペトリネットがチューリング機械と等価であることを導いている。
-
共有資源付きタイム・ペトリネットの即時発火活性について
太田淳、久村富持：
計測自動制御学会論文集30-6, pp.694-701, 1994年6月
一般的には、通常の発火規則の下でのペトリネットの活性は、共有資源をモデル化した共有資源プレースの有無にまったく影響されないが、即時発火規則の下では、共有資源が同時進行性を制限することがあるので、活性に影響を及ぼす場合がある。とくに、発火継続時間がトランジションによって異なるタイム・ペトリネットにおいては、活性は大きな影響を受ける。本研究では、この共有資源付き即時発火タイム・ペトリネットの活性と通常の発火規則の下での活性の間の関係を考察している。
-
A Subclass of Petri Nets Where Liveness is Preserved Under the Earliest Firing Rule
A. Ohta and T. Hisamura:
Electronics and Communications in Japan, pp.1744-1752, 1994年5月
上記論文の英訳。
-
ペトリネットの活性が即時発火規則のもとで保存されるサブクラスについて
太田淳、久村富持：
電子情報通信学会論文誌J76-A-12, pp.1744-1752, 1993年12月
発火可能なトランジションをすぐに発火させる即時発火規則を導入したペトリネットの活性問題を考えている。まず、POCネットにおいて、活性が即時発火活性のための十分条件であることを導いている。つぎに、トランジションの多重発火を許した場合、拡張自由選択ネットでは、活性が即時発火活性のための必要十分条件であることを導いている。また、POCネットであり、かつ極小サイフォンがトラップであるクラスにおいても、活性であることが即時発火活性のための必要十分条件であることも導いている。
-
POC net, a subclass of Petri nets, and its application to timed Petri nets
A. Ohta and T. Hisamura:
International Journal of Systems Science 24-3, pp.539-552, 1993年3月
新しいペトリネットのサブクラスとして、POCネットを提案し、プレース活性がトランジション活性であるための必要十分条件であることを導いている。この議論は発火可能なトランジションはすぐに発火しなければならない即時発火規則の下でも成り立ち、この結果、POCネットが通常の発火規則の下で活性であれば、即時発火規則の下でも活性であることも示している。さらに、POCネットかつTCネットであるペトリネットの活性問題が決定的多項式時間で解けることを導いている。
-
ペトリネットにおける活性のトークン数増加に対する単調性について
太田淳、久村富持：
早稲田大学理工学研究所報告第136輯, pp.91-98, 1992年2月
活性問題はペトリネットの重要な解析問題の一つである。あるマーキングで活性であるペトリネットが、より多くのトークンをもつマーキングでも活性であるとは限らない。これは、資源共用問題において、無計画に資源を増やした結果、かえってシステムが正常に動作できなくなる場合に対応する。本研究では、ペトリネットの活性なマーキングが与えられたとき、トークン数の増加について活性が保存される（活性の単調性）ための条件について考察している。
-
マークグラフの可達問題の計算量
太田淳、久村富持：
電子情報通信学会論文誌J73-A-4, pp.863-868, 1990年4月
ペトリネットのサブクラスの一つであるマークグラフの可達問題については、その（可達でないことを示すための）計算量は非決定的対数領域困難であることが知られていて、
一つの下界が与えられている。本研究では、マークグラフの可達問題に関するMurataの結果にもとづき、マークグラフの可達問題が決定的多項式時間で解けることを示し、よい計算量の一つの上界を示している。さらに、初期あるいは目的マーキングが有界でない場合のマークグラフの可達問題もあわせて考察している。
-
時間付きプレースをもつペトリネットの繰返し工程スケジューリング問題への応用
太田淳、斎藤一晶、久村富持：
計測自動制御学会論文集25-6, pp.714-716, 1988年6月
繰り返し工程ジョブショップ型スケジューリング問題の周期を最小化する問題を、プレースに処理時間を表す定数と、処理待ち時間を表す変数からなるトークンの滞留時間を割り当てたタイム・ペトリネットでモデル化している。そして、ペトリネットの代数的解析法であるSifakisらのSインバリアントを用いた結果から条件式を導出し、さらに機械の制約に対応する条件式を付加して、これらを満足する最小周期解を処理待ち時間と周期を変数として求めている。
-
処理時間に不確定性を有するスケジューリング問題への確率タイム・ペトリネットの応用
斎藤一晶、太田淳、久村富持：
計測自動制御学会論文集25-4, pp.476-481, 1988年4月
工程のうちのいくつかの処理の処理時間に不確定性があり、それらがある確率分布関数に従う場合の準最適スケジューリング問題を、確率タイム・ペトリネットを用いてモデル化を行っている。そして、総処理時間の期待値を最小とする解を、可達木をもとに考察し、１個および２個の不確定処理を含む問題で数値計算の結果を、モンテカルロ法によるシミュレーション結果と対比して、その妥当性を示している。
口頭発表(フルペーパーの査読付きの国際会議など)
-
On Some Analysis Properties of Colored Petri Net using Underlying Net
A. Ohta and K. Tsuji:
Proc. IEEE MWSCAS 2004, vol.III, pp.395-398
Petri net is an effective tool to model and evaluate concurrent systems.
Colored Petri net has been proposed to model large scale systems more
effectively.
Among analysis tools for colored Petri nets, such as reachability tree,
to net invariants, to unfolded equivalent noncolored net,
we use underlying noncolored Petri net.
This method requires restriction on binding of the arc expression.
In this report, some analysis properties of colored Petri net are studied
using its underlying noncolored net.
Sufficient conditions for boundedness and persistency are derived.
Some restrictions on structure and binding are
used to obtain a necessary condition for liveness.
-
Analysis of Liviness Monotonicity in Petri Net using Insufficiently Marked Siphons
A. Ohta and K. Tsuji:
IEICE International Technical Conference on Circuits/Systems, Computers and Communications 2004, 7E3L-3(CD-ROM), July 2004
Petri net is a mathematical model for concurrent systems.
Liveness is one of important properties of Petri net.
Siphon and trap are effective tools for liveness analysis.
Existence of a token free siphon is a sufficient condition for nonliveness.
Authors has suggested insufficiently marked siphon as an extension of
token free siphon.
On the other hand, siphon and trap are also used to derive necessary condition for
liveness monotonicity.
In this report we show stronger necessary condition using insufficiently marked siphons.
-
Unfolding of Petri nets with semilinear reachability set
A. Ohta and K. Tsuji:
Proc. IEEE ISCAS 2004, vol.IV, pp.501-504, May 2004
Petri net is an effective model for concurrent systems.
State space of a general Petri net is infinite. Even if it is
finite, its size grows exponentially as the size of the net does.
This problem, called state space explosion, makes Petri net analysis hard.
Unfolding is suggested to give a compact description of
the state space of a bounded Petri net.
This is extended to unbounded net using symbol ω used in the coverability tree
generating algorithm.
However, using ω causes lack of information.
On the other hand, if unbounded Petri net has a semilinear state space,
it can be expressed without lack of information with extended coverability tree.
This paper suggests an extension of unfolding of Petri net with semilinear
state space without lack of information.
-
Insufficiently Marked Siphon of Petri Nets - Extension of Token-free Siphon
A. Ohta and K. Tsuji:
Proc. IEEE ISCAS 2003, vol.III, pp.244-247, May 2003
Petri net is a mathematical model for concurrent systems.
Liveness is one of important properties of Petri net.
A live Petri net exhibits no local deadlocks.
Siphon is a subset of places useful for liveness analysis.
Token-free siphon implies non-liveness of Petri net.
In this report, we suggest an insufficiently marked siphon
as an extended token-free siphon.
More general necessary condition for liveness is obtained
using this new status of siphons.
Two methods are proposed to obtain an insufficiently marked siphon.
-
タイムペトリネットの活性問題について
太田淳：
電子情報通信学会第10回回路とシステム軽井沢ワークショップ, 1997年4月
Merlinの時間付きペトリネットの解析問題について時間を取り去った同一の構造を持つペトリネットとの関係を述べる。ついで、時間付き自由選択ネットの活性問題の必要十分条件を導く。また、時間付きの活性問題が多項式時間で解けるクラスを示す。
口頭発表(抄録の査読付きの国際会議など)
-
Analysis of Petri Nets with Batch Processing Arcs
A. Ohta, C. Kato and K. Tsuji:
SICE Annual Conference, pp.517-520, August 2004
This paper studies analysis of Petri net extended with batch processing arcs.
If a batch processing arc is connected from a place p to a transition t,firing of t removes all tokens in p.
Turing machine equivalence and liveness condition of subclasses of batch Petri net are shown.
-
Fuzzy Timing Petri Net and Concurrency
Atsushi Ohta and Kohkichi Tsuji:
SICE(Society of Instrument and Control Engineer Japan) Annual Conference, pp.511-512, August 2003
Fuzzy timing Petri net has been suggested to
introduce time without spoiling concurrency.
This paper shows
a formal definition of fuzzy timing Petri net.
Then some problem concerning concurrency in fuzzy timing Petri net
is pointed out and
modification is suggested to cope with the problem.
-
Liveness Preserving Place Deletion in Petri Net
Atsushi Ohta, Takuo Hayashi and Kohkichi Tsuji:
IEICE International Technical Conference on Circuits/Systems, Computers and Communications 2003, pp.1755-1758, July 2003
Petri net is an effective modeling tool for concurrent systems.
Liveness problem is one of analysis problems in Petri net theory
verifying whether the system is free from any local deadlocks.
It is well-known that computational complexity of liveness problem
of general Petri net is deterministic exponential space.
This paper studies reduction method of Petri net
that preserves liveness property to cope with computational complexity.
The reduction is done by deletion of a place.
This result also derives a subclass of Petri net of which
liveness problem is NP-complete.
-
Polynomial Time Solvability of Liveness Problem of Siphon Containing Circuit Nets
A. Ohta and Kohkichi Tsuji:
Proc. IEICE International Technical Conference on Circuits/Systems, Computers and Communications 2002, pp.971-974, Jul 2002
Petri net is an effective modeling tool for concurrent systems.
Liveness problem is one of analysis problems in Petri net theory
verifying whether the system is free from any local deadlocks.
It is well known that computational complexity of liveness problem
of general Petri net is deterministic exponential space.
Some subclasses, such as marked graph and free choice net,
are suggested where liveness problem is verified
in less complexity.
This paper studies liveness of siphon containing circuit (SCC) net.
Liveness condition based on algebraic inequalities is shown.
Then polynomial time decidability of liveness of SCC net is derived,
if the given net is known to be an SCC net a priori.
-
A Consideration on Liveness Problem of Extended Strong Asymmetric Choice Nets.
A. Ohta and Kohkichi Tsuji:
Proc. IEICE International Technical Conference on Circuits/Systems, Computers and Communications 2001, pp.316-319, Jul 2001
Petri net is an effective modeling tool for concurrent systems.
Liveness problem is one of analysis problems in Petri net theory
verifying whether the system is free from any local deadlocks.
It is well known that computational complexity of liveness problem
of general Petri net is deterministic exponential space.
Some subclasses, such as marked graph and free choice net,
are suggested where liveness problem is verified
in less complexity.
This paper studies liveness of ESAC net.
ESAC net is a super class of free choice net suggested by Li et al.
It is shown that liveness problem is NP-complete for
ESAC systems where every place has at
most two output transitions.
-
On the Reachability Set of Petri Net under the Earliest Firing Rule
A. Ohta, H. Seto and K. Tsuji:
IEICE International Technical Conference on Circuits/Systems, Computers and Communications 2000, pp.641-644, July 2000
This paper studies coverability tree and reachability set of
Petri net under the earliest firing rule.
Conventional algorithm for coverability tree for `normal' Petri net
is not good for Petri net under the earliest firing rule.
Moreover, it is shown that there exists no
coverability graph for general class of earliest firing Petri net.
Some subclasses are studied where coverability graph can be
constructed.
-
On Liveness of Timed Extended Partially Ordered Condition Net under the Earliest Firing Rule
A. Ohta and Kohkichi Tsuji:
Proc. IEICE International Technical Conference on Circuits/Systems, Computers and Communications '99, pp.1156-1159, 1999年7月
Petri is an efficient modeling tool for discrete event systems.
Liveness is one of analysis problems of Petri nets,
which concerns with potential possibility of occurrence of events.
Some subclasses of Petri net are suggested with their liveness conditions.
In this report, liveness of a subclass named
extended partially ordered condition (EPOC) nets is studied.
First, equivalence of liveness and place-liveness is proved under the
normal firing rule.
Then a necessary and sufficient condition of liveness is derived.
These results are true for the earliest firing rule and
this gives a sufficient condition of an earliest firing EPOC net.
-
On Reachability Problem of Controlled Petri Nets under the Earliest Firing Rule
A. Ohta:
Proc. IEICE International Technical Conference on Circuits/Systems, Computers and Communications '98, pp.1681-1684, 1998年7月
This report treats the reachability problem of controlled
earliest firing Petri nets.
In the controlled Petri net, some transitions are controllable and
they have their external input place. The firings of these transitions
are controlled by putting token(s) in these places.
`Strict reachability problem' is to verify whether the target marking is
reachable with some appropriate control from every reachable state.
In this report strict reachability problems of some subclasses are considered.
-
On Reachability Problem of Subclasses of Time Petri Nets
A. Ohta:
Proc. IEICE International Technical Conference on Circuits/Systems, Computers and Communications, '97, pp.1179-1182, 1997年7月
Merlinの時間付きペトリネットの可達問題を考察する。一般のクラスに対して、この問題は非可解である。そこで、ペトリネットの構造を非同期選択ネットに限定し、トランジションの発火時間に、ある意味での公平性が保証されるように制約を加えることによって、可達問題が可解であるクラスを得る。
口頭発表(査読なし)
-
TPNのスケジューリング問題への応用
斎藤一晶、太田淳、久村富持：
計測自動制御学会第1回離散事象システム研究会, 1988年9月
-
マークグラフの可達性問題の計算量
太田淳、久村富持：
計測自動制御学会第3回離散事象システム研究会, 1989年5月
-
ペトリネットの活性のトークン数増大に関する単調性について
太田淳、久村富持：
計測自動制御学会第4回離散事象システム研究会, 1990年4月
-
プレース活性が活性と等価になるサブクラスとそのタイムペトリネットへの応用
太田淳、久村富持：
計測自動制御学会第7回離散事象システム研究会, 1991年5月
-
あるクラスのタイムペトリネットの活性について
太田淳、久村富持：
第30回計測自動制御学会学術講演会, 1991年7月
ペトリネットの新たなサブクラスである、DOSIネット、DISOネットを提案し、それらの活性は、即時発火規則のもとで、時間を導入しても保存されることを示した。
-
共有資源付きタイムペトリネットの活性について
太田淳、久村富持：
第31回計測自動制御学会学術講演会, 1993年7月
-
容量制限プレースをもつペトリネットの活性に関する一考察
太田淳、久村富持：
計測自動制御学会第12回離散事象システム研究会, 1993年12月
プレースに入るトークン数に上限をつけたペトリネットの活性問題を考察した。相補プレースを用い、有向閉路に着目することにより、容量制限付きの状態機械、マークグラフ、無競合ネット、非減少閉路ネットについて、活性問題が多項式時間で解けることを示した。
-
許可枝を持つペトリネットのサブクラスの活性問題について
太田淳、大場敏行、久村富持：
計測自動制御学会第13回離散事象システム研究会, 1994年7月
-
許可枝付きマークグラフの活性問題に関する一考察
太田淳、久村富持：
第33回計測自動制御学会学術講演会, 1994年7月
-
繰り返し工程ジョブショップ型スケジューリング問題のタイム・マークグラフを用いた準最適解解法
太田淳、久村富持：
計測自動制御学会システム情報合同シンポジウム, 1994年10月
ジョブショップ型スケジューリング問題における、競合の解決を、タイム・マークグラフの初期マーキング配置問題に定式化し、Laftitらによって提案されたアルゴリズムを用いて準最適周期解を求める。
-
即時発火ペトリネットの有界性に関する一考察
太田淳、久村富持：
電子情報通信学会技術研究報告94-332, pp.117-124, 1994年11月
即時発火ペトリネットの有界性問題が非可解であることを示した。そのサブクラスである、即時発火マークグラフ、即時発火無競合ネットの有界性問題に対して、グラフの強連結成分を利用した多項式時間アルゴリズムを提案した。
-
許可枝をもつペトリネットの結合系の活性について
太田淳、大場敏行、久村富持：
計測自動制御学会第15回離散事象システム研究会, 1994年12月
許可枝が1つのみのプレースあるいは1つのみのトランジションに接続する状態機械あるいはマークグラフを結合してできる許可枝付き状態機械とマークグラフの活性問題を考察する。
-
タイム・ペトリネットの最短時間可達問題
太田淳、久村富持：
電子情報通信学会技術研究報告95-137, pp.23-28, 1995年7月
タイム・ペトリネットにおいて、与えられた初期マーキングから最終マーキングへ最短時間で到達する問題を考察する。一般には、即時発火による解が必ずしも最適であるとは限らないこと、非同期選択ネットでは最適であることを示した。また、状態機械の最短時間可達問題に対する、グラフの最短経路問題を利用した多項式時間アルゴリズムを提案した。
-
許可枝付きタイムマークグラフの性能評価について
太田淳、久村富持：
第34回計測自動制御学会学術講演会, 1995年7月
許可枝のついたタイムマークグラフの与えられた周期による周期動作を実現するための重みつき和最小の初期マーキングを求める問題を考察した。この問題に対して、多項式時間の近似アルゴリズムを2つ提案した。
-
SMAネットの代数的判別法
太田淳、久村富持：
1995年電子情報通信学会基礎・境界ソサイエティ大会, 1995年9月
-
ペトリネットの活性の単調性のための十分条件
太田淳、久村富持：
計測自動制御学会システム情報合同シンポジウム, 1995年10月
拡張されたアークの解放を提案し、これを用いてペトリネットの活性が初期トークンの増加に対して保たれるための一つの十分条件を導いた。
-
即時発火ペトリネットの解析に関する一考察
太田淳、久村富持：
計測自動制御学会第17回離散事象システム研究会, 1996年1月
-
即時発火ペトリネットの解析における帰着問題
太田淳、久村富持：
電子情報通信学会技術研究報告96-58, pp.9-14, 1996年5月
即時発火ペトリネットの各種の可達問題、各種の活性問題の間の帰着関係を示した。また、これらの問題に対応する言語が帰納的可算であるかどうか、帰納的であるかどうかを導いた。
-
非同期選択ネットの即時発火活性について
太田淳、久村富持：
計測自動制御学会第18回離散事象システム研究会, 1996年5月
-
時間付きペトリネットのサブクラスの活性問題について
太田淳、久村富持：
第35回計測自動制御学会学術講演会, 1996年7月
トランジションに最小発火遅れと最大発火遅れを導入したMerlinのタイムペトリネットの活性問題を考察する。そして、発火時間に制約をつけた非同期選択ネットについて、活性のための必要十分条件を導いた。
-
制御されたサイフォンに関する一考察
太田淳、久村富持：
計測自動制御学会システム情報合同シンポジウム, 1996年10月
サイフォンがトークンを持ち続けるための線形代数を用いたLautenbachらによる十分条件を拡張する。また、Barkaouiらによる制御できないサイフォンのための集合の分割の具体的な方法の一つを与える。
-
発火時間に制約を加えた時間ペトリネットのサブクラスの活性問題
太田淳、久村富持：
電子情報通信学会技術研究報告96-309, pp.9-14, 1996年10月
Merlinタイムペトリネットの活性問題を考察する。発火時間に制約をつけた非対称選択ネットについて、活性のための十分条件を導いた。
-
タイムペトリネットの繰り返し工程ジョブショップ型スケジューリング問題への応用
太田淳、久村富持：
電気学会産業システム情報化研究会IIS97-3, 1997年1月
「繰り返し工程ジョブショップ型スケジューリング問題のタイム・マークグラフを用いた準最適解解法」のアルゴリズムについて、計算量を軽減する方策を提案した。
-
発火時間に制約を加えた時間付きPOCネットの活性問題
太田淳、久村富持：
電子情報通信学会技術研究報告96-493, pp.7-14, 1997年1月
Merlinのタイムペトリネットの活性問題を考察する。発火時間に制約をつけたPOCネットについて、活性のための十分条件を導いた。
-
対応する時間なしペトリネットを用いた色付きペトリネットの解析に関する一考察
太田淳：
電子情報通信学会技術研究報告97-51, pp.33-37, 1997年5月
色付きペトリネットは、ペトリネットの構成要素に色を導入することで、大規模なシステムの複雑さを、ネット構造と付加情報である色とに分割するモデルである。その色付きペトリネットの解析の一つの方法として、色を除去したネットとの関連を考察する。とくに、あるクラスの色付きペトリネットの活性のための必要条件を導く。
-
即時発火ペトリネットの状態空間のBDDによる表現
太田淳：
電子情報通信学会技術研究報告97-156, pp.1-6, 1997年7月
ペトリネットの状態空間の爆発的増大に対する解決法として提案された二分決定木による表現を、即時発火ペトリネットの状態空間表現に拡張した。
-
即時発火ペトリネットの構造と可達問題の関係についての一考察
太田淳：
計測自動制御学会システム／情報合同シンポジウム'97講演論文集, pp.95-98, 1997年11月
即時発火規則におけるトランジションの発火回数を制御できる場合の可達問題が可解であるクラスに、弱パーシステントネット、非同期選択ネットがある。これらの構造上の制約が可解性のために本質的であることを示す。
-
即時発火ペトリネットの状態空間のunfoldingによる表現法の検討
太田淳：
電子情報通信学会技術研究報告97-507, pp.9-12, 1998年1月
ペトリネットの状態空間の爆発的増大に対する解決法として提案されたunfoldingによる表現を、即時発火ペトリネットの状態空間表現に拡張した。
-
制御された即時発火ペトリネットのサブクラスの「完全」可到達問題について
太田淳：
電子情報通信学会技術研究報告98-87, pp.25-30, 1998年5月
-
AC/DCネットの挙動的トラップの代数的表現について
太田淳：
電子情報通信学会技術研究報告98-220, pp.9-13, 1998年7月
-
AC/DCネットの制御されたサイフォンについての一考察
太田淳：
計測自動制御学会システム／情報合同シンポジウム'98講演論文集, pp.25-28, 1998年11月
-
Pインバリアントを用いたペトリネットのフィードバック制御問題の線形計画法を用いた一解法
太田淳：
電子情報通信学会技術研究報告98-565, pp.9-13, 1999年1月