(57)【要約】本発明は、バイナリ・デシジョン・ダイアグラム（BDD）からなる故障の木の最小カットセットを算出する最小カットセット算出システムであって、再帰部分と基本部分とからなる再帰関数を用いて、入力されたBDDの二つのサブBDDのうちの一つのサブBDDから、他のサブBDDに含まれる冗長パスを除去する減算手段を有し、前記減算手段は、前記基本部分に、前記二つのサブBDDが終端ノードではなく、等価である場合に、終端ノード０を出力する等価除去手段を含む最小カットセット算出システムである。
2013085025.tif 000002
【特許請求の範囲】
【請求項１】
バイナリ・デシジョン・ダイアグラム（BDD）からなる故障の木の最小カットセットを算出する最小カットセット算出システムであって、
再帰部分と基本部分とからなる再帰関数を用いて、入力されたBDDの二つのサブBDDのうちの一つのサブBDDから、他のサブBDDに含まれる冗長パスを除去する減算手段を有し、
前記減算手段は、前記基本部分に、前記二つのサブBDDが終端ノードではなく、等価である場合に、終端ノード０を出力する等価除去手段を含む
最小カットセット算出システム。
【請求項２】
前記減算手段は、前記二つのサブBDDの終端ノードの判定及び前記二つのサブBDDの等価の判定後に、前記再帰部分を用いて冗長パスを除去する
請求項１に記載の最小カットセット算出システム。
【請求項３】
再帰部分と基本部分とからな再帰関数を用いて、BDDからなる故障の木の最小カットセットを算出する最小化手段を有し、
前記最小化手段は、前記減算手段によりサブBDDの冗長パスが除去された後に、前記再帰部分の計算を行って前記サブBDDの最小化する
請求項１又は請求項２に記載の最小カットセット算出システム。
【請求項４】
バイナリ・デシジョン・ダイアグラム（BDD）からなる故障の木の最小カットセットを算出する最小カットセット算出システムであって、
再帰部分と基本部分とからな再帰関数を用いて、BDDからなる故障の木の最小カットセットを算出する最小化手段を有し、
前記最小化手段は、前記BDDのサブBDDの冗長パスが除去された後に、前記再帰部分の計算を行う
最小カットセット算出システム。
【請求項５】
バイナリ・デシジョン・ダイアグラム（BDD）からなる故障の木の最小カットセットを算出する最小カットセット算出方法であって、
再帰部分と基本部分とからなる再帰関数を用いて、入力されたBDDの二つのサブBDDのうちの一つのサブBDDから、他のサブBDDに含まれる冗長パスを除去する減算処理を有し、
前記減算処理は、前記基本部分に、前記二つのサブBDDが終端ノードではなく、等価である場合に、終端ノード０を出力する等価除去処理を含む
最小カットセット算出方法。
【請求項６】
前記減算処理は、前記二つのサブBDDの終端ノードの判定及び前記二つのサブBDDの等価の判定後に、前記再帰部分を用いて冗長パスを除去する
請求項５に記載の最小カットセット算出方法。
【請求項７】
再帰部分と基本部分とからな再帰関数を用いて、BDDからなる故障の木の最小カットセットを算出する最小化処理を有し、
前記最小化処理は、前記減算処理によりサブBDDの冗長パスが除去された後に、前記再帰部分の計算を行って前記サブBDDの最小化する
請求項５又は請求項６に記載の最小カットセット算出方法。
【請求項８】
バイナリ・デシジョン・ダイアグラム（BDD）からなる故障の木の最小カットセットを算出する最小カットセット算出方法であって、
再帰部分と基本部分とからな再帰関数を用いて、BDDからなる故障の木の最小カットセットを算出する最小化処理を有し、
前記最小化処理は、前記BDDのサブBDDの冗長パスが除去された後に、前記再帰部分の計算を行う
最小カットセット算出方法。
【請求項９】
バイナリ・デシジョン・ダイアグラム（BDD）からなる故障の木の最小カットセットを算出する最小カットセット算出プログラムであって、
前記最小カットセット算出プログラムは、コンピュータに、
再帰部分と基本部分とからなる再帰関数を用いて、入力されたBDDの二つのサブBDDのうちの一つのサブBDDから、他のサブBDDに含まれる冗長パスを除去する減算処理を実行させ、
前記減算処理は、前記基本部分に、前記二つのサブBDDが終端ノードではなく、等価である場合に、終端ノード０を出力する等価除去処理を含む
最小カットセット算出プログラム。
【請求項１０】
バイナリ・デシジョン・ダイアグラム（BDD）からなる故障の木の最小カットセットを算出する最小カットセット算出方法プログラムであって、
前記最小カットセット算出プログラムは、コンピュータに、
再帰部分と基本部分とからな再帰関数を用いて、BDDからなる故障の木の最小カットセットを算出する最小化処理を実行させ、
前記最小化処理は、前記BDDのサブBDDの冗長パスが除去された後に、前記再帰部分の計算を行う
最小カットセット算出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最小カットセット評価システム、最小カットセット算出方法及びプログラムに関し、特にバイナリ・デシジョン・ダイアグラム（BDD）からなる故障の木の最小カットセット（MCS）を算出するための最小カットセット評価システム、最小カットセット算出方法及びプログラムに関する。
【背景技術】
【０００２】
非特許文献１および非特許文献２に、本発明に関連する技術が記載されている。そして、非特許文献１に記載されている従来のアルゴリズムを図１および図２に示す。【０００３】
図１および図２に示された従来のアルゴリズムは、“minsol”および “without”と名付けられた二つの再帰関数（recursive functions）から構成される。これらは与えられた二分決定図（Binary Decision Diagram：以下、BDDと記載する）の最小解を算出するためのものであり、他のBDDのパスに含まれる冗長パスを、BDDから除去するためのものである。【０００４】
従来のアルゴリズムは、複数のBDDからなる故障の木における最小カットセット（MCSs）を算出する典型的な手法と見なされてきたが、下記に述べるようにいまだに課題がある。【０００５】
第１に、図２に示すように関数“without”は、入力される二つのBDD(FおよびG)のひとつが１又は０の終端ノードである場合の再帰呼び出しをしない基本部分（ベースケース）のみを考慮しており、入力される二つのBDDが終端ノードではない同じノードである場合、つまり、
2013085025.tif 000003
の場合の基本部分（ベースケース）を考慮していない。【０００６】
このような場合において、ふたつの入力されるBDDであるFとGは、それらが等価であるか等価でないかにかかわらず、関数“without”によって再帰的に分解して評価しなければならない（図２の最後のelseのx = yを参照）。この場合の再帰的な分解と評価は、F = Gであるから明らかに不要である。【０００７】
既約BDD（Reduced BDD）がite (x, F, F)（iteは、if-then-elseによる分解を表す）のフォームの中に無用なノードを含んでいない場合、すなわち、
2013085025.tif 000004
の場合の基本部分（ベースケース）の省略は可能である。【０００８】
しかしながら、ひとつのBDDの中の共有ノードの存在に起因して、無用なノードがBDD内に存在しない場合であっても、without (F,F)を適用することが度々起こりうる。【０００９】
第２に、図１に示すように関数“without”は、Fの最小化の過程で、FのサブBDDであるGの最小化（最小解の算出）の後に呼び出される。加えて、非特許文献２の定理１０がに示されているように、オリジナルBDDを最小化する過程でふたつのサブBDDを最小化した後に関数“without”を呼び出すような修正が提案されている。このように、非特許文献の技術では、関数“without”は、ふたつのサブBDDが最小化される前には呼び出されない。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】A. Rauzy: New algorithms for fault trees analysis, Reliability Engineering and System Safety, 40(3), Elsevier, 1993, pp. 203-211
【非特許文献２】Y. Dutuit and A. Rauzy: Exact and Truncated Computations of Prime Implicants of Coherent and Non-Coherent Fault Trees with Aralia, Reliability Engineering and System Safety, 58(2), Elsevier, 1997, pp. 127-144.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
上述した技術において、以下の課題がある。【００１２】
第１の課題は、上記非特許文献の技術は、等価なふたつのBDDに対して、冗長パスの除去する不必要な処理が再帰的に適用されるということである。その理由は、従来のアルゴリズムが関数“without”のふたつの入力BDDが等価である場合における再帰呼び出しをしない基本部分（ベースケース）を検討しておらず、また、BDDはite (x, F, F)のフォームに無用なノードを含んでいないということを前提にしているからである。【００１３】
第２の課題は、上記非特許文献の技術のように、関数“without”を後から処理する方法は、最小化の効率を悪化させるということである。BDDの最小化のパフォーマンスは、そのBDDのサブBDDの大きさに一般的に依存する。そして、BDDを設定する時、そのBDDのサブBDDの最小化が不十分な場合があり、上記非特許文献のアルゴリズムのように、他のサブBDDのパスに含まれる冗長パスをサブBDDから事前に除去せずに行えば、サブBDDを最小化する処理の負荷が多くなるからである。【００１４】
そこで、本発明は上記課題に鑑みて発明されたものであって、その目的は、バイナリ・デシジョン・ダイアグラム（BDD）からより効果的な方法で、故障の木の最小カットセットを算出する技術を提供することにある。
【課題を解決するための手段】
【００１５】
本発明は、バイナリ・デシジョン・ダイアグラム（BDD）からなる故障の木の最小カットセットを算出する最小カットセット算出システムであって、再帰部分と基本部分とからなる再帰関数を用いて、入力されたBDDの二つのサブBDDのうちの一つのサブBDDから、他のサブBDDに含まれる冗長パスを除去する減算手段を有し、前記減算手段は、前記基本部分に、前記二つのサブBDDが終端ノードではなく、等価である場合に、終端ノード０を出力する等価除去手段を含む最小カットセット算出システムである。【００１６】
本発明は、バイナリ・デシジョン・ダイアグラム（BDD）からなる故障の木の最小カットセットを算出する最小カットセット算出システムであって、再帰部分と基本部分とからな再帰関数を用いて、BDDからなる故障の木の最小カットセットを算出する最小化手段を有し、前記最小化手段は、前記BDDのサブBDDの冗長パスが除去された後に、前記再帰部分の計算を行う最小カットセット算出システムである。【００１７】
本発明は、バイナリ・デシジョン・ダイアグラム（BDD）からなる故障の木の最小カットセットを算出する最小カットセット算出方法であって、再帰部分と基本部分とからなる再帰関数を用いて、入力されたBDDの二つのサブBDDのうちの一つのサブBDDから、他のサブBDDに含まれる冗長パスを除去する減算処理を有し、前記減算処理は、前記基本部分に、前記二つのサブBDDが終端ノードではなく、等価である場合に、終端ノード０を出力する等価除去処理を含む最小カットセット算出方法である。【００１８】
本発明は、バイナリ・デシジョン・ダイアグラム（BDD）からなる故障の木の最小カットセットを算出する最小カットセット算出方法であって、再帰部分と基本部分とからな再帰関数を用いて、BDDからなる故障の木の最小カットセットを算出する最小化処理を有し、前記最小化処理は、前記BDDのサブBDDの冗長パスが除去された後に、前記再帰部分の計算を行う最小カットセット算出方法である。【００１９】
本発明は、バイナリ・デシジョン・ダイアグラム（BDD）からなる故障の木の最小カットセットを算出する最小カットセット算出プログラムであって、前記最小カットセット算出プログラムは、コンピュータに、再帰部分と基本部分とからなる再帰関数を用いて、入力されたBDDの二つのサブBDDのうちの一つのサブBDDから、他のサブBDDに含まれる冗長パスを除去する減算処理を実行させ、前記減算処理は、前記基本部分に、前記二つのサブBDDが終端ノードではなく、等価である場合に、終端ノード０を出力する等価除去処理を含む最小カットセット算出プログラムである。【００２０】
本発明は、バイナリ・デシジョン・ダイアグラム（BDD）からなる故障の木の最小カットセットを算出する最小カットセット算出方法プログラムであって、前記最小カットセット算出プログラムは、コンピュータに、再帰部分と基本部分とからな再帰関数を用いて、BDDからなる故障の木の最小カットセットを算出する最小化処理を実行させ、前記最小化処理は、前記BDDのサブBDDの冗長パスが除去された後に、前記再帰部分の計算を行う最小カットセット算出プログラムである。
【発明の効果】
【００２１】
本発明によれば、バイナリ・デシジョン・ダイアグラム（BDD）から効果的な方法で、故障の木の最小カットセットを算出することができる。
【図面の簡単な説明】
【００２２】
【図１】図１は非特許文献１のminsol関数を示す図である。
【図２】図２は非特許文献１のwithout関数を示す図である。
【図３】図３は本発明の実施の形態の構成を示すブロック図である。
【図４】図４は本発明の実施の形態の動作フローチャートである。
【図５】図５は本発明の実施の形態の動作フローチャートである。
【図６】図６は“minsol”関数を示す図である。
【図７】図７は“without”関数を示す図である。
【図８】図８は他の“without”関数を示す図である。
【図９】図９は実施例におけるBDDを示した図である。
【図１０】図１０は図９に示すBDDに、without(3, 2)が適用された後のBDDを示した図である。
【図１１】図１１は本発明による関数の呼び出し回数と、従来技術による関数の呼び出し回数との比較結果を示した図である。
【図１２】図１２は、所定の故障の木について、本発明と従来技術とを適用した場合の比較結果を示した図である。
【発明を実施するための形態】
【００２３】
次に、本発明の実施の形態について図面を参照して詳細に説明する。
【００２４】
図３で参照される本発明の実施の形態は、最小化手段１１０と減算手段１２０とを含む。減算手段１２０は、等価除去手段１２１を含む。
【００２５】
これらの手段はそれぞれ概略つぎのように動作する。
【００２６】
最小化手段１１０は、与えられたBDDの最小カットセット（ＭＣＳｓ）を算出するものである。そして、最小化手段１１０は、あるサブBDDが終端ノードではない場合、そのサブBDDから、他のサブBDDのパスに含まれる全ての冗長パスを除去するために、減算手段１２０を呼び出す。
【００２７】
減算手段１２０は、あるサブBDDが終端ノードではない場合、そのサブBDDから、他のサブBDDのパスに含まれる全ての冗長パスを除去する。
【００２８】
等価除去手段１２１は、減算手段１２０に入力された二つのBDDが等価であるか不等価であるかを調べ、二つのBDDが等価であれば終端ノードとして０（偽）を出力する。すなわち、第１のBDDと第２のBDDとが等価ならば、第１のBDDの全てのパスは第２のBDDに含まれ、結果として、終端ノード０（偽）を出力する。
【００２９】
上記の構成において、最小化手段１１０は、入力BDDのふたつのBDDを再帰的に最小化の処理を行う前に、減算手段１２０を呼び出す。そして、減算手段１２０で冗長パスが除去された後に、サブBDDの最小化の再帰的計算を行う。
【００３０】
次に、図３及び図４，５のフローチャート、図６に示される関数minsol、図７に示される関数withoutを参照し、本実施の形態の全体の動作について詳細に説明する。
【００３１】
まず、ひとつのBDD（以下、ＢＤＤ＿Fと記載する）がシステムに入力され（ステップＡ１）、最小化手段１１０によって処理される。ここでは、非特許文献１のアルゴリズムと比較するために“minsol”という同じ名称を使用し、最小化手段１１０が用いる関数として定義する。
【００３２】
最小化手段１１０は、ＢＤＤ＿Fが終端ノード（０終端又は１終端）であるかをチェックする（ステップＡ２）。ＢＤＤ＿Fが終端ノードであれば（ステップＡ２  Ｙｅｓ）、ＢＤＤ＿Fをそのまま返す（ステップＡ３）。ＢＤＤ＿Fが終端ノードではなく、F = ite(x, G, H)（xはブーリアン変数、Gは１の枝で接続されているＢＤＤ＿FのサブＢＤＤ（ノード）、Hは０の枝で接続されているＢＤＤ＿FのサブＢＤＤ（ノード））の形をとっている場合（ステップＡ２  Ｎｏ）、減算手段120により、関数without(G, H)を呼び出され、その返値を中間変数Kとして与えられる（ステップＡ４）。尚、関数withoutは、サブＢＤＤ＿Hのパスに含まれるすべてのパスを、サブＢＤＤ＿Gから除去するために、減算手段１２０が用いる関数である。
【００３３】
関数without関数により冗長パスが除去された後、関数milsol(K)が再帰的に呼び出しされ、その返値は中間変数Uとして保存される（ステップＡ５）。
【００３４】
関数minsol(H)の再帰呼び出しは、ＢＤＤ＿Fの０の枝で接続されているサブＢＤＤ＿Hに関して実行され、その返値は中間変数Vとして保存される（ステップＡ６）。
【００３５】
最後に、必要であれば（例えば、非特許文献１および２で提案されているように関数iteの記憶を実行する場合）、保存されている中間変数U,Vから新しいBDDであるite(x, U, V)が生成され（ステップＡ７）、Ｒとして出力される（ステップＡ８）。
【００３６】
続いて、減算手段１２０が行うステップＡ４の処理について、図５のフローチャートを用いて説明する。
【００３７】
関数without(G, H)を実行するために（ステップＡ４１）、減算手段１２０は、サブＢＤＤ＿Gおよび／またはサブＢＤＤ＿Hが、終端ノード（０終端又は１終端）であるかをチェックする（ステップＡ４２）。サブＢＤＤ＿Gおよび／またはサブＢＤＤ＿Hが、終端ノード（０終端又は１終端）である場合には（ステップＡ４２  Yes）、終端ノード（０終端又は１終端）の場合における再帰呼び出しをしない基本部分（ベースケース）（図７の２行目から６行目に記載）が適用され（ステップＡ４４）、その結果が出力される（ステップＡ４６）。
【００３８】
サブＢＤＤ＿Gおよび／またはサブＢＤＤ＿Hが、終端ノード（０終端又は１終端）ではない場合には（ステップＡ４２  No）、減算手段１２０の等価除去手段１２１は、サブＢＤＤ＿GとサブＢＤＤ＿Hとが等価（非終端ノードBDD）であるかをチェックする（ステップＡ４３）。
【００３９】
サブＢＤＤ＿GとサブＢＤＤ＿Hとが等価である場合には（ステップＡ４３  Yes）、関数withoutの再帰的計算を行わずに、結果として０を出力する（ステップＡ４７）。一方、サブＢＤＤ＿GとサブＢＤＤ＿Hとが等価でなければ（ステップＡ４３  No）、終端ノードではない場合の再帰部分（図７の７行目から１８行目に記載）が適用され（ステップＡ４５）、その結果が出力される（ステップＡ４６）。
【００４０】
尚、サブＢＤＤ＿GとサブＢＤＤ＿Hとが等価であるかのチェックは、サブＢＤＤ＿GとサブＢＤＤ＿Hとが終端ノードであるかのチェックの前に行うこともできる。その場合の減算手段１２０が用いる関数withoutに対応する変数を図８に示す。
【００４１】
次に、本実施の形態の効果について説明する。
【００４２】
第１の効果は、再帰的な処理を行うことなく、二つの等価なBDD間の冗長パスを除去することができるという効果である。何故なら、二つのBDDが等価であれば、第１のBDDのすべてのパスは第２のBDDに含まれ、減算手段の等価除去手段が結果として終端ノード０（偽）を出力するからである。
【００４３】
第２の効果は、最小カットセット（ＭＣＳ）の算出の効率を全体的に高めることができるという効果である。何故なら、サブBDDの最小化の前に冗長パスを除去すれば、サブBDDのサイズと複雑さが縮小され、サブBDDを最小化するコストが削減されるからである。
【００４４】
次に、具体的な実施例を用いて本発明の動作を説明する。
【００４５】
図９にBDDの一例を示す。
【００４６】
図９に示されるBDDの論理式は、
2013085025.tif 000005
である。ここでは、説明を簡潔にするため、各BDDノードのアドレスに自然数を用い、１の枝を実線の矢印、０の枝を点線の矢印で示している。また、分解・構築のためのＢＤＤ＿Fの変数の順序を、a＜b＜cとする。
【００４７】
図９に示されるBDDは、２つの共有終端ノード（０終端と１終端）に加えて、３つのBDDノードがある。終端ノードを除くBDDノードは、ｎ、ｘ、ｉ及びｊの４つの部分からなり、ｎは例えばhash-tableの中のアドレスを示し、ｘはブーリアン変数、ｉは１の枝で接続されるサブのＢＤＤ（ノード）のアドレスを示し、ｊは０の枝で接続されるサブのＢＤＤ（ノード）のアドレスを示す。そして、アドレス４のノードはite(a, 3, 2)、アドレス３のノードはite(b,1,2)、アドレス２のノードはite(c,1,0)と表すことができる。
【００４８】
アドレス２のノードite(c, 1, 0)は、２つの親ノードite(a, 3, 2)と、ite(b, 1, 2)との共有ノードである。
【００４９】
最小化手段１１０が、関数minsol(4)でBDDの最小カットセット（solutions）を計算する（図４のステップＡ１）。本例では、入力パラメーターである４（＝Ｆ）が終端ノード（０終端又は１終端）であるかをチェックする（図４のステップＡ２）。ここでは、Ｆ＝４は終端ノードではない。そこで、アドレス４のサブBDDノードであるアドレス３のサブBDDノードとアドレス２のサブBDDノードとの間の冗長パスを除去するため、関数without（3,2）を呼び出す（図４のステップＡ４及び図５のステップＡ４１）。
【００５０】
アドレス３のサブBDDノードとアドレス２のサブBDDノードとは終端ノードではなく（ステップＡ４２  No）、等価ではないので（ステップＡ４３  No）、図７の８行目から１２行目に記載されている、x ＜ yの場合に基づいて、二つの再帰関数であるwithout(1,2) と without(2,2)とが呼び出される。（図５のステップＡ４５）。
【００５１】
図７の６行目に記載されている通り、関数without(1, 2)の結果として１が返される。関数without(2,2)の結果は、０が返される。そして、関数without(1,2) と without(2,2)の結果により、アドレス５のite(b, 1, 0)の新しいBDDノードが生成される。新しいBDDノードは、関数without(3, 2)の結果として出力される（図５のステップＡ４６）。関数without(3, 2)の処理後の修正されたBDDを図１０に示す。
【００５２】
図１０に示されるBDDに基づいて行われるminsol(5)とminsol(2)とは同様に簡易なものであり、最小解のみをもつ最終出力されるBDDは、図１０に示したものと同じである。なぜなら、minsol(5) と minsol(2)の以後は変化しないからである。
【００５３】
ここで、本発明と非特許文献１に示される従来アルゴリズムとの違いを明確にするため、ふたつのアルゴリズムでふたつの関数“minsol”と“without”とが呼び出される回数の統計データを図１１に示す。
【００５４】
この数値は、ふたつのアルゴリズムを、プログラミング言語のひとつであるPython（パイソン）に実装して得られた値である。本発明による方法により“without”関数の呼び出し回数は、本実例において６から４へと約３０％減少している。
【００５５】
更に、非特許文献１に記載されている故障の木の実例により、本発明の効率性を示す。
【００５６】
この故障の木の名称はEuropean 1で、非特許文献１の付録に収録されている。この故障の木は６１の基本イベント（変数）と８４のゲート（connectives）からなり、その大きさ（基本イベントとゲートの数の合計）は１４５である。尚、引用文献にはふたつの誤記がある。つまり、ゲートg118とゲートg117とはそれぞれ、g118:= (g114 | c047)およびg117 := (g113 | c046)とすべきであり、g118 := (g114 | g047) and g117 := (g113 | g046)ではない。
【００５７】
関数呼出数で従来アルゴリズムと本発明の方法とを比較した統計データを図１２に示す。
【００５８】
この例においては、等価のBDDを構築するために両方法とも深さ優先順序、すなわち基本イベントは出現順に番号付けされる方法を採用した。
【００５９】
尚、BDDの大きさは９１６５で、非特許文献１に示された６０４４の大きさのものとは異なる。その理由は、非特許文献１において、順序付け方法は深さ優先探索と呼ばれているが、その順序づけ方法と本発明の方法とに若干の相違がある可能性がある。非特許文献１では順序付け方法の詳細が記載されていないので、双方の順序づけ方法のあいだの違いをここでは正確に明らかにすることができない。
【００６０】
本発明の順序づけ方法により構築されたBDDでは２２０２の共有ノードがあった。これにより、BDDは無視できない数の共有ノードを持ちうるかもしれないという事実を示している。本発明の方法は、このような共有ノードをより効率的に処理できる方法であることをまさに示している。図１２に示すようにふたつの関数“minsol”と“without”とに対する呼出数を１５％縮減することができ、さらには、実践的なベンチマークとなる故障の木に関して、本発明の方法の効率性が示されている。
【００６１】
以上で実施の形態の説明を終わるが、上述した説明からも明らかなように、各部をハードウェアで構成することも可能であるが、コンピュータプログラムにより実現することも可能である。この場合、プログラムメモリに格納されているプログラムで動作するプロセッサによって、上述した各実施の形態又は実施例と同様の機能、動作を実現させる。また、上述した実施の形態又は実施例の一部の機能のみをコンピュータプログラムにより実現することも可能である。
【００６２】
また、上記の実施の形態の内容は、以下のようにも表現されうる。
【００６３】
（付記１）  バイナリ・デシジョン・ダイアグラム（BDD）からなる故障の木の最小カットセットを算出する最小カットセット算出システムであって、
再帰部分と基本部分とからなる再帰関数を用いて、入力されたBDDの二つのサブBDDのうちの一つのサブBDDから、他のサブBDDに含まれる冗長パスを除去する減算手段を有し、
前記減算手段は、前記基本部分に、前記二つのサブBDDが終端ノードではなく、等価である場合に、終端ノード０を出力する等価除去手段を含む
最小カットセット算出システム。
【００６４】
（付記２）  前記減算手段は、前記二つのサブBDDの終端ノードの判定及び前記二つのサブBDDの等価の判定後に、前記再帰部分を用いて冗長パスを除去する
付記１に記載の最小カットセット算出システム。
【００６５】
（付記３）  再帰部分と基本部分とからな再帰関数を用いて、BDDからなる故障の木の最小カットセットを算出する最小化手段を有し、
前記最小化手段は、前記減算手段によりサブBDDの冗長パスが除去された後に、前記再帰部分の計算を行って前記サブBDDの最小化する
付記１又は付記２に記載の最小カットセット算出システム。
【００６６】
（付記４）  バイナリ・デシジョン・ダイアグラム（BDD）からなる故障の木の最小カットセットを算出する最小カットセット算出システムであって、
再帰部分と基本部分とからな再帰関数を用いて、BDDからなる故障の木の最小カットセットを算出する最小化手段を有し、
前記最小化手段は、前記BDDのサブBDDの冗長パスが除去された後に、前記再帰部分の計算を行う
最小カットセット算出システム。
【００６７】
（付記５）  バイナリ・デシジョン・ダイアグラム（BDD）からなる故障の木の最小カットセットを算出する最小カットセット算出方法であって、
再帰部分と基本部分とからなる再帰関数を用いて、入力されたBDDの二つのサブBDDのうちの一つのサブBDDから、他のサブBDDに含まれる冗長パスを除去する減算処理を有し、
前記減算処理は、前記基本部分に、前記二つのサブBDDが終端ノードではなく、等価である場合に、終端ノード０を出力する等価除去処理を含む
最小カットセット算出方法。
【００６８】
（付記６）  前記減算処理は、前記二つのサブBDDの終端ノードの判定及び前記二つのサブBDDの等価の判定後に、前記再帰部分を用いて冗長パスを除去する
付記５に記載の最小カットセット算出方法。
【００６９】
（付記７）  再帰部分と基本部分とからな再帰関数を用いて、BDDからなる故障の木の最小カットセットを算出する最小化処理を有し、
前記最小化処理は、前記減算処理によりサブBDDの冗長パスが除去された後に、前記再帰部分の計算を行って前記サブBDDの最小化する
付記５又は付記６に記載の最小カットセット算出方法。
【００７０】
（付記８）  バイナリ・デシジョン・ダイアグラム（BDD）からなる故障の木の最小カットセットを算出する最小カットセット算出方法であって、
再帰部分と基本部分とからな再帰関数を用いて、BDDからなる故障の木の最小カットセットを算出する最小化処理を有し、
前記最小化処理は、前記BDDのサブBDDの冗長パスが除去された後に、前記再帰部分の計算を行う
最小カットセット算出方法。
【００７１】
（付記１０）  バイナリ・デシジョン・ダイアグラム（BDD）からなる故障の木の最小カットセットを算出する最小カットセット算出プログラムであって、
前記最小カットセット算出プログラムは、コンピュータに、
再帰部分と基本部分とからなる再帰関数を用いて、入力されたBDDの二つのサブBDDのうちの一つのサブBDDから、他のサブBDDに含まれる冗長パスを除去する減算処理を実行させ、
前記減算処理は、前記基本部分に、前記二つのサブBDDが終端ノードではなく、等価である場合に、終端ノード０を出力する等価除去処理を含む
最小カットセット算出プログラム。
【００７２】
（付記１１）  バイナリ・デシジョン・ダイアグラム（BDD）からなる故障の木の最小カットセットを算出する最小カットセット算出方法プログラムであって、
前記最小カットセット算出プログラムは、コンピュータに、
再帰部分と基本部分とからな再帰関数を用いて、BDDからなる故障の木の最小カットセットを算出する最小化処理を実行させ、
前記最小化処理は、前記BDDのサブBDDの冗長パスが除去された後に、前記再帰部分の計算を行う
最小カットセット算出プログラム。
【００７３】
以上好ましい実施の形態及び実施例をあげて本発明を説明したが、本発明は必ずしも上記実施の形態及び実施例に限定されるものではなく、その技術的思想の範囲内において様々に変形し実施することが出来る。
【００７４】
本出願は、２０１１年１２月９日に出願された日本出願特願２０１１−２７０７２９号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【００７５】
１１０    最小化手段
１２０    減算手段
１２１    等価除去手段
【図１】
2013085025.tif 000006
【図２】
2013085025.tif 000007
【図３】
2013085025.tif 000008
【図４】
2013085025.tif 000009
【図５】
2013085025.tif 000010
【図６】
2013085025.tif 000011
【図７】
2013085025.tif 000012
【図８】
2013085025.tif 000013
【図９】
2013085025.tif 000014
【図１０】
2013085025.tif 000015
【図１１】
2013085025.tif 000016
【図１２】
2013085025.tif 000017
【国際調査報告】
2013085025.tif 000018
2013085025.tif 000019
2013085025.tif 000020