(57)【要約】  行列生成装置（１００）は、木構造生成部（１１０）、ルート処理部（１２０）、ノード処理部（１３０）を備える。木構造生成部（１１０）は、論理式Ｆを表現する二分木Ｔを生成する。ルート処理部（１２０）は、論理式Ｆの要素のうち、二分木Ｔのルートによって表現される要素の種類に応じた行列Ｍを生成する。ノード処理部（１３０）は、二分木Ｔのルート以外のノードを順次選択し、子ノードを持つノードによって表現される要素の種類に応じた操作を行列Ｍに対して行い、子ノードを持たないノードによって表現される要素である変数を行列Ｍの一行に対応付ける。ノード処理部（１３０）は、二分木Ｔのノードを選択し終えた後は行列Ｍ及び写像ρを出力する。写像ρは、行列Ｍの各行に対応付けた変数を示す情報である。
2016002020.tif 000002
【特許請求の範囲】
【請求項１】
論理式の入力を受けて、前記論理式を表現する木構造データを生成する木構造生成部と、
前記論理式の要素のうち、前記木構造生成部により生成された木構造データのルートによって表現される要素の種類を判定し、判定した種類に応じた行列を生成するルート処理部と、
前記ルート処理部により生成された行列をメモリに格納するとともに、前記木構造生成部により生成された木構造データの前記ルート以外のノードを順次選択し、子ノードを持つノードを選択した場合は、前記論理式の要素のうち、選択したノードによって表現される要素の種類に応じた操作を、前記メモリに格納した行列に対して行い、子ノードを持たないノードを選択した場合は、前記論理式の要素のうち、選択したノードによって表現される要素である変数を、前記メモリに格納した行列の一行に対応付け、当該木構造データのノードを選択し終えた後は、前記メモリに格納した行列及びその行列の各行に対応付けた変数を示す情報を出力するノード処理部と
を備えることを特徴とする行列生成装置。
【請求項２】
前記ルート処理部は、判定した種類が論理和演算子である場合は、全ての成分が１である二行一列の行列を、論理和演算子に応じた行列として生成することを特徴とする請求項１の行列生成装置。
【請求項３】
前記ノード処理部は、選択したノードによって表現される要素の種類が論理和演算子である場合は、新たな行を追加するとともに、次に変数を対応付ける行をＣＲ行目として、（ＣＲ＋１）行目の各成分をＣＲ行目の各成分と同じ値に設定する操作を、論理和演算子に応じた操作として行うことを特徴とする請求項２の行列生成装置。
【請求項４】
前記ルート処理部は、判定した種類が論理積演算子である場合は、一行目一列目及び二行目二列目の成分が１、一行目二列目及び二行目一列目の成分が０である二行二列の行列を、論理積演算子に応じた行列として生成することを特徴とする請求項１から３のいずれかの行列生成装置。
【請求項５】
前記ノード処理部は、選択したノードによって表現される要素の種類が論理積演算子である場合は、新たな行及び列を追加するとともに、次に変数を対応付ける行をＣＲ行目とし、ＣＲ行目の成分が１である列のうち、序数が最小の列をＣＬ列目として、ＣＲ行目ＣＬ列目及び（ＣＲ＋１）行目（ＣＬ＋１）列目の成分を１、ＣＲ行目（ＣＬ＋１）列目及び（ＣＲ＋１）行目ＣＬ列目の成分を０に設定する操作を、論理積演算子に応じた操作として行うことを特徴とする請求項４の行列生成装置。
【請求項６】
前記ルート処理部は、判定した種類が論理積演算子である場合は、一行目一列目及び二行目二列目の成分が０、一行目二列目及び二行目一列目の成分が１である二行二列の行列を、論理積演算子に応じた行列として生成することを特徴とする請求項１から３のいずれかの行列生成装置。
【請求項７】
前記ノード処理部は、選択したノードによって表現される要素の種類が論理積演算子である場合は、新たな行及び列を追加するとともに、次に変数を対応付ける行をＣＲ行目とし、ＣＲ行目の成分が１である列のうち、序数が最小の列をＣＬ列目として、ＣＲ行目ＣＬ列目及び（ＣＲ＋１）行目（ＣＬ＋１）列目の成分を０、ＣＲ行目（ＣＬ＋１）列目及び（ＣＲ＋１）行目ＣＬ列目の成分を１に設定する操作を、論理積演算子に応じた操作として行うことを特徴とする請求項６の行列生成装置。
【請求項８】
前記ノード処理部により出力される行列の行のうち、同じ列の成分を加算した場合に全ての列の加算結果が１になる行の組み合わせについては、各行に対応付けられた変数が真であれば、前記論理式が真となり、
前記ノード処理部により出力される行列の行のうち、同じ列の成分を加算した場合に少なくとも一列の加算結果が１にならない行の組み合わせについては、各行に対応付けられた変数が真であっても、前記論理式が偽となることを特徴とする請求項１から７のいずれかの行列生成装置。
【請求項９】
前記ノード処理部は、前記木構造データのノードごとの処理を再帰呼び出しにより実行することを特徴とする請求項１から８のいずれかの行列生成装置。
【請求項１０】
前記論理式は、秘密分散方式で分散された情報の組み合わせを定義する論理式であることを特徴とする請求項１から９のいずれかの行列生成装置。
【請求項１１】
コンピュータが、論理式の入力を受けて、前記論理式を表現する木構造データを生成し、
前記コンピュータが、前記論理式の要素のうち、前記木構造データのルートによって表現される要素の種類を判定し、判定した種類に応じた行列を生成し、
前記コンピュータが、生成した行列をメモリに格納するとともに、前記木構造データの前記ルート以外のノードを順次選択し、子ノードを持つノードを選択した場合は、前記論理式の要素のうち、選択したノードによって表現される要素の種類に応じた操作を、前記メモリに格納した行列に対して行い、子ノードを持たないノードを選択した場合は、前記論理式の要素のうち、選択したノードによって表現される要素である変数を、前記メモリに格納した行列の一行に対応付け、前記木構造データのノードを選択し終えた後は、前記メモリに格納した行列及びその行列の各行に対応付けた変数を示す情報を出力することを特徴とする行列生成方法。
【請求項１２】
コンピュータに、
論理式の入力を受けて、前記論理式を表現する木構造データを生成する木構造生成処理と、
前記論理式の要素のうち、前記木構造生成処理により生成された木構造データのルートによって表現される要素の種類を判定し、判定した種類に応じた行列を生成するルート処理と、
前記ルート処理により生成された行列をメモリに格納するとともに、前記木構造生成処理により生成された木構造データの前記ルート以外のノードを順次選択し、子ノードを持つノードを選択した場合は、前記論理式の要素のうち、選択したノードによって表現される要素の種類に応じた操作を、前記メモリに格納した行列に対して行い、子ノードを持たないノードを選択した場合は、前記論理式の要素のうち、選択したノードによって表現される要素である変数を、前記メモリに格納した行列の一行に対応付け、当該木構造データのノードを選択し終えた後は、前記メモリに格納した行列及びその行列の各行に対応付けた変数を示す情報を出力するノード処理と
を実行させることを特徴とする行列生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、行列生成装置及び行列生成方法及び行列生成プログラムに関するものである。本発明は、例えば、暗号化及び復号に用いられる秘密分散行列を生成する装置及び方法及びプログラムに関するものである。
【背景技術】
【０００２】
秘密分散方式では、秘密情報がいくつかの分散情報に分けられる。秘密情報を復元するには、特定の組み合わせの分散情報を集めなければならない。どのような組み合わせの分散情報を集めればよいかは、論理和や論理積等を用いた論理式で定義することができる。秘密分散行列は、その論理式を行列形式に変換したものである。秘密分散行列の各行には、論理式に含まれる要素が割り当てられている。秘密分散行列は、論理式を満たす要素の行の和又は積が所望の値になるように設計される。論理式を満たさない要素の行をどのように組み合わせても所望の値は得られない。【０００３】
例えば、論理式Ｆが変数Ｐと変数Ｑとの論理積であり、秘密分散行列Ｍの一行目に変数Ｐ、二行目に変数Ｑが割り当てられているとする。この場合、変数Ｐと変数Ｑとの両方が真であれば、論理式Ｆが真になる。即ち、変数Ｐと変数Ｑとの組み合わせが論理式Ｆを満たす。変数Ｐ及び変数Ｑは、いずれも単独では論理式Ｆを満たさない。よって、秘密分散行列Ｍは、一行目及び二行目がいずれも所望の値ではなく、一行目と二行目との和又は積が所望の値になるように設計される。【０００４】
秘密分散行列は、関数型暗号に用いられる（例えば、特許文献１参照）。【０００５】
従来、秘密分散行列を生成するための方法がいくつか提案されている（例えば、非特許文献１及び２参照）。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】国際公開第２０１１／１３５８９５号
【非特許文献】
【０００７】
【非特許文献１】Ａ．  Ｌｅｗｋｏ，  Ｂ．  Ｗａｔｅｒｓ，  “Ｄｅｃｅｎｔｒａｌｉｚｉｎｇ  Ａｔｔｒｉｂｕｔｅ−Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ”，  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  ＥＵＲＯＣＲＹＰＴ  ２０１１，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  Ｖｏｌｕｍｅ  ６６３２，  ２０１１，  ｐｐ  ５６８−５８８
【非特許文献２】Ｚ．  Ｌｉｕ，  Ｚ．  Ｃａｏ，  “Ｏｎ  Ｅｆｆｉｃｉｅｎｔｌｙ  Ｔｒａｎｓｆｅｒｒｉｎｇ  ｔｈｅ  Ｌｉｎｅａｒ  Ｓｅｃｒｅｔ−Ｓｈａｒｉｎｇ  Ｓｃｈｅｍｅ  Ｍａｔｒｉｘ  ｉｎ  Ｃｉｐｈｅｒｔｅｘｔ−Ｐｏｌｉｃｙ  Ａｔｔｒｉｂｕｔｅ−Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ”，  ＩＡＣＲ  Ｃｒｙｐｔｏｌｏｇｙ  ｅＰｒｉｎｔ  Ａｒｃｈｉｖｅ，  ３７４，  ２０１０
【発明の概要】
【発明が解決しようとする課題】
【０００８】
非特許文献１に記載されている方法では、行列の成分として１と−１と０という３つの値を用いなければならない。非特許文献２に記載されている方法でも、多くの値を用いている。従来の方法では、秘密分散行列を効率的に生成することができない。【０００９】
本発明は、例えば、論理式から行列を効率的に生成することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の一の態様に係る行列生成装置は、
論理式の入力を受けて、前記論理式を表現する木構造データを生成する木構造生成部と、
前記論理式の要素のうち、前記木構造生成部により生成された木構造データのルートによって表現される要素の種類を判定し、判定した種類に応じた行列を生成するルート処理部と、
前記ルート処理部により生成された行列をメモリに格納するとともに、前記木構造生成部により生成された木構造データの前記ルート以外のノードを順次選択し、子ノードを持つノードを選択した場合は、前記論理式の要素のうち、選択したノードによって表現される要素の種類に応じた操作を、前記メモリに格納した行列に対して行い、子ノードを持たないノードを選択した場合は、前記論理式の要素のうち、選択したノードによって表現される要素である変数を、前記メモリに格納した行列の一行に対応付け、当該木構造データのノードを選択し終えた後は、前記メモリに格納した行列及びその行列の各行に対応付けた変数を示す情報を出力するノード処理部とを備える。
【発明の効果】
【００１１】
本発明では、最初に、木構造データのルートによって表現される要素の種類に応じた行列が生成される。その後、木構造データの各ノードによって表現される要素の種類に応じた操作が行列に対して行われる。変数を表現するノードについては、その変数が行列の一行に対応付けられる。最終的には、各行に変数が対応付けられた行列が得られる。このように、本発明によれば、論理式を表現する木構造データを辿って行列を効率的に生成することができる。
【図面の簡単な説明】
【００１２】
【図１】実施の形態１で最終的に生成される行列の一例を示す図。
【図２】実施の形態１に係る行列生成装置の構成を示すブロック図。
【図３】実施の形態１に係る行列生成装置の木構造生成部の構成を示すブロック図。
【図４】実施の形態１で生成される二分木の一例を示す図。
【図５】図４の二分木の再帰構造を示す図。
【図６】実施の形態１に係る行列生成装置のルート処理部の構成を示すブロック図。
【図７】実施の形態１に係る行列生成装置のノード処理部の構成を示すブロック図。
【図８】実施の形態１に係る行列生成装置のルート処理部の動作を示すフローチャート。
【図９】実施の形態１に係る行列生成装置のノード処理部の動作を示すフローチャート。
【図１０】実施の形態１で行列を生成する例を示す図。
【図１１】本発明の実施の形態に係る行列生成装置のハードウェア構成の一例を示す図。
【発明を実施するための形態】
【００１３】
以下、本発明の実施の形態について、図を用いて説明する。
【００１４】
実施の形態の説明では、以下の記法を用いる。
【００１５】
論理式Ｆの変数Ｐの内容が、ある種類Ａの値がａであるという事象の場合、変数Ｐを次式で表す。
Ａ＝ａ
【００１６】
一例として、種類Ａが「性別」であれば、値ａは「男性」又は「女性」である。
【００１７】
論理式Ｆの変数Ｐの内容が、ある種類Ａの値がａでないという事象の場合、変数Ｐを次式で表す。
Ａ！＝ａ
【００１８】
行列Ｍの行は、上から下に向かって昇順で数えられる（即ち、序数が割り当てられる）。例えば、最も上の行が一行目である。一行目のすぐ下の行が二行目である。
【００１９】
行列Ｍの列は、左から右に向かって昇順で数えられる（即ち、序数が割り当てられる）。例えば、最も左の列が一列目である。一列目のすぐ右の列が二列目である。
【００２０】
行列Ｍの行番号（即ち、序数）と論理式Ｆの変数との間には、写像が成り立つ。行番号ＲＯＷと変数Ｐとの間に写像ρが成り立つことを次式のように記述する。
ρ（ＲＯＷ）＝Ｐ
【００２１】
ρ（１）＝ｐ１、ρ（２）＝ｐ２となる写像ρが定義されていることを以下のように記述する。
ρ：｛（１，ｐ１），（２，ｐ２）｝
【００２２】
実施の形態１．
図１は、本実施の形態で最終的に生成される行列Ｍの一例を示す図である。
【００２３】
図１において、行列Ｍは、Ｌ行×ｒ列の秘密分散行列である。写像ρは、行列Ｍの各行と変数の集合｛ｐ１，・・・，ｐｎ｝に含まれる一つの変数とを対応付ける。即ち、行列Ｍの全ての行が写像ρによって一つの変数と対応付けられる。
【００２４】
図１の例では、Ｌ＝４、ｒ＝３である。即ち、行列Ｍは、四行三列の行列である。また、ｎ＝４である。変数ｐ１〜ｐ４は、それぞれＡ！＝１０、Ｂ＝２０、Ｃ！＝３０、Ｄ＝４０である。即ち、変数の集合は、｛Ａ！＝１０，Ｂ＝２０，Ｃ！＝３０，Ｄ＝４０｝である。
【００２５】
写像ρは、以下のように定義できる。
ρ：｛（１，（Ａ！＝１０）），（２，（Ｂ＝２０）），（３，（Ｃ！＝３０）），（４，（Ｄ＝４０））｝
【００２６】
本実施の形態では、行列Ｍと写像ρとが最終的な出力となる。この出力は、例えば、関数型暗号に用いられる。
【００２７】
なお、本実施の形態において、行列Ｍは、秘密分散行列以外の行列であってもよい。行数Ｌ、列数ｒ、変数の数ｎは、適宜変更することができる。各変数の内容も、適宜変更することができる。
【００２８】
図２は、本実施の形態に係る行列生成装置１００の構成を示すブロック図である。
【００２９】
図２において、行列生成装置１００は、木構造生成部１１０、ルート処理部１２０、ノード処理部１３０を備える。
【００３０】
木構造生成部１１０は、論理式Ｆの入力を受けて、論理式Ｆを表現する二分木Ｔを生成する。
【００３１】
論理式Ｆは、論理積（ａｎｄ）、論理和（ｏｒ）、否定（ｎｏｔ）といった演算子と、変数とを組み合わせて作成される。演算子及び変数は、それぞれ論理式Ｆの要素である。論理式Ｆは、例えば、秘密分散方式で分散された情報の組み合わせを定義する論理式である。
【００３２】
二分木Ｔは、木構造データの一例である。二分木Ｔは、論理式Ｆの要素をノードとして持つ。各ノードには、ノード番号が割り当てられる。本実施の形態では、ルートのノード番号が１となり、左側の子ノードを優先して各ノードにノード番号が順次割り当てられる。例えば、ルートが左側に子ノードを持っていれば、その子ノードのノード番号は２となる。ノード番号が２のノードが左側に子ノード（即ち、ルートの孫ノード）を持っていれば、その子ノードのノード番号は３となる。ノード番号が２のノードが子ノードを持っておらず、ルートが右側に子ノードを持っていれば、その子ノードのノード番号が３となる。なお、ノード番号の割り当て方は、適宜変更することができる。
【００３３】
木構造生成部１１０は、生成した二分木Ｔ及びその二分木Ｔのノード数Ｎを、ルート処理部１２０及びノード処理部１３０に出力する。
【００３４】
ルート処理部１２０は、木構造生成部１１０により生成された二分木Ｔ及びその二分木Ｔのノード数Ｎの入力を受けて、論理式Ｆの要素のうち、二分木Ｔのルートによって表現される要素の種類を判定する。ルート処理部１２０は、判定した種類に応じた行列Ｍを生成する。
【００３５】
例えば、ルートによって表現される要素の種類が論理積演算子であれば、ルート処理部１２０は、論理積処理を実行する。論理積処理では、論理積演算子に応じた行列Ｍが生成される。また、ルートのノード番号の次のノード番号Ｉが計算される。
【００３６】
ルートによって表現される要素の種類が論理和演算子であれば、ルート処理部１２０は、論理和処理を実行する。論理和処理では、論理和演算子に応じた行列Ｍが生成される。また、ルートのノード番号の次のノード番号Ｉが計算される。
【００３７】
ルートによって表現される要素の種類が変数であれば（即ち、ノード数Ｎが１の場合）、ルート処理部１２０は、変数処理を実行する。変数処理では、変数に応じた行列Ｍが生成される。また、ルートのノード番号の次のノード番号Ｉが計算される。さらに、写像ρによって変数が行列Ｍの一行に対応付けられる。
【００３８】
ルート処理部１２０は、生成した行列Ｍをノード処理部１３０に出力する。ルート処理部１２０は、計算したノード番号Ｉもノード処理部１３０に出力する。ルート処理部１２０は、写像ρを生成していれば、写像ρもノード処理部１３０に出力する。
【００３９】
ノード処理部１３０は、木構造生成部１１０により生成された二分木Ｔ及びその二分木Ｔのノード数Ｎと、ルート処理部１２０により生成された行列Ｍ及び写像ρ（もしあれば）と、ノード番号Ｉとの入力を受けて、二分木Ｔ、ノード数Ｎ、行列Ｍ、ノード番号Ｉ、写像ρをメモリ（図示していない）に格納する。
【００４０】
ノード処理部１３０は、二分木Ｔのルート以外のノードを順次選択する。具体的には、ノード処理部１３０は、ノード番号Ｉに対応するノードを選択する。ノード番号Ｉは、ノード数Ｎを超えるまで１ずつインクリメントされる。
【００４１】
ノード処理部１３０は、子ノードを持つノードを選択した場合は、論理式Ｆの要素のうち、選択したノードによって表現される要素の種類に応じた操作を、メモリに格納した行列Ｍに対して行う。
【００４２】
例えば、選択したノードによって表現される要素の種類が論理積演算子であれば、ノード処理部１３０は、論理積処理を実行する。論理積処理では、論理積演算子に応じた操作が行列Ｍに対して行われる。
【００４３】
選択したノードによって表現される要素の種類が論理和演算子であれば、ノード処理部１３０は、論理和処理を実行する。論理和処理では、論理和演算子に応じた操作が行列Ｍに対して行われる。
【００４４】
ノード処理部１３０は、子ノードを持たないノード（即ち、リーフ）を選択した場合は、論理式Ｆの要素のうち、選択したノードによって表現される要素である変数を、メモリに格納した行列Ｍの一行に対応付ける。
【００４５】
即ち、選択したノードによって表現される要素の種類が変数であれば、ノード処理部１３０は、変数処理を実行する。変数処理では、写像ρによって変数が行列Ｍの一行に対応付けられる。
【００４６】
ノード処理部１３０は、二分木Ｔのノードを選択し終えた後は、メモリに格納した行列Ｍ及び写像ρを出力する。写像ρは、行列Ｍの各行に対応付けた変数を示す情報である。
【００４７】
以下では、木構造生成部１１０の詳細について説明する。
【００４８】
図３は、木構造生成部１１０の構成を示すブロック図である。図４は、本実施の形態で生成される二分木Ｔの一例を示す図である。
【００４９】
図３において、木構造生成部１１０は、論理式入力部１１１、二分木生成部１１２、二分木出力部１１３を備える。
【００５０】
以下では、図４の例を用いて、木構造生成部１１０の各部の動作を説明する。
【００５１】
論理式入力部１１１は、論理積（ａｎｄ）、論理和（ｏｒ）、否定（ｎｏｔ）が組み合わされた以下の論理式Ｆの入力を受ける。
Ａ！＝１０  ａｎｄ  （（Ｂ＝２０  ａｎｄ  Ｃ！＝３０）  ｏｒ  Ｄ＝４０）
【００５２】
この論理式Ｆは、Ａが１０ではなく、Ｂが２０であり、かつ、Ｃが３０でない場合、若しくは、Ａが１０ではなく、かつ、Ｄが４０である場合に成り立つ。
【００５３】
二分木生成部１１２は、論理式入力部１１１によって得られた論理式Ｆを二分木Ｔに変換する。
【００５４】
論理式Ｆにおける演算の優先順位は、括弧内の論理式、論理積（ａｎｄ）、論理和（ｏｒ）の順である。よって、論理式Ｆの演算順は、括弧内の論理積（ａｎｄ）、括弧内の論理和（ｏｒ）、括弧外の論理積（ａｎｄ）の順となる。二分木生成部１１２は、論理式Ｆを二分木Ｔに変換する際に、論理式Ｆの演算順の逆順に、論理式Ｆの要素をルートから配置していく。具体的には、まず、二分木生成部１１２は、最後に演算される演算子Ｘ（図４の例では、括弧外の論理積）をルートに配置する。二分木生成部１１２は、演算子Ｘの左側の子ノードに、演算子Ｘの左側の論理式で最後に演算される演算子Ｙ１若しくは変数Ｙ２（図４の例では、Ａ！＝１０）を配置する。二分木生成部１１２は、演算子Ｘの右側の子ノードにも同様に、演算子Ｘの右側の論理式で最後に演算される演算子Ｚ１（図４の例では、括弧内の論理和）若しくは変数Ｚ２を配置する。次に、二分木生成部１１２は、演算子Ｘの左側の子ノードに着目する。演算子Ｘの左側の子ノードが演算子Ｙ１であれば、二分木生成部１１２は、演算子Ｙ１の左側の子ノードに、演算子Ｙ１の左側の論理式で最後に演算される演算子若しくは変数を配置する。二分木生成部１１２は、演算子Ｙ１の右側の子ノードにも同様に、演算子Ｙ１の右側の論理式で最後に演算される演算子若しくは変数を配置する。その後、二分木生成部１１２は、演算子Ｘの右側の子ノードについて同様の処理を行う。一方、演算子Ｘの左側の子ノードが変数Ｙ２であれば、二分木生成部１１２は、そのまま演算子Ｘの右側の子ノードについての処理を行う。二分木生成部１１２は、全てのリーフに変数を配置し終えるまで、左側の子ノードについての処理と右側の子ノードについての処理とを交互に繰り返す。
【００５５】
二分木Ｔが完成したならば、二分木生成部１１２は、各ノードにノード番号を付与する。ルートには１が付与される。他のノードには、左側優先で２以降の番号が付与される。二分木生成部１１２は、ノード番号の最大値をノード数Ｎとして記録する。
【００５６】
図４の例では、以下の７個のノードを持つ二分木Ｔが生成される。
・ノード番号１（ルート）：論理積（ａｎｄ）
・ノード番号２（リーフ）：Ａ！＝１０
・ノード番号３：論理和（ｏｒ）
・ノード番号４：論理積（ａｎｄ）
・ノード番号５（リーフ）：Ｂ＝２０
・ノード番号６（リーフ）：Ｃ！＝３０
・ノード番号７（リーフ）：Ｄ＝４０
【００５７】
二分木出力部１１３は、二分木生成部１１２により生成された二分木Ｔと、二分木生成部１１２により記録されたノード数Ｎとを出力する。
【００５８】
以下では、ルート処理部１２０及びノード処理部１３０の詳細について説明する。処理は図５に示すような再帰構造を用いて行われる。
【００５９】
図６は、ルート処理部１２０の構成を示すブロック図である。図７は、ノード処理部１３０の構成を示すブロック図である。図８は、ルート処理部１２０の動作を示すフローチャートである。図９は、ノード処理部１３０の動作を示すフローチャートである。
【００６０】
図６において、ルート処理部１２０は、ルート判定部１２１、論理積処理部１２２ａ、論理和処理部１２２ｂ、変数処理部１２２ｃ、処理結果出力部１２３を備える。
【００６１】
図７において、ノード処理部１３０は、ノード判定部１３１、論理積処理部１３２ａ、論理和処理部１３２ｂ、変数処理部１３２ｃ、処理数判定部１３３、処理結果出力部１３４を備える。
【００６２】
以下では、図８を参照しながら、ルート処理部１２０の各部の動作を説明する。
【００６３】
Ｓ２１において、ルート判定部１２１は、二分木Ｔ及びノード数Ｎの入力を受ける。
【００６４】
Ｓ２２において、ルート判定部１２１は、行番号から変数への写像ρを初期化する。
【００６５】
Ｓ２３において、ルート判定部１２１は、二分木Ｔのルートが論理積と論理和と変数とのいずれであるかを判定する。ルートが論理積であれば、フローはＳ２４ａに進む。ルートが論理和であれば、フローはＳ２４ｂに進む。ルートが変数であれば、フローはＳ２４ｃに進む。
【００６６】
Ｓ２４ａにおいて、論理積処理部１２２ａは、ルート判定部１２１から二分木Ｔの入力を受けて、以下の行列Ｍを生成する。フローはＳ２５ａに進む。
【数１】
2016002020.tif 000003
【００６７】
Ｓ２５ａにおいて、論理積処理部１２２ａは、二分木Ｔのルートのノード番号に１を加算してノード番号Ｉを得る。フローはＳ２６に進む。
【００６８】
Ｓ２４ｂにおいて、論理和処理部１２２ｂは、ルート判定部１２１から二分木Ｔの入力を受けて、以下の行列Ｍを生成する。フローはＳ２５ｂに進む。
【数２】
2016002020.tif 000004
【００６９】
Ｓ２５ｂにおいて、論理和処理部１２２ｂは、二分木Ｔのルートのノード番号に１を加算してノード番号Ｉを得る。フローはＳ２６に進む。
【００７０】
Ｓ２４ｃにおいて、変数処理部１２２ｃは、ルート判定部１２１から二分木Ｔと写像ρとの入力を受けて、以下の行列Ｍを生成する。フローはＳ２５ｃに進む。
（１）
【００７１】
Ｓ２５ｃにおいて、変数処理部１２２ｃは、二分木Ｔのルートのノード番号に１を加算してノード番号Ｉを得る。また、変数処理部１２２ｃは、以下の写像ρを定義する。
ρ（１）＝ｐ１
【００７２】
即ち、変数処理部１２２ｃは、以下のように写像ρを更新する。フローはＳ２６に進む。
ρ：｛（１，ｐ１）｝
【００７３】
Ｓ２６において、処理結果出力部１２３は、論理積処理部１２２ａと論理和処理部１２２ｂと変数処理部１２２ｃとのいずれかにより生成された行列Ｍを出力する。処理結果出力部１２３は、論理積処理部１２２ａと論理和処理部１２２ｂと変数処理部１２２ｃとのいずれかにより計算されたノード番号Ｉも出力する。処理結果出力部１２３は、さらに、初期状態の写像ρ、或いは、変数処理部１２２ｃにより更新された写像ρを出力する。
【００７４】
以下では、図９を参照しながら、ノード処理部１３０の各部の動作を説明する。
【００７５】
Ｓ３１において、ノード判定部１３１は、二分木Ｔ、ノード数Ｎ、行列Ｍ、ノード番号Ｉ、写像ρの入力を受ける。
【００７６】
Ｓ３２において、ノード判定部１３１は、処理行番号ＣＲを１に設定する。行列ＭのＣＲ行目は、次に変数が対応付けられる行である。
【００７７】
Ｓ３３において、処理数判定部１３３は、ノード番号Ｉがノード数Ｎより大きいかどうかを判定する。ノード番号Ｉがノード数Ｎより小さいか、ノード数Ｎと同じである（即ち、Ｉ≦Ｎ）場合、フローはＳ３４に進む。ノード番号Ｉがノード数Ｎより大きい（即ち、Ｉ＞Ｎ）場合、二分木Ｔにはこれ以上選択するノードがないため、フローはＳ３６に進む。
【００７８】
Ｓ３４において、ノード判定部１３１は、ノード番号Ｉに対応するノードを選択する。ノード判定部１３１は、選択したノードが論理積と論理和と変数とのいずれであるかを判定する。ノード（この場合、子ノードを持つノード）が論理積であれば、フローはＳ３５ａに進む。ノード（この場合、子ノードを持つノード）が論理和であれば、フローはＳ３５ｂに進む。ノード（この場合、リーフ）が変数であれば、フローはＳ３５ｃに進む。
【００７９】
Ｓ３５ａにおいて、論理積処理部１３２ａは、ノード判定部１３１から二分木Ｔ、行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρの入力を受けて、論理積処理を実行する。論理積処理では、行列Ｍ及びノード番号Ｉが更新される。論理積処理の詳細については、後述する。フローはＳ３３に戻る。
【００８０】
Ｓ３５ｂにおいて、論理和処理部１３２ｂは、ノード判定部１３１から二分木Ｔ、行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρの入力を受けて、論理和処理を実行する。論理和処理では、行列Ｍ及びノード番号Ｉが更新される。論理和処理の詳細については、後述する。フローはＳ３３に戻る。
【００８１】
Ｓ３５ｃにおいて、変数処理部１３２ｃは、ノード判定部１３１から二分木Ｔ、行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρの入力を受けて、変数処理を実行する。変数処理では、行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρが更新される。変数処理の詳細については、後述する。フローはＳ３３に戻る。
【００８２】
フローがＳ３３に戻り、再びＳ３４に進む場合、処理数判定部１３３は、論理積処理部１３２ａと論理和処理部１３２ｂと変数処理部１３２ｃとのいずれかにより更新された行列Ｍ及びノード番号Ｉをノード判定部１３１に渡す。処理数判定部１３３は、変数処理部１３２ｃにより処理行番号ＣＲ及び写像ρが更新されていれば、更新された処理行番号ＣＲ及び写像ρもノード判定部１３１に渡す。
【００８３】
Ｓ３６において、処理結果出力部１３４は、処理数判定部１３３から行列Ｍと写像ρとの入力を受けて、行列Ｍと写像ρとを出力する。
【００８４】
以下では、Ｓ３５ａで実行される論理積処理の詳細について説明する。
【００８５】
論理積処理部１３２ａは、入力として、二分木Ｔ、Ｌ’×ｒ’の行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρを受け取る。
【００８６】
論理積処理部１３２ａは、Ｌ’×ｒ’の行列Ｍにおいて、（Ｌ’＋１）行目として成分が全て０である行を追加する。行が追加されるため、行列Ｍは（Ｌ’＋１）×ｒ’の行列となる。
【００８７】
論理積処理部１３２ａは、（Ｌ’＋１）×ｒ’の行列Ｍにおいて、（ｒ’＋１）列目として成分が全て０である列を追加する。列が追加されるため、行列Ｍは（Ｌ’＋１）×（ｒ’＋１）の行列となる。
【００８８】
論理積処理部１３２ａは、（Ｌ’＋１）×（ｒ’＋１）の行列Ｍにおいて、ＣＲ行目の最も左に１が存在する列をＣＬ列目と定義する。
【００８９】
論理積処理部１３２ａは、ｉをｒ’からＣＬまでの値として、（Ｌ’＋１）×（ｒ’＋１）の行列Ｍにおいて、（ｉ＋１）列目をｉ列目で上書きする。即ち、論理積処理部１３２ａは、ｒ’列目を（ｒ’＋１）列目にコピーし、（ｒ’−１）列目をｒ’列目にコピーし、・・・、最後に、ＣＬ列目を（ＣＬ＋１）列目にコピーする。
【００９０】
論理積処理部１３２ａは、ｊをＬ’からＣＲまでの値として、（Ｌ’＋１）×（ｒ’＋１）の行列Ｍにおいて、（ｊ＋１）行目をｊ行目で上書きする。即ち、論理積処理部１３２ａは、Ｌ’行目を（Ｌ’＋１）行目にコピーし、（Ｌ’−１）行目をＬ’行目にコピーし、・・・、最後に、ＣＲ行目を（ＣＲ＋１）行目にコピーする。
【００９１】
論理積処理部１３２ａは、（Ｌ’＋１）×（ｒ’＋１）の行列Ｍにおいて、ＣＲ行目ＣＬ列目の成分を１に、ＣＲ行目（ＣＬ＋１）列目の成分を０に、（ＣＲ＋１）行目ＣＬ列目の成分を０に、（ＣＲ＋１）行目（ＣＬ＋１）列目の成分を１に書き換える。
【００９２】
論理積処理部１３２ａは、ノード番号Ｉに１を加算する。
【００９３】
論理積処理部１３２ａは、二分木Ｔ、（Ｌ’＋１）×（ｒ’＋１）の行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρを出力する。
【００９４】
以下では、Ｓ３５ｂで実行される論理和処理の詳細について説明する。
【００９５】
論理和処理部１３２ｂは、入力として、二分木Ｔ、Ｌ’×ｒ’の行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρを受け取る。
【００９６】
論理和処理部１３２ｂは、Ｌ’×ｒ’の行列Ｍにおいて、（Ｌ’＋１）行目として成分が全て０である行を追加する。行が追加されるため、行列Ｍは（Ｌ’＋１）×ｒ’の行列となる。
【００９７】
論理和処理部１３２ｂは、ｊをＬ’からＣＲまでの値として、（Ｌ’＋１）×ｒ’の行列Ｍにおいて、（ｊ＋１）行目をｊ行目で上書きする。即ち、論理積処理部１３２ａは、Ｌ’行目を（Ｌ’＋１）行目にコピーし、（Ｌ’−１）行目をＬ’行目にコピーし、・・・、最後に、ＣＲ行目を（ＣＲ＋１）行目にコピーする。
【００９８】
論理和処理部１３２ｂは、ノード番号Ｉに１を加算する。
【００９９】
論理和処理部１３２ｂは、二分木Ｔ、（Ｌ’＋１）×ｒ’の行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρを出力する。
【０１００】
以下では、Ｓ３５ｃで実行される変数処理の詳細について説明する。
【０１０１】
変数処理部１３２ｃは、入力として、二分木Ｔ、Ｌ’×ｒ’の行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρを受け取る。
【０１０２】
変数処理部１３２ｃは、処理行番号ＣＲとノード番号Ｉのリーフの変数ｐｋとの間に、以下の写像ρを定義する。
ρ（ＣＲ）＝ｐｋ
【０１０３】
即ち、変数処理部１３２ｃは、写像ρに（ＣＲ，ｐｋ）を追加する。
【０１０４】
変数処理部１３２ｃは、ノード番号Ｉに１を加算する。
【０１０５】
変数処理部１３２ｃは、処理行番号ＣＲに１を加算する。
【０１０６】
変数処理部１３２ｃは、二分木Ｔ、Ｌ’×ｒ’の行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρを出力する。
【０１０７】
本実施の形態では、ノード処理部１３０により出力される行列Ｍの行のうち、同じ列の成分を加算した場合に全ての列の加算結果が１になる行の組み合わせについては、各行に対応付けられた変数が真であれば、論理式Ｆが真となる。逆に、ノード処理部１３０により出力される行列Ｍの行のうち、同じ列の成分を加算した場合に少なくとも一列の加算結果が１にならない行の組み合わせについては、各行に対応付けられた変数が真であっても、論理式Ｆが偽となる。このような性質を持つ行列Ｍを生成するために、本実施の形態では、前述したルート処理及びノード処理が行われる。
【０１０８】
例えば、ルート処理部１２０は、論理式Ｆの要素のうち、二分木Ｔのルートによって表現される要素の種類が論理積演算子である場合は、Ｓ２４ａの処理を行う。即ち、ルート処理部１２０は、一行目一列目及び二行目二列目の成分が１、一行目二列目及び二行目一列目の成分が０である二行二列の行列を、論理積演算子に応じた行列Ｍとして生成する。
【０１０９】
例えば、ルート処理部１２０は、論理式Ｆの要素のうち、二分木Ｔのルートによって表現される要素の種類が論理和演算子である場合は、Ｓ２４ｂの処理を行う。即ち、ルート処理部１２０は、全ての成分が１である二行一列の行列を、論理和演算子に応じた行列Ｍとして生成する。
【０１１０】
例えば、ノード処理部１３０は、論理式Ｆの要素のうち、子ノードを持つノードによって表現される要素の種類が論理積演算子である場合は、Ｓ３５ａの処理を行う。即ち、ノード処理部１３０は、新たな行及び列を追加するとともに、次に変数を対応付ける行をＣＲ行目とし、ＣＲ行目の成分が１である列のうち、序数が最小の列をＣＬ列目として、ＣＲ行目ＣＬ列目及び（ＣＲ＋１）行目（ＣＬ＋１）列目の成分を１、ＣＲ行目（ＣＬ＋１）列目及び（ＣＲ＋１）行目ＣＬ列目の成分を０に設定する操作を、論理積演算子に応じた操作として行列Ｍに対して行う。
【０１１１】
Ｓ３５ａの処理では、実質的には、ＣＲ行目を２行に拡張して、（ＣＲ＋１）行目以降を１行ずつ下にずらしている。また、ＣＬ列目を２列に拡張して、（ＣＬ＋１）列目以降を１列ずつ右にずらしている。これにより、拡張前のＣＲ行目ＣＬ列目の成分を、Ｓ２４ａの処理で生成される行列と同じ二行二列の部分行列に変換しつつ、拡張（即ち、論理積演算子に応じた操作）の影響が他の成分に及ぶことを回避できる。このため、選択したノードによって表現される論理積演算子を適切に行列Ｍに反映することができる。
【０１１２】
例えば、ノード処理部１３０は、論理式Ｆの要素のうち、子ノードを持つノードによって表現される要素の種類が論理和演算子である場合は、Ｓ３５ｂの処理を行う。即ち、ノード処理部１３０は、新たな行を追加するとともに、次に変数を対応付ける行をＣＲ行目として、（ＣＲ＋１）行目の各成分をＣＲ行目の各成分と同じ値に設定する操作を、論理和演算子に応じた操作として行列Ｍに対して行う。
【０１１３】
Ｓ３５ｂの処理では、実質的には、ＣＲ行目を２行に拡張して、（ＣＲ＋１）行目以降を１行ずつ下にずらしている。これにより、拡張前のＣＲ行目で値が１の成分を、Ｓ２４ｂの処理で生成される行列と同じ二行一列の部分行列に変換しつつ、拡張（即ち、論理和演算子に応じた操作）の影響が他の成分に及ぶことを回避できる。このため、選択したノードによって表現される論理和演算子を適切に行列Ｍに反映することができる。
【０１１４】
このように、本実施の形態によれば、論理式Ｆを表現する二分木Ｔを辿って行列Ｍを効率的に生成することができる。
【０１１５】
本実施の形態では、ノード処理部１３０が、二分木Ｔのノードごとの処理を再帰呼び出しにより実行する。そのため、行列Ｍをより効率的に生成することができる。
【０１１６】
以上説明したように、本実施の形態に係る行列生成方法は、論理式Ｆの入力を受けるステップと、論理式Ｆと等価な木構造を生成するステップと、木構造のルートに対して処理を行うステップと、木構造のノードに対して、子ノードを持つかどうかを判定するステップと、ノードが子ノードを持つ場合は再帰呼び出しにより子ノードに対して処理を行うステップと、ノードが子ノードを持たない場合は変数を行に対応付け、親ノードへ戻るステップとを含むものである。
【０１１７】
この行列生成方法において、生成される行列Ｍの成分は０又は１である。論理式Ｆが成立する行からなる部分行列の行ベクトルを線形結合すると、全て１からなるベクトルを生成することができる。論理式Ｆが成立しない行からなる部分行列の行ベクトルを線形結合しても全て１からなるベクトルを生成することはできない。
【０１１８】
また、この行列生成方法において、ノードが論理積（ａｎｄ）の場合は、行列Ｍの中に論理積（ａｎｄ）を表す部分行列が生成される。ノードが論理和（ｏｒ）の場合は、行列Ｍの中に処理行と同じ行が追加される。
【０１１９】
この行列生成方法を用いることで、行列Ｍのサイズを小さくすることができる。また、論理式Ｆから行列Ｍへの変換処理を効率化することができる。さらに、実装時のプログラムサイズを小さくすることができる。
【０１２０】
なお、本実施の形態は、必要に応じて種々の変更が可能である。
【０１２１】
例えば、本実施の形態では、Ｓ２４ａ及びＳ３５ａの論理積処理によって、以下のような行列（又は部分行列）が生成される。
【数３】
2016002020.tif 000005
【０１２２】
しかし、Ｓ２４ａ及びＳ３５ａの論理積処理によって、以下のような行列（又は部分行列）が生成されてもよい。
【数４】
2016002020.tif 000006
【０１２３】
また、本実施の形態では、行列Ｍが０及び１で構成されるが、行列Ｍが０及び１以外の整数値、若しくは、実数値で構成されてもよい。
【０１２４】
図１０は、本実施の形態で行列Ｍを生成する例を示す図である。
【０１２５】
図１０の例では、図４の例を適用している。
【０１２６】
以下では、図８を参照しながら、図１０の例におけるルート処理部１２０の各部の動作を説明する。
【０１２７】
Ｓ２１において、ルート判定部１２１は、以下の論理式Ｆを表現する二分木Ｔ及びノード数Ｎの入力を受ける。
Ａ！＝１０  ａｎｄ  （（Ｂ＝２０  ａｎｄ  Ｃ！＝３０）  ｏｒ  Ｄ＝４０）
【０１２８】
ノードを持つノード数Ｎは７である。二分木Ｔは、以下の７個のノードを持つ。
・ノード番号１（ルート）：論理積（ａｎｄ）
・ノード番号２（リーフ）：Ａ！＝１０
・ノード番号３：論理和（ｏｒ）
・ノード番号４：論理積（ａｎｄ）
・ノード番号５（リーフ）：Ｂ＝２０
・ノード番号６（リーフ）：Ｃ！＝３０
・ノード番号７（リーフ）：Ｄ＝４０
【０１２９】
Ｓ２２において、ルート判定部１２１は、写像ρを初期化する。
【０１３０】
Ｓ２３において、ルート判定部１２１は、二分木Ｔのルートが論理積であると判定する。フローはＳ２４ａに進む。
【０１３１】
Ｓ２４ａにおいて、論理積処理部１２２ａは、以下の行列Ｍを生成する。フローはＳ２５ａに進む。
【数５】
2016002020.tif 000007
【０１３２】
Ｓ２５ａにおいて、論理積処理部１２２ａは、ノード番号を１から２に更新する。フローはＳ２６に進む。
【０１３３】
Ｓ２６において、処理結果出力部１２３は、行列Ｍ、ノード番号Ｉ、写像ρを出力する。
【０１３４】
以下では、図９を参照しながら、図１０の例におけるノード処理部１３０の各部の動作を説明する。
【０１３５】
Ｓ３１において、ノード判定部１３１は、二分木Ｔ、ノード数Ｎ、行列Ｍ、ノード番号Ｉ、写像ρの入力を受ける。ノード数Ｎは７である。ノード番号Ｉは２である。
【０１３６】
Ｓ３２において、ノード判定部１３１は、処理行番号ＣＲを１に設定する。
【０１３７】
Ｓ３３において、処理数判定部１３３は、ノード番号Ｉがノード数Ｎより小さい（即ち、Ｉ＝２、Ｎ＝７であるため、Ｉ≦Ｎ）と判定する。フローはＳ３４に進む。
【０１３８】
Ｓ３４において、ノード判定部１３１は、ノード番号Ｉに対応するノードを選択する。ノード判定部１３１は、選択したノードが変数（Ａ！＝１０）であると判定する。フローはＳ３５ｃに進む。
【０１３９】
Ｓ３５ｃにおいて、変数処理部１３２ｃは、入力として、二分木Ｔ、２×２の行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρを受け取る。処理行番号ＣＲは１である。ノード番号Ｉは２である。
【０１４０】
変数処理部１３２ｃは、処理行番号ＣＲとノード番号Ｉのリーフの変数（Ａ！＝１０）との間に、以下の写像ρを定義する。
ρ（１）＝（Ａ！＝１０）
【０１４１】
即ち、変数処理部１３２ｃは、写像ρに（１，（Ａ！＝１０））を追加する。
【０１４２】
変数処理部１３２ｃは、ノード番号Ｉを２から３に更新する。
【０１４３】
変数処理部１３２ｃは、処理行番号ＣＲを１から２に更新する。
【０１４４】
変数処理部１３２ｃは、二分木Ｔ、２×２の行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρを出力する。フローはＳ３３に戻る。
【０１４５】
Ｓ３３において、処理数判定部１３３は、ノード番号Ｉがノード数Ｎより小さい（即ち、Ｉ＝３、Ｎ＝７であるため、Ｉ≦Ｎ）と判定する。フローはＳ３４に進む。
【０１４６】
Ｓ３４において、ノード判定部１３１は、ノード番号Ｉに対応するノードを選択する。ノード判定部１３１は、選択したノードが論理和であると判定する。フローはＳ３５ｂに進む。
【０１４７】
Ｓ３５ｂにおいて、論理和処理部１３２ｂは、入力として、二分木Ｔ、２×２の行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρを受け取る。処理行番号ＣＲは２である。ノード番号Ｉは３である。写像ρは｛（１，（Ａ！＝１０））｝である。
【０１４８】
論理和処理部１３２ｂは、２×２の行列Ｍにおいて、三行目として成分が全て０である行を追加する。行が追加されるため、行列Ｍは以下の３×２の行列となる。
【数６】
2016002020.tif 000008
【０１４９】
論理和処理部１３２ｂは、３×２の行列Ｍにおいて、二行目を三行目にコピーする。その結果、行列Ｍは以下の行列となる。
【数７】
2016002020.tif 000009
【０１５０】
論理和処理部１３２ｂは、ノード番号Ｉを３から４に更新する。
【０１５１】
論理和処理部１３２ｂは、二分木Ｔ、３×２の行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρを出力する。フローはＳ３３に戻る。
【０１５２】
Ｓ３３において、処理数判定部１３３は、ノード番号Ｉがノード数Ｎより小さい（即ち、Ｉ＝４、Ｎ＝７であるため、Ｉ≦Ｎ）と判定する。フローはＳ３４に進む。
【０１５３】
Ｓ３６において、処理結果出力部１３４は、処理数判定部１３３から行列Ｍと写像ρとの入力を受けて、行列Ｍと写像ρとを出力する。
【０１５４】
Ｓ３４において、ノード判定部１３１は、ノード番号Ｉに対応するノードを選択する。ノード判定部１３１は、選択したノードが論理積であると判定する。フローはＳ３５ａに進む。
【０１５５】
Ｓ３５ａにおいて、論理積処理部１３２ａは、入力として、二分木Ｔ、３×２の行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρを受け取る。処理行番号ＣＲは２である。ノード番号Ｉは４である。写像ρは｛（１，（Ａ！＝１０））｝である。
【０１５６】
論理積処理部１３２ａは、３×２の行列Ｍにおいて、四行目として成分が全て０である行を追加する。行が追加されるため、行列Ｍは以下の４×２の行列となる。
【数８】
2016002020.tif 000010
【０１５７】
論理積処理部１３２ａは、４×２の行列Ｍにおいて、三列目として成分が全て０である列を追加する。列が追加されるため、行列Ｍは以下の４×３の行列となる。
【数９】
2016002020.tif 000011
【０１５８】
論理積処理部１３２ａは、４×３の行列Ｍにおいて、ＣＲ行目の最も左に１が存在する列をＣＬ列目と定義する。即ち、論理積処理部１３２ａは、ＣＬを２に設定する。
【０１５９】
論理積処理部１３２ａは、４×３の行列Ｍにおいて、二列目を三列目にコピーする。その結果、行列Ｍは以下の行列となる。
【数１０】
2016002020.tif 000012
【０１６０】
論理積処理部１３２ａは、４×３の行列Ｍにおいて、三行目を四行目にコピーし、二行目を三行目にコピーする。その結果、行列Ｍは以下の行列となる。
【数１１】
2016002020.tif 000013
【０１６１】
論理積処理部１３２ａは、４×３の行列Ｍにおいて、ＣＲ行目ＣＬ列目の成分を１に、ＣＲ行目（ＣＬ＋１）列目の成分を０に、（ＣＲ＋１）行目ＣＬ列目の成分を０に、（ＣＲ＋１）行目（ＣＬ＋１）列目の成分を１に書き換える。即ち、論理積処理部１３２ａは、二行目二列目及び三行目三列目の成分を１に、二行目三列目及び三行目二列目の成分を０に設定する。その結果、行列Ｍは以下の行列となる。
【数１２】
2016002020.tif 000014
【０１６２】
論理積処理部１３２ａは、ノード番号Ｉを４から５に更新する。
【０１６３】
論理積処理部１３２ａは、二分木Ｔ、４×３の行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρを出力する。フローはＳ３３に戻る。
【０１６４】
Ｓ３３において、処理数判定部１３３は、ノード番号Ｉがノード数Ｎより小さい（即ち、Ｉ＝５、Ｎ＝７であるため、Ｉ≦Ｎ）と判定する。フローはＳ３４に進む。
【０１６５】
Ｓ３４において、ノード判定部１３１は、ノード番号Ｉに対応するノードを選択する。ノード判定部１３１は、選択したノードが変数（Ｂ＝２０）であると判定する。フローはＳ３５ｃに進む。
【０１６６】
Ｓ３５ｃにおいて、変数処理部１３２ｃは、入力として、二分木Ｔ、４×３の行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρを受け取る。処理行番号ＣＲは２である。ノード番号Ｉは５である。写像ρは｛（１，（Ａ！＝１０））｝である。
【０１６７】
変数処理部１３２ｃは、処理行番号ＣＲとノード番号Ｉのリーフの変数（Ｂ＝２０）との間に、以下の写像ρを定義する。
ρ（２）＝（Ｂ＝２０）
【０１６８】
即ち、変数処理部１３２ｃは、写像ρに（２，（Ｂ＝２０））を追加する。
【０１６９】
変数処理部１３２ｃは、ノード番号Ｉを５から６に更新する。
【０１７０】
変数処理部１３２ｃは、処理行番号ＣＲを２から３に更新する。
【０１７１】
変数処理部１３２ｃは、二分木Ｔ、４×３の行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρを出力する。フローはＳ３３に戻る。
【０１７２】
Ｓ３３において、処理数判定部１３３は、ノード番号Ｉがノード数Ｎより小さい（即ち、Ｉ＝６、Ｎ＝７であるため、Ｉ≦Ｎ）と判定する。フローはＳ３４に進む。
【０１７３】
Ｓ３４において、ノード判定部１３１は、ノード番号Ｉに対応するノードを選択する。ノード判定部１３１は、選択したノードが変数（Ｃ！＝３０）であると判定する。フローはＳ３５ｃに進む。
【０１７４】
Ｓ３５ｃにおいて、変数処理部１３２ｃは、入力として、二分木Ｔ、４×３の行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρを受け取る。処理行番号ＣＲは３である。ノード番号Ｉは６である。写像ρは｛（１，（Ａ！＝１０）），（１，（Ｂ＝２０））｝である。
【０１７５】
変数処理部１３２ｃは、処理行番号ＣＲとノード番号Ｉのリーフの変数（Ｃ！＝３０）との間に、以下の写像ρを定義する。
ρ（３）＝（Ｃ！＝３０）
【０１７６】
即ち、変数処理部１３２ｃは、写像ρに（３，（Ｃ！＝３０））を追加する。
【０１７７】
変数処理部１３２ｃは、ノード番号Ｉを６から７に更新する。
【０１７８】
変数処理部１３２ｃは、処理行番号ＣＲを３から４に更新する。
【０１７９】
変数処理部１３２ｃは、二分木Ｔ、４×３の行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρを出力する。フローはＳ３３に戻る。
【０１８０】
Ｓ３３において、処理数判定部１３３は、ノード番号Ｉがノード数Ｎと同じ（即ち、Ｉ＝７、Ｎ＝７であるため、Ｉ≦Ｎ）と判定する。フローはＳ３４に進む。
【０１８１】
Ｓ３４において、ノード判定部１３１は、ノード番号Ｉに対応するノードを選択する。ノード判定部１３１は、選択したノードが変数（Ｄ＝４０）であると判定する。フローはＳ３５ｃに進む。
【０１８２】
Ｓ３５ｃにおいて、変数処理部１３２ｃは、入力として、二分木Ｔ、４×３の行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρを受け取る。処理行番号ＣＲは３である。ノード番号Ｉは７である。写像ρは｛（１，（Ａ！＝１０）），（１，（Ｂ＝２０）），（３，（Ｃ！＝３０））｝である。
【０１８３】
変数処理部１３２ｃは、処理行番号ＣＲとノード番号Ｉのリーフの変数（Ｄ＝４０）との間に、以下の写像ρを定義する。
ρ（４）＝（Ｄ＝４０）
【０１８４】
即ち、変数処理部１３２ｃは、写像ρに（４，（Ｄ＝４０））を追加する。
【０１８５】
変数処理部１３２ｃは、ノード番号Ｉを７から８に更新する。
【０１８６】
変数処理部１３２ｃは、処理行番号ＣＲを４から５に更新する。
【０１８７】
変数処理部１３２ｃは、二分木Ｔ、４×３の行列Ｍ、処理行番号ＣＲ、ノード番号Ｉ、写像ρを出力する。フローはＳ３３に戻る。
【０１８８】
Ｓ３３において、処理数判定部１３３は、ノード番号Ｉがノード数Ｎより大きい（即ち、Ｉ＝８、Ｎ＝７であるため、Ｉ＞Ｎ）と判定する。フローはＳ３６に進む。
【０１８９】
Ｓ３６において、処理結果出力部１３４は、４×３の行列Ｍと写像ρとを出力する。写像ρは｛（１，（Ａ！＝１０）），（１，（Ｂ＝２０）），（３，（Ｃ！＝３０）），（４，（Ｄ＝４０））｝である。
【０１９０】
図１１は、本発明の実施の形態に係る行列生成装置１００のハードウェア構成の一例を示す図である。
【０１９１】
図１１において、行列生成装置１００は、コンピュータであり、出力装置９１０、入力装置９２０、記憶装置９３０、処理装置９４０といったハードウェアを備える。ハードウェアは、行列生成装置１００の各部（本発明の実施の形態の説明において「部」として説明するもの）によって利用される。
【０１９２】
出力装置９１０は、例えば、ＬＣＤ（Ｌｉｑｕｉｄ・Ｃｒｙｓｔａｌ・Ｄｉｓｐｌａｙ）等の表示装置、プリンタ、通信モジュール（通信回路等）である。出力装置９１０は、本発明の実施の形態の説明において「部」として説明するものによってデータ、情報、信号の出力（送信）のために利用される。
【０１９３】
入力装置９２０は、例えば、キーボード、マウス、タッチパネル、通信モジュール（通信回路等）である。入力装置９２０は、本発明の実施の形態の説明において「部」として説明するものによってデータ、情報、信号の入力（受信）のために利用される。
【０１９４】
記憶装置９３０は、例えば、ＲＯＭ（Ｒｅａｄ・Ｏｎｌｙ・Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ・Ａｃｃｅｓｓ・Ｍｅｍｏｒｙ）、ＨＤＤ（Ｈａｒｄ・Ｄｉｓｋ・Ｄｒｉｖｅ）、ＳＳＤ（Ｓｏｌｉｄ・Ｓｔａｔｅ・Ｄｒｉｖｅ）である。記憶装置９３０には、プログラム９３１、ファイル９３２が記憶される。プログラム９３１には、本発明の実施の形態の説明において「部」として説明するものの処理（機能）を実行するプログラムが含まれる。ファイル９３２には、本発明の実施の形態の説明において「部」として説明するものによって演算、加工、読み取り、書き込み、利用、入力、出力等が行われるデータ、情報、信号（値）等が含まれる。
【０１９５】
処理装置９４０は、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ）である。処理装置９４０は、バス等を介して他のハードウェアデバイスと接続され、それらのハードウェアデバイスを制御する。処理装置９４０は、記憶装置９３０からプログラム９３１を読み出し、プログラム９３１を実行する。処理装置９４０は、本発明の実施の形態の説明において「部」として説明するものによって演算、加工、読み取り、書き込み、利用、入力、出力等を行うために利用される。
【０１９６】
本発明の実施の形態の説明において「部」として説明するものは、「部」を「回路」、「装置」、「機器」に読み替えたものであってもよい。また、本発明の実施の形態の説明において「部」として説明するものは、「部」を「工程」、「手順」、「処理」に読み替えたものであってもよい。即ち、本発明の実施の形態の説明において「部」として説明するものは、ソフトウェアのみ、ハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせで実現される。ソフトウェアは、プログラム９３１として、記憶装置９３０に記憶される。プログラム９３１は、本発明の実施の形態の説明において「部」として説明するものとしてコンピュータを機能させるものである。或いは、プログラム９３１は、本発明の実施の形態の説明において「部」として説明するものの処理をコンピュータに実行させるものである。
【０１９７】
以上、本発明の実施の形態について説明したが、この実施の形態を部分的に実施しても構わない。例えば、この実施の形態の説明において「部」として説明するもののうち、いずれか１つのみを採用してもよいし、いくつかの任意の組み合わせを採用してもよい。なお、本発明は、この実施の形態に限定されるものではなく、必要に応じて種々の変更が可能である。
【符号の説明】
【０１９８】
１００  行列生成装置、１１０  木構造生成部、１１１  論理式入力部、１１２  二分木生成部、１１３  二分木出力部、１２０  ルート処理部、１２１  ルート判定部、１２２ａ  論理積処理部、１２２ｂ  論理和処理部、１２２ｃ  変数処理部、１２３  処理結果出力部、１３０  ノード処理部、１３１  ノード判定部、１３２ａ  論理積処理部、１３２ｂ  論理和処理部、１３２ｃ  変数処理部、１３３  処理数判定部、１３４  処理結果出力部、９１０  出力装置、９２０  入力装置、９３０  記憶装置、９３１  プログラム、９３２  ファイル、９４０  処理装置。
【図１】
2016002020.tif 000015
【図２】
2016002020.tif 000016
【図３】
2016002020.tif 000017
【図４】
2016002020.tif 000018
【図５】
2016002020.tif 000019
【図６】
2016002020.tif 000020
【図７】
2016002020.tif 000021
【図８】
2016002020.tif 000022
【図９】
2016002020.tif 000023
【図１０】
2016002020.tif 000024
【図１１】
2016002020.tif 000025
【国際調査報告】
2016002020.tif 000026
2016002020.tif 000027