ＲＥＴＥネットワーク組織化方法
【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、知識ベース即ちエキスパート・コンピュータ・システムにおいて使用される知識ベースを構築するためのシステムおよび方法に関する。特に、本発明は、知識ベース・コンピュータ・システムにおいて使用されるルールのＲＥＴＥパターン・マッチング・ネットワークを構築するためのシステムおよび方法に関する。
【０００２】
【関連技術】コンピュータにおいて動作するエキスパート・システムのための知識ベースは、典型的にはルールからなっている。これらのルールは、一般にＩＦ−ＴＨＥＮステートメントの形態で表現される。このルールのＩＦ部分は、パターンを形成する条件（システムにおけるオブジェクトに対するテスト）のコレクションを表わす。
【０００３】たくさんのパターンのコレクションとたくさんのオブジェクトのコレクションとのマッチングは、推論エンジンの１つの動作である。推論エンジンは、人工知能およびエキスパート・システムにおける論証構成要素である。推論エンジンは、典型的に３つの構成要素あるいは方法、即ち、(１)オブジェクトのコレクションと与えられたルールとの突合わせ、(２)その条件がオブジェクトに完全にマッチするルールのリストから１つのルールを選択し、(３)選択されたルールの発火（始動）を含む。
【０００４】推論エンジンにおける最も時間を費やす段階は、マッチング・プロセスである。例えば、１０００のオブジェクトと１０００のルールを持つシステムおよび方法であって、各ルールが３つの条件を持つ場合を考えよう。非常に簡単な実現方式においては、各ルールは全てのオブジェクトと比較される。これは、各実行サイクル毎に１兆回以上の突合わせ操作をもたらす。
【０００５】ＲＥＴＥのパターン・マッチング・アルゴリズムは、作業の小さな部分（即ち、１兆回より遥かに少ない突合わせ作業）のみでこの事例の結果を達成することができる複雑なアルゴリズムである。ＲＥＴＥパターン・マッチング・アルゴリズムについては、Ｃ．Ｌ．Ｆｏｒｇｙ著「ＲＥＴＥ： Ａ ＦＡＳＴＡＬＧＯＲＩＴＨＭ ＦＯＲ ＴＨＥ ＭＡＮＹ ＰＡＴＴＥＲＮ／ＭＡＮＹ ＯＡＢＪＥＣＴ ＰＡＴＴＥＲＮ ＭＡＴＣＨ ＰＲＯＢＬＥＭ」（「Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ」、第１９巻、１７〜３７頁、１９８２年）、およびＣ．Ｌ．Ｆｏｒｇｙ著「ＭＥＡＳＵＲＥＭＥＮＴＳ ＯＮ ＰＲＯＤＵＣＴＩＯＮ ＳＹＳＴＥＭＳ」（Ｄｅｐａｒｔｍｅｎｔ ｏｆ ＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，Ｃａｒｎｅｇｉｅ−Ｍｅｌｌｏｎ Ｕｎｉｖ．，米国ペンシルバニア州ピッツバーグ、１９８３年）に記載されている。以降ＲＥＴＥのパターン・マッチング・アルゴリズムについては、本発明により解決される問題の理解のため必要な程度にのみ記述する。
【０００６】このＲＥＴＥのパターン・マッチング・アルゴリズムは、突合わせ要素または方法に対する「分割征服」手法を実現する。与えられたルールを構成する条件がテストされる。１つの条件の失敗は、以降の条件のテストを阻止する。突合わせを行うため、ＲＥＴＥのパターン・マッチング・アルゴリズムは、ルールの前提となるものから組み立てられた（まとめられた）増補識別ネットワーク（本文では、ＲＥＴＥネットワークと呼ぶ）を使用する。各オブジェクトが、このオブジェクトのみに関する条件に対して最初にテストされる。次いで、これらのテストを通ったオブジェクトは、多くのオブジェクトを必要とするテストを行うために他のオブジェクトと一緒にされる。全てのテストを通ったオブジェクトのコレクションは、選択および発火（始動）の候補となる。
【０００７】このＲＥＴＥネットワークは、接続された節点のネットワークを含む。これらの節点とは、ｒｏｏｔ（根）節点、ａｌｐｈａ（アルファ）節点、ｂｅｔａ（ベータ）節点、ａｎｄ（アンド）節点、ｂｅｔａ ｎｏｔ（ベータ否定）節点、ａｎｄ ｎｏｔ（アンド否定）節点、ｔｅｒｍｉｎａｌ（終端）節点およびｇａｍｍａ（ガンマ）節点を含む。各オブジェクト・タイプ毎に１つのｒｏｏｔ節点がある。
【０００８】ｒｏｏｔ節点は、テストされるオブジェクトに対するエントリ点を表わす。ｒｏｏｔ節点は、そのオブジェクト・タイプに基づいてネットワークにおける子節点にそのオブジェクトを同報する。
【０００９】ａｌｐｈａ節点は、要素内（ｉｎｔｒａ−ｅｌｅｍｅｎｔ）テストを表わす。要素内テストは、１つのオブジェクトに対してテストを行う。要素内テストは、オブジェクトの属性がルールにおいて指定される如き定数値を有するかどうかと関連し得る。要素内テストはまた、オブジェクトの属性が述語による定数と関連しているかどうかと関係し得る。要素内テストは、更に、同じオブジェクトの２つの属性が指定された関連の下で一致するかどうかと関連し得る。これらのテストは、ルールの前提において負に定量化される変数について行われる。これらのテストはまた、正に定量化される変数についても行われる。即ち、これらのテストは、変数の不在ならびに変数の存在を検証するため使用され得る。
【００１０】ｂｅｔａ節点およびｂｅｔａ ｎｏｔ節点は、要素間（ｉｎｔｅｒ−ｅｌｅｍｅｎｔ）テストを表わす。要素内テストと異なり、要素間テストは多重データ・オブジェクトの試験属性をテストする。これらのテストは、２つ以上のデータ・オブジェクト間にある関係があるかどうかを判定する。ｂｅｔａ節点は、（１）純粋に負に定量化されるか、あるいは（２）純粋に正に定量化されるデータ・オブジェクトのセットをテストするため用いられる。正に定量化された変数と負に定量化された変数の組合わせに関するテストは、混成量化テストと呼ばれる。これらは、ｂｅｔａ ｎｏｔ節点によりＲＥＴＥネットワークにおいて実現される。ｇａｍｍａ節点は、ｂｅｔａ節点の変形である。ｂｅｔａ節点と同様に、これらの節点は要素間テストを実行する。しかしながら、ｂｅｔａ節点と異なり、これらの節点は、１つのソースからその入力の全てを受取り、ｂｅｔａ節点は左側の入力と右側の入力を有するが、ｇａｍｍａ節点は左側入力のみを有する。
【００１１】全ての要素間テストは、幾つかのデータ・オブジェクトが一緒にされてこれらが１つの点におけるテストに使用できるようにすることを必要とする。ｂｅｔａ節点は２つの入力を持つため、これらはオブジェクトの組合わせに役立つ。しかし、時には、全てのオブジェクトは１つの点（おそらくは、例えば、前のｂｅｔａ節点）において既に使用可能である。もしこの１つの点が要素間テストに対する入力として供し得るならば、２番目の入力は余分である。このため、幾つかの従来のシステムは、この異例な場合を許容するため、ｇａｍｍａ節点とｂｅｔａ節点を区別する。
【００１２】ａｎｄ節点は、後続の節点により後でテストするためのオブジェクトの組合わせを生成するように用いられる。これら節点は、一切のテストを行わない。これらは、単にデータ・オブジェクトのマージを容易にする。ａｎｄ ｎｏｔ節点は、ａｎｄ節点の変形例である。これらは、正に定量化された変数テストの結果を負に定量化された変数テストの結果と統合する。上記のａｌｐｈａ、ｂｅｔａおよびｇａｍｍａテストと関連して見ると、ａｎｄ ｎｏｔ節点はテスト不在の意味を構成する。
【００１３】ｔｅｒｍｉｎａｌ節点は、与えられたルールに対するＲＥＴＥネットワークの底部を表わす。各ルールは唯１つのｔｅｒｍｉｎａｌ節点を有する。
【００１４】同じテストを繰返して行うことを避けるため、ＲＥＴＥネットワークはメモリ節点を使用する。メモリ節点は、ネットワーク内の状態としてのオブジェクトとの突合わせ結果を記憶する。これらの節点は、ａｌｐｈａメモリ節点とｂｅｔａメモリ節点と呼ばれる。メモリ節点を構成するため、ネットワーク内の節点間を通過するオブジェクトは「トークン」と呼ばれ、これは１つのタグおよび１つのオブジェクト・リストからなる。タグは、なにかが知識ベースに加えられたことを示す＋か、あるいはなにかが知識ベースから取除かれたことを示す−であり得る。トークンと関連するオブジェクトのリストは、システムがルールの前提における連続するオブジェクトに対して突合わせを試みるかあるいは既に突合わせた如きオブジェクトの順列と対応する。
【００１５】動作は以下のとおりである。ａｌｐｈａ節点の入力に到着するトークンが関連するテストを満足する時は常に、ａｌｐｈａ節点の子節点へ送られる。もしこのトークンがテストを満足しなければ、子節点へは送られない。もし１つのオブジェクトが全ての要素内テストを満足する（これはまだ全ての要素間テストを満足しないかも知れないが）ならば、このオブジェクトはルールと「部分的に一致する」と言われる。ルールの前提の条件と部分的に一致するオブジェクトと対応するトークンは、ａｌｐｈａメモリ節点に記憶される。もし同じルールあるいは異なるルールの２つのオブジェクトが部分的に一致する全く同じテストを持つならば、ネットワークはこの２つに対してａｌｐｈａメモリ節点を共有する。
【００１６】トークンがｂｅｔａ節点の左側入力に分配されると、ｂｅｔａ節点は入来トークンを、その右側の親のａｌｐｈａ節点に関連するａｌｐｈａメモリ節点に記憶された各トークンと比較する。左側のトークンと一致する各右側トークンの場合は、新しいトークンが構成され、子のｂｅｔａメモリ節点に記憶される。このトークンは、次に子の節点に送られる。新しいトークンは左側のトークンと同じタグを持ち、オブジェクトのリストは左側および右側のトークンに対するオブジェクトの編集物となる。
【００１７】＋タグを持つトークンがｔｅｒｍｉｎａｌ節点に入る時は常に、それは衝突（conflict）セットに関連ルールの（トークンと対応する）インスタンシエーションを加える。−タグを持つトークンの到着は、衝突セットからの対応ルールのインスタンシエーションの削除をもたらす。
【００１８】明らかなように、知識ベースに対して最も後のルールの始動によりなされた変更のみが各サイクル毎に処理されねばならない。これらの変更は、ネットワークを介して「フィルタ」し、関連する場合に、ネットワークに記憶された状態が更新される。これは、ＲＥＴＥのパターン・マッチング・アルゴリズムの重要な属性である。このネットワークの出力は、衝突セットに対する束縛変数の仕様（拘束要因、突合わせたオブジェクト）を含む。
【００１９】ＲＥＴＥネットワークは、ＯＰＳ５（コンピュータ言語）に基づくコンピュータ・システムを用いて初めて実現された。このＯＰＳ５システムは、Ｃ．Ｌ．Ｆｏｒｇｙ著「ＯＰＳ５ ＵＳＥＲＳ ＭＡＮＵＡＬ」（Ｄｅｐａｒｔｍｅｎｔｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｃａｒｎｅｇｉｅ−ＭｅｌｌｏｎＵｎｉｖ．、１９８１年）に記載されている。
【００２０】ＯＰＳ５に基づくコンピュータ・システムにおいて、ユーザは、ルールの左側（ＬＨＳ）即ち前提を論理積形態にフォーマットしなければならない。換言すれば、ＲＥＴＥネットワークは、論理積形態で表現されるルールのみを処理することができる。ｐ１と名付けられた典型的なＯＰＳ５ルールは、下記の構文を用いて表現される。即ち、（ｐ ｐ１ （Ｃ１ ↑ａｔｒｒ１ ＜ｘ＞ ↑ａｔｔｒ２ １２）
（Ｃ２ ↑ａｔｔｒ１ １５ ↑ａｔｔｒ２ ＜ｘ＞）
−（Ｃ３ ↑ａｔｔｒ１ ＜ｘ＞）
（ｒｅｍｏｖｅ ２））
ルールｐ１は、そのＬＨＳに３つの条件を有する。これらの条件は、閉じ括弧のセットにより識別される。
【００２１】第１の条件（ルールの最初の行）は３つの個々のテストを有する。最初のテストは、オブジェクトがタイプＣ１であるかどうかに対応する。第２のテストは、タイプＣ１のオブジェクトが属性↑ａｔｔｒ１およびある値＜ｘ＞を持つかどうかに対応する。どんな値でも変数ｘと一致し得る。（ある変数による値の指定の示唆については以下において論述する。）第３のテストは、タイプＣ１のオブジェクトが１２に等しい値を持つ属性↑ａｔｔｒ２を有するかどうかに対応する。
【００２２】第２の条件（ルールの２行目）もまた、３つの個々のテストを有する。最初のテストは、オブジェクトがタイプＣ２であるかどうかに対応する。第２のテストは、タイプＣ２のオブジェクトが１５に等しい値を持つ属性↑ａｔｔｒ１を持つかどうかに対応する。第３のテストは、タイプＣ２のオブジェクトが値＜ｘ＞を持つ属性↑ａｔｔｒ２を持つかどうかに対応する。
【００２３】第３の条件（ルールの３番目の行）は、２つの個々のテストのみを有する。この条件が否定である（−参照）ことに注意を要する。最初のテストは、オブジェクトがタイプＣ３であるかどうかに対応する。第２のテストは、タイプＣ３のオブジェクトが属性↑ａｔｔｒ１および値＜ｘ＞を持つかどうかに対応する。
【００２４】ルールｐ１は、コンピュータ・システムおよび方法に第１の条件を満足するオブジェクトが存在し、また第２の条件を満足するオブジェクトが存在し、かつ第３の条件を満足するオブジェクトが存在するならば、始動される。このことが、３つの例示条件間の関係が論理積関係を示すことに注意する必要がある。
【００２５】ルール１においては、変数ｘが各条件に対する１回のテスト、即ち、第１の条件におけるオブジェクト・タイプＣ１の↑ａｔｔｒ１、第２の条件のオブジェクト・タイプＣ２の↑ａｔｔｒ２、および第３の条件におけるオブジェクト・タイプＣ３の↑ａｔｔｒ１において指定されることに注意されたい。変数ｘの共通指定の結果は、ルールが始動するためには、ＯＰＳ５言語コンピュータ・システムのアーキテクチャが、オブジェクトＣ１、Ｃ２およびＣ３と、それらの対応する属性（それぞれ、↑ａｔｔｒ１，↑ａｔｔｒ２，↑ａｔｔｒ１）が同じ値を有することを要求する。ＯＰＳ５に基づくコンピュータ・システムにおいては、これは異なるオブジェクトの属性が等しいかどうかをテストする唯一の方法である。
【００２６】ＯＰＳ５システムのＲＥＴＥネットワーク構築アーキテクチャは、ユーザが１つの条件において異なるオブジェクトの属性が同じであるかどうかをテストすることを許さず、ユーザがオブジェクト・タイプが最初に定義される時テストを包含しなければならないことを理解すべきである。以下に述べるように、この制限は著しい短所である。
【００２７】また、ユーザがオブジェクト・タイプが最初に定義される時与えられたオブジェクト・タイプについて全ての要素内テストを指定しなければならないことも理解すべきである。以下に述べるように、上記の制限は同様にＯＰＳ５ＲＥＴＥネットワーク構築アーキテクチャの著しい短所である。
【００２８】ＯＰＳ５システムは、要素内テスト、即ち単一のオブジェクトに対するテストを求めて、ルールの各条件を逐次調べることによりＲＥＴＥネットワークを構築する。各条件に対して、ネットワーク・コンパイラは、特定のオブジェクト・タイプの要素内テストを調べるテスト節点を一体に繋ぐ（与えられる条件、従ってオブジェクトに対して幾つかの要素内テストが存在し得る）。ＯＰＳ５システムは、ユーザがルールを書いた正確な順序で要素内テストの各々についてａｌｐｈａ節点を構築する。
【００２９】一旦ネットワーク・コンパイラが要素内テストを終了すると、このコンパイラはルールの各条件を再び調べて、要素間テストについて調べる節点を付加する。ＯＰＳ５に基づくシステムは、ｂｅｔａ節点を最初に構築する。ｂｅｔａ節点は、同様にユーザが書いたように正確に同じ順序で構築される。ＯＰＳ５システムは、次にｂｅｔａ ｎｏｔ節点を構築する。このｂｅｔａ ｎｏｔ節点もまた、ユーザが書いたのと正確に同じ順序で構築される。ＯＰＳ５システムにおいては、ｂｅｔａ節点またはｂｅｔａ ｎｏｔ節点の右側の入力は常にａｌｐｈａ節点から入るが、その左側入力はａｌｐｈａ節点またはｂｅｔａ節点から入り得る。
【００３０】次に、ＯＰＳ５コンパイラは各ルール毎にｔｅｒｍｉｎａｌ節点を付加する。
【００３１】明らかなように、ＯＰＳ５システムは「高制御」アーキテクチャを使用する。用語「高制御」とは、ユーザが結果として得るＲＥＴＥネットワーク構造に対して完全な制御を有するシステムおよび方法を意味する。高制御システムは、最適のＲＥＴＥネットワークが構築できるように、ユーザがルールを書く上でＯＰＳ５システムの制約に対する高度の馴染みを持つことを許容する。ＲＥＴＥネットワークの最適化が進むほど、マッチング・プロセスが早くなる。このようなユーザは、時に「パワー・ユーザ」と呼ばれる。効率のよいＲＥＴＥネットワークを構築する際、このような高制御のアーキテクチャに馴染みの少ないユーザは大きな問題に遭遇し易い。
【００３２】先に述べたように、ＯＰＳ５ ＲＥＴＥネットワーク構築アーキテクチャにおける１つの大きな問題は、ルールの前提内のオブジェクトについてのテストの仕様を処理する柔軟性に関する。ＯＰＳ５システムにおいては、ユーザは、オブジェクト・タイプが最初に定義される時、特定のオブジェクトに関する全てのテスト（要素内テストか、あるいは要素間テストか）を指定しなければならない。ＯＰＳ５アーキテクチャは、オブジェクトについての全てのテストが１つの条件内に分類されることを必要とする。ＯＰＳ５アーキテクチャは柔軟性に非常に欠ける。
【００３３】上記の制約は、ユーザが１つのオブジェクトについて任意のテスト、あるいは幾つかのオブジェクトについて相互に関連するテストを書くことを妨げる。ＯＰＳ５アーキテクチャは、ユーザが考えてルールを表現できる方法を決定する。これは、ＯＰＳ５システムの著しい制約である。
【００３４】ＯＰＳ５アーキテクチャにおける別の問題は、論理和を使用する能力に関する。ＯＰＳ５システムは論理和（即ち、ＯＲと関連する条件）を認識せず、ＲＥＴＥネットワークは論理積プロセスのみである。換言すれば、ＲＥＴＥネットワークは成功主義である。オブジェクトは与えられたテストにパスするかあるいはパスしない。ある場合にはパスするが、他の場合にはそうでない中間の根拠がない。論理和の使用は、この「中間の」根拠の使用を意味する。従って、ＲＥＴＥネットワークは、本質的に論理和向きと見做すことができない。ＯＰＳ５においては、ユーザは２つの個々のルールを構築しなければならない。特に、ユーザは論理和の各節に対して１つのルールを作らねばならない。
【００３５】ＯＰＳ５アーキテクチャにおける別の重要な問題は、ユーザが否定ルールを書く能力に関する。ＯＰＳ５システムは、複雑な否定的前提を認識しない。ユーザは、ルールを肯定的に枠付けしたステートメントで書かざるを得ない。
【００３６】ＯＰＳ５アーキテクチャの別の問題は、ＲＥＴＥに基づくシステムにおけるルールの動作（ＲＨＳ）部分を実施するために、ＲＨＳで参照されたオブジェクトがルールのＬＨＳに拘束されねばならないという要件に関する。ＯＰＳ５に基づくシステムにおいては、ユーザは、ルールのＲＨＳにおいて操作されるオブジェクトがルールのＬＨＳで参照されることを確実にしなければならない。この要件を満たすことができないと、システムの誤動作をまねく結果となることがある。
【００３７】上記のことは標準的なＲＥＴＥネットワークの処理について述べたが、他の構成およびＲＥＴＥ処理の強化は可能である。例示に過ぎないが、ＲＥＴＥネットワーク処理の修正についてはＭ．Ｉ．Ｓｃｈｏｒ等著「Ａｄｖａｎｃｅｓ ＩｎＲＥＴＥ Ｐａｔｔｅｒｎ Ｍａｔｃｈｉｎｇ」（ＩＢＭ Ｔ．Ｊ．Ｗａｔｓｏｎ Ｒｅｓｅａｒｃｈ Ｃｅｎｔｅｒ，ニューヨーク州ヨークタウン・ハイツ、１９８６年）に記載されている。
【００３８】ＲＥＴＥパターン・マッチング・アルゴリズムに対する別の拡張は「ＴＲＥＡＴアルゴリズム」である。このＴＲＥＡＴアルゴリズムについては、Ｄ．Ｐ．Ｍｉｒａｎｋｅｒ著「Ｔｒｅａｔ： Ａ Ｂｅｔｔｅｒ Ｗａｙ ｆｏｒ ＡＩＰｒｏｄｕｃｔｉｏｎ Ｓｙｓｔｅｍｓ」（Ｐｒｅｃｅｅｄｎｇｓ ｏｆ ６ｔｈＮａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ ＡｒｔｉｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅ、カナダ、ＷＡ、シアトル、１９８７年７月１３日〜１７日、４２〜４７頁）に記載されている。同文献に記載の如く、主な相違は、ＴＲＥＡＴアルゴリズムがネットワークにおける部分的結果をセーブしないことである。これは、ＲＥＴＥアルゴリズムより小さなメモリを使用するという利点を有する。
【００３９】
【発明の目的】以下に示すように、本発明は、ＲＥＴＥパターン・マッチング・アルゴリズムの広範囲な拡張に等しく適用し得るものである。
【００４０】本発明の一目的は、オブジェクトに対する任意に指定されたテストを有するルールを処理することができるＲＥＴＥネットワーク構築システムおよび方法を開発することにある。
【００４１】本発明の別の目的は、論理和によってオブジェクトに対するテストを関連させるルールを処理できるＲＥＴＥネットワーク構築システムおよび方法の開発にある。
【００４２】本発明の更に別の目的は、否定ルールを処理できるＲＥＴＥネットワーク構築システムおよび方法の開発にある。
【００４３】本発明の更に他の目的は、ルールの前提に指定されない暗黙の条件を有するルールを処理できるＲＥＴＥネットワーク構築システムおよび方法の開発にある。
【００４４】上記および他の目的については、本発明のシステムおよび方法により達成される。
【００４５】
【発明の概要】本発明は、従来のＲＥＴＥネットワーク生成システムおよび方法においてはこれまで得られない利点を提供する。本発明は、ＲＥＴＥネットワーク・システムの要件および利点を維持しながらＲＥＴＥネットワークを構成する、斬新な試みを用いるコンピュータ・システムおよび方法である。当業者には明らかなように、本発明は、ＲＥＴＥネットワークの種々の増強により統合化が可能であり、本発明の趣旨から逸脱することなく修正可能である。
【００４６】本発明は、主としてコンピュータによる人工知能あるいはエキスパート・システム構築ツールの環境において使用されることが予期される。しかし、本発明は、専用の人工知能またはエキスパート・システム・コンピュータ・システムと統合化が可能である。
【００４７】一実施例においては、本発明のシステムおよび方法は、オブジェクトに対する任意の指定されたテストを有するルールを処理することができる。ユーザは、オブジェクトの順序を心配することなくルールを書くことができる（このような心配は、従来のＲＥＴＥネットワーク生成システムおよび方法には存在する）。同時に、本発明のシステムおよび方法は、ユーザがＲＥＴＥネットワークのトポロジーをかなりの程度制御することを可能にする。
【００４８】本発明のシステムおよび方法は、(１)ＲＥＴＥネットワークの全体的なトポロジーを制御するため要素間テスト（例えば、ｂｅｔａ、ｂｅｔａ ｎｏｔ）のユーザにより書かれる如き相対的順序付けを可能にし、(２)前記要素間テストの相対的順序付けを考慮し、(３)オブジェクトの１の属性は複雑なテストにおいて参照されないが、オブジェクトの別の属性に対するテストの順序付けをできる限り考慮し、(４)ＲＥＴＥネットワークのサブセット全体が前記テストの成否の結果として可能化あるいは不能化されるかをその配置が制御するので、前記要素内テストがＲＥＴＥネットワークの性能を調整することを許容し、および（または）(５)負に定量化されたテストの意味論的意義を保存することにより、上記の特徴を達成する。
【００４９】別の実施例においては、本発明のシステムおよび方法は、ＲＥＴＥネットワークが性格において本質的に論理積的である（即ち、条件が一緒に＊＊ＡＮＤされることを要求する）故に、（典型的にＯＲ演算子により識別される）論理和形態で表わされるルールを認識し処理することができ、本発明はこのルールをＲＥＴＥネットワークを構築するように内部的に修正する。これを達成するため、本発明は、ＯＲ節を持つルールの前提を使用する。論理の標準的な論理和ルールを用いて、これを論理和正規形に変換する。この操作の結果、一緒にＯＲされる１組の論理積節をもたらすことになる。変換の後、本発明は論理積節について処理して各節毎に個々のルールを形成する。
【００５０】別の実施例においては、本発明のシステムおよび方法は、否定ルール（典型的には、ＮＯＴ演算子により識別される）を認識する。ＲＥＴＥネットワークはルールの任意の否定を取扱うことができないため、本発明のシステムおよび方法は、論理和ルールの場合のように、ルールを内部的に修正してＲＥＴＥネットワークを構築する。本発明のシステムおよび方法は、否定節に対してこれを肯定節に変換するためド・モルガンの法則を用いることによりこの変換を行う。
【００５１】別の実施例においては、本発明のシステムおよび方法は、暗黙条件を取扱う。本発明は、ルールの右側（ＲＨＳ）における各オブジェクトを検査して、これがルールの左側（ＬＨＳ）にあることを保証する。もしオブジェクトがＲＨＳに存在するがＬＨＳになければ、これは暗黙条件になる候補である。もし本発明がオブジェクトがＬＨＳの暗黙条件であると判定するならば、このオブジェクトをＲＥＴＥネットワークに加える。
【００５２】本発明の種々の目的、特徴および付随する利点については、本発明の以降の詳細な記述により更によく理解されよう。詳細な記述は、添付図面を参照する。
【００５３】
【実施例】本発明は、ＲＥＴＥネットワークを構築するためのシステムおよび方法である。本発明のシステムおよび方法は、従来のＲＥＴＥネットワーク構築システムおよび方法においてはこれまで得られなかった利点を提供する。本発明は、コンピュータに基づくエキスパート・システムの開発シェルおよび専用エキスパート・システムと共に統合化が可能である。図１は、本発明の動作を全般的に示す高レベルのブロック図である。動作ブロック１０１に示されるように、本発明はまず、１階述語論理あるいは相当の形態と機能的に実質上等価である構文でルールをユーザが入力することを可能にする。１階述語論理は、例えば、ルールを論理和、論理積あるいは否定形で表現することを許容する。
【００５４】動作ブロック１０２は、本発明の第２の動作を示す。動作ブロック１０２は、ルールについて動作（変換）してＲＥＴＥネットワークを表わすデータ構造を生成する。更に、動作ブロック１０２は、オブジェクトに対するテストを任意指定したルールを認識して処理するように動作する。動作ブロック１０２は、更に、論理和関係を持つオブジェクトに対する２つ以上のテストを有するルールを認識して処理するように動作する。動作ブロック１０２は更に、論理積関係を有するオブジェクトに対する２つ以上のテストを有するルールを認識して処理するように動作する。
【００５５】動作ブロック１０２に対応する構造は、本発明のＲＥＴＥネットワーク・モジュール２０６（最初に図２に関して論述する）である。以下において明らかになるように、本発明のＲＥＴＥネットワーク・モジュール２０６は、ユーザがルールをより多くの意義を持ちかつ理解可能なように表現することを可能にする。
【００５６】動作ブロック１０４は、ＲＥＴＥネットワークを表わす結果として得るデータ構造を示している。
【００５７】次に図２において、本発明のＲＥＴＥネットワーク・モジュール２０６のコンピュータ環境２００が示される。コンピュータ環境２００は、一般に、中央処理装置（ＣＰＵ）２０２と、ＲＥＴＥネットワーク・モジュール２０６を格納する主メモリ２０４と、入出力（Ｉ／Ｏ）デバイス２０８と、バッファ２１２とを含む。ＣＰＵ２０２、主メモリ２０４およびバッファ２１２は、ホスト・バス２１４を介して通信する。Ｉ／Ｏデバイス２０８およびバッファ２１２は、システム・バス２１６を介して通信する。
【００５８】望ましい実施態様においては、図２に示した形態は、ＩＢＭ ＰＳ／２パーソナル・コンピュータのワークステーション環境の形態である。ＩＢＭＰＳ／２は、「ＩＢＭ ＰＳ／２ Ｇｕｉｄｅ ｔｏ Ｏｐｅｒａｔｉｏｎｓ Ｍａｎｕａｌ」（米国ニューヨーク、アーモンク）に詳細に説明されている。
【００５９】コンピュータ環境２００を構成するコンピュータの構成要素／サブシステムは従来の設計であることを理解すべきである。現在入手可能な、あるいは将来開発される適当なコンピュータ構成要素／サブシステムを使用することができる。単なる例示として、本発明は、メインフレーム・コンピュータの如き他の形態で統合することが可能である。また、本発明は典型的には別のソフトウエア・モジュール（図示せず）と関連して動作することも理解すべきである。このような付加的なソフトウエア・モジュールは、エキスパート・システムのアプリケーションを開発できるようにするために必要となろう。
【００６０】また、ＲＥＴＥネットワーク・モジュール２０６は種々の他の形態において提供できることも理解すべきである。単なる例示として、ＲＥＴＥネットワーク・モジュール２０６は、ハードウエアまたは読出し専用メモリ（ＲＯＭ）デバイス（図示せず）に構成することができるファームウエアの形態を取ることもできる。更にまた、ＲＥＴＥネットワーク・モジュール２０６は、各ＲＯＭがＲＥＴＥネットワーク・モジュール２０６により実行されるものと類似する特定の動作を実行する、多重構成ＲＯＭの形態を取ることもできる。
【００６１】ＲＥＴＥネットワーク・モジュール２０６の高レベルの構造的表示が図３に示される。図示の如く、ＲＥＴＥネットワーク・モジュール２０６は、パーサ（構文解析）モジュール３０２と変換モジュール３０４とを含む。
【００６２】構文解析モジュール３０２は、ユーザにより入力されるルールを抽出して解釈し、またメモリ装置２０４（図２）に格納されたこれらルールを表わすデータを生成する機能を有する。一旦メモリ装置２０４に格納されると、このルールは、ＲＥＴＥネットワークを構築するため変換モジュール３０４により操作することができる。一般に、当技術において構文解析系（パーサ）は周知である。更に、大半のコンピュータ・システムは構文解析系を典型的に使用する。しかし、構文解析系は、通常は各システムの特定の要件を満たすように注文設計されている。
【００６３】図４は、本発明の構文解析モジュール３０２の高レベルの動作を示すブロック図である。動作ブロック４０２により示されるように、構文解析モジュール３０２は、ＣＰＵ２０２に対して最初に各ルール（前述の如く、１階述語論理と類似する構文で表現される）を調べることを指令する。動作ブロック４０４により示されるように、構文解析モジュール３０２は、ＣＰＵ２０２に各ルール毎に１つの抽象構文ツリーを生成するように命令する。動作ブロック４０６により示されるように、構文解析モジュール４０２は次に、変換モジュール３０４により後で処理するため、メモリ装置２０４に各ルールに対する抽象構文ツリーを記憶するように指令する。
【００６４】当業者には、１階述語論理に従う多数の言語が開発できることが明らかであろう。本発明の望ましい実施態様においては、構文解析モジュール３０２は、ＫＲＬと本発明者が呼ぶ構文におけるルールを認識して処理することができる。ＫＲＬは知識表現言語である。ＫＲＬ構文は、「Ｔｈｅ ＩＮＴＥＧＲＡＴＥＤ ＲＥＡＳＯＮＩＮＧ ＳＨＥＬＬ ＲＥＦＥＲＥＮＣＥ ＭＡＮＵＡＬ，ＩＢＭ」（１９８９年）に詳細に説明されている。
【００６５】ＫＲＬルールは、Ｉｆ−Ｔｈｅｎステートメントの形態で構成される。本発明においては、ユーザは、ＫＲＬルールのＩｆ部分を論理積、論理和あるいは否定形のいずれかで入力することができる。以下において明らになるように、本発明は、ユーザがルールのＩｆ部分を論理積、論理和あるいは否定形のいずれかで入力することを許容する構文言語を処理するために使用することができる。
【００６６】ＫＲＬ構文は、本発明が認識し処理できる唯一の言語である。現在入手可能な、あるいは将来開発される他の言語（構文）を使用することができる。当業者には明らかなように、このような状況においては、構文解析モジュール３０２は、実際に使用される構文の様式に見合うように修正（特別注文）されねばならないことになる。
【００６７】本論の目的にとって、僅かに高いレベルの抽象化でＫＲＬルールを表わすことが役立とう。この抽象化は、本文ではＫＲＬショートハンドと呼ぶ。
【００６８】ＫＲＬショートハンドにおいては、１つの文字で完全な要素内テストあるいは要素間テストが表わされる。例えば、車（オブジェクト）の色（属性）が青（属性値）であるかどうかをテストするルール条件においては、ＫＲＬは下記の如くになる。即ち、 ｘ： ｃａｒ Ｉｆ ｘ.ｃｏｌｏｒ ＝ 'Ｂｌｕｅ' ｔｈｅｎ... ＫＲＬショートハンドでは、簡単に書くことになる。即ち、 Ｉｆ Ａ ｔｈｅｎ....ここで、Ａは条件テスト全体を意味すると見做される。
【００６９】ＲＥＴＥネットワーク構成の目的のためにルールの顕著な要素を理解するための手段を除いて、ＫＲＬに勝るＫＲＬショートハンドの利点はない。
【００７０】本発明の望ましい実施態様は実際にはＫＲＬを使用すると理解すべきであるが、本文における全ての事例ルールはＫＲＬショートハンドで示される。
【００７１】再びＫＲＬの事例について見れば、Ｒｕｌｅ １．０で示されるルールのＬＨＳの表記は、下記のように論理積形で書くことができる。即ち、 Ｒｕｌｅ １.０．
ＫＲＬでは、ｘ： ｃａｒ： Ｉｆ ｘ.ｃｏｌｏｒ＝'Ｂｌｕｅ' ａｎｄ ｘ.ｗｈｅｅｌｓ＝４ ｔｈｅｎ.... ＫＲＬショートハンドでは、Ｉｆ Ａ ａｎｄ Ｂ ｔｈｅｎ...ＫＲＬショートハンドでは、シンボルＡおよびＢはそれぞれ、ルール１．０内の個々のテストを示す。各テストは、１つのオブジェクトについての要素内テスト、あるいは幾つかのオブジェクトについての要素間テストと対応し得る。以下に述べるように、本発明は、オブジェクトに対するテストの任意仕様を認識することができる。例えば、テストＡは、車の色が青であるかどうかと対応する。テストＢは、同じオブジェクトが４つの車輪（別の属性値の対）を持つかどうかと対応する。
【００７２】従来のＲＥＴＥネットワーク構築システムおよび方法は、本発明とは異なり、テストの上記の任意の論理積を認識して処理することができない。
【００７３】以下は、論理和形で書かれたＲｕｌｅ２．０で示されるＫＲＬルールのＬＨＳの表記である。即ち、 Ｒｕｌｅ２．０ Ｉｆ Ａ ｏｒ Ｂ ｔｈｅｎ．．．
下記は、それぞれＲｕｌｅ３．０および３．１で示される、否定形で書かれた２つのＫＲＬルールのＬＨＳの表記である。即ち、 Ｒｕｌｅ３．０ Ｉｆ ＮＯＴ（Ａ ａｎｄ Ｂ） ｔｈｅｎ．．．
Ｒｕｌｅ３．１ Ｉｆ ＮＯＴ（Ａ ｏｒ Ｂ） ｔｈｅｎ．．．
本発明の構文解析モジュール３０２は、論理積、論理和あるいは否定形のいずれかで表わされるルールを処理（構文解析）するように設計される。構文解析モジュール３０２はまた、オブジェクトに対するテストの任意仕様を処理するように設計される。更に、構文解析モジュール３０２は、ルールの能動部分（即ち、ＲＨＳ）を処理するように設計される。
【００７４】動作ブロック４０４に関して先に述べたように、構文解析モジュール３０２は各ＫＲＬルールに対して１つの抽象構文ツリーを生成する。抽象構文ツリーは当技術においては周知である。この抽象構文ツリーは、変換モジュール３０４により後で処理されるように、メモリ装置２０４に表現を示す便利な方法である。データ構造はメモリ装置２０４に格納される。望ましいモードにおいて、抽象構文ツリーはＫＲＬルールを表わすデータ構造である。
【００７５】単なる例示として、ＫＲＬショートハンドで示されるＲｕｌｅ４．０で示したＫＲＬルールの下記の抽象化について考察しよう。即ち、 Ｒｕｌｅ４．０ Ｉｆ(Ａ ａｎｄ Ｂ ａｎｄ Ｃａｎｄ Ｄ) ｔｈｅｎ...図５は、構文解析モジュール３０２により構築されたＲｕｌｅ４．０と対応する抽象構文ツリーを示す。Ｒｕｌｅ４．０に対する抽象構文ツリーは、プロダクション節点５０４、ＡＮＤ節点５０８、テストＡ節点５１０、テストＢ節点５１２、テストＣ節点５１４およびテストＤ節点５１６を含む。プロダクション節点５０４は、このルールに対するメモリ装置２０４内の場所である。各ルールは、関連するプロダクション節点を有する。また、プロダクション節点５０２および５０６も示される。プロダクション節点５０２および５０６は、各プロダクション節点が接続されることを示すため示される。
【００７６】ＡＮＤ節点５０８は、抽象構文ツリーの最も高いレベルである。ＡＮＤ節点５０８は、テストＡ、Ｂ、Ｃ、Ｄ間、即ちテストＡ節点５１０、テストＢ節点５１２、テストＣ節点５１４、テストＤ節点５１６の論理積関係を示す。
【００７７】また、数式節点５１８も示される。数式節点５１８は、テストＡ（テスト節点５１０）において行うことができる数学的演算を表わす。例えば、＝、＞または＜、＞＝、＜＝、＝タイプの数学的演算を実施することができる。例えば、ある数学式は下記のテストである。即ち、ｘ＝４。図５に更に示されるのは、本発明のシンボル・リスト節点５２４である。シンボル・リスト節点５２４は、テスト節点５１０の数式節点５１８において使用される特有な変数の合計リストである。本発明のシンボル・リスト節点は、各テスト条件において生じるオブジェクトを要約する便利な方法を提供する。以下に述べるように、シンボル・リストは本発明の重要な特質である。シンボル・リストは、フロー・リスト（以下に述べる）を許容し、従ってＲＥＴＥネットワークを容易に構成する。ここでは、シンボル・リストが、与えられたテストと関連する全ての特有な（全ての異なる型（種類）の）変数を含むメモリ装置２０４に格納されたリストを表わすと理解することが重要である。
【００７８】以下に述べるように、与えられたルールに対するＲＥＴＥネットワークを構築するため必要である重要な情報は、どのオブジェクトがルールの各条件テストと関連するか、どれだけが特有であり、オブジェクトが負に定量化されるかどうかである。特に、与えられたテスト節点に含まれるオブジェクトの量は、テスト節点がＲＥＴＥネットワークにおいて１入力節点あるいは２入力節点として表わされるかを決定する。
【００７９】変換モジュール３０４の高レベルのブロック図が図６に示される。図示の如く、変換モジュール３０４は、否定モジュール６０２と、論理和モジュール６０４と、構成モジュール６０６と、暗黙条件モジュール６０８と、最適化モジュール６１０を含む。これらのモジュールの動作は、図７に関して説明する。
【００８０】図７は、変換モジュール３０４の動作を高レベルで示すブロック図である。動作ブロック７０４（これは、「ｎｏｔ処理」と呼ばれる）により示されるように、変換モジュール３０４は、各抽象構文ツリーを最初に調べてこのルールが否定されるかどうかを判定するようにＣＰＵ２０２に対して命令する。もしこのルールが否定されるならば、変換モジュール３０４はＣＰＵ２０２に対して否定を排除するように命令する。望ましい実施態様においては、これは変換モジュール３０４により行われる最初の動作である。変換モジュール３０４においては、この動作は否定モジュール６０２（図６）によって行われる。しかし、動作ブロック７０４により示される動作は必ずしも変換モジュール３０４により最初に行われる動作である必要がないことを理解すべきである。しかし、もし否定が最初に指定されなければ、別のＯＲ節点が導入され、更に処理が要求されることになる。このため、望ましい実施態様では、否定を最初に排除することにする。他のメソッドは本質的にそれほど有効ではない。
【００８１】動作ブロック７０６（「ＯＲ処理」と呼ぶ）により表わされる如く、変換モジュール３０４は、各抽象構文ツリーを再び調べて、論理和形で表わされるルールを論理積正規形に変換するようにＣＰＵ２０２に命令する。この動作は、論理和モジュール６０４（図６R>６）により行われる。
【００８２】望ましい実施態様においては、上記の論理和フォーマット動作は、変換モジュール３０４により行われる第２の動作である。しかし、動作ブロック７０６により示される動作は必ずしも変換モジュール３０４により行われる第２の動作である必要はないことを理解すべきである。例えば、動作ブロック７０６により示される動作は、動作ブロック７０４により示される動作が後に続く最初の動作であってもよい。しかし、先に述べたように、望ましい実施態様は否定を最初に排除する。
【００８３】ブロック７０４、７０６により示される動作は、ＲＥＴＥネットワークの構築に先立ち生起する先行処理である。これらの動作は、ユーザが与えられたルールを否定形および（または）論理和形で表わすことを可能にする。これらの動作は、本発明の重要な特徴である。
【００８４】動作ブロック７０８により示されるように、変換モジュール３０４は次に、ＣＰＵ２０２に対して本発明のＲＥＴＥネットワークを構築するように命令する。動作ブロック７０８は、ＲＥＴＥネットワークの実際の構築プロセスを示す。この動作は、構成モジュール６０６（図６）によって行われる。
【００８５】動作ブロック７１０により示されるように、変換モジュール３０４は、必要に応じて、ＣＰＵ２０２に暗黙条件を加えることを指令する。動作ブロック７１０は、ルールのＲＨＳにおける各オブジェクトを調べてこれがルールのＬＨＳに存在することを保証するプロセスを示す。この動作は、暗黙条件モジュール６０８（図６）により行われる。
【００８６】動作ブロック７１２により示されるように、変換モジュール３０４は、最後にＣＰＵ２０２に対して本発明のＲＥＴＥネットワークを最適化するように指令する。動作ブロック７１２は、２つ以上のルールに現れるテストが同じテスト節点を共有するように、ＲＥＴＥネットワークを再構成するプロセスを示す。この動作は、最適化モジュール６１０（図６）により行われる。
【００８７】次に変換モジュール３０４の構造について論述する。否定モジュール６０２が図８において（図６のその一般形態に加えて）拡張された形態で示されることに注意する。図示の如く、否定モジュール６０２は、下方否定モジュール８０２と、ＡＮＤ排除モジュール８０４と、ＯＲ排除モジュール８０６とを含む。
【００８８】下方否定モジュール８０２は、コンピュータ環境２００が否定ルールを認識するように提供される。以下に示すＲｕｌｅ５．０は、構文記法で表わされる否定ルールの事例である。即ち、 Ｒｕｌｅ５．０ Ｉｆ ＮＯＴ(Ａ ａｎｄ（Ｂ ｏｒ Ｃ）ａｎｄ ＮＯＴ Ｄ）
上記の如く、式全体またはＬＨＳが否定される。
【００８９】Ｒｕｌｅ５．０に対する抽象構文ツリーが図９に示される。
【００９０】以下は、図９の抽象構文ツリーと関連して図８に示した（下方）否定モジュール８０２の動作の論議である。下方否定モジュール８０２は、各ルール（従って、ルール５．０）に対する抽象構文ツリーを調べて、これが否定されるルールであるかどうかを判定するようにＣＰＵ２０２に対して指令する。ルール５．０の事例においては、下方否定モジュール８０２は、ルール５．０が否定されることを判定する。次いで、下方否定モジュール８０２は、ルール５．０の抽象構文ツリーについて動作して否定節点を排除する。これは、ド・モルガン理論および（または）２重否定の法則をルール５．０のＬＨＳに対して用いることにより行われる。換言すれば、ＮＯＴ節点９０４により示される否定は、ルール５．０内の個々の命題（条件）へプッシュ・ダウンされる。
【００９１】ルール５．０のＬＨＳに否定を分配することは、結果として下記の構文記法を得る。即ち、 ＬＨＳ＝ＮＯＴ Ａ ＯＲ（ＮＯＴ Ｂ ＡＮＤ ＮＯＴ Ｃ）ＯＲ Ｄ図１０は、図１０に示した如き否定が下方否定モジュール８０２によりプッシュ・ダウンされた後の修正された抽象構文ツリーを示している。図９のＡＮＤ節点９０６の否定は図１０のＯＲ節点１００２と等価であることを注目すべきである。換言すれば、これらは、式ＮＯＴ（Ａ ａｎｄ Ｂ）＝ＮＯＴ Ａ ｏｒＮＯＴ Ｂを表わす。後者の式は、論理和を除いて、ＲＥＴＥネットワークに対する適正なフォーマットである。同様に、否定ＯＲ節点は、ＡＮＤ節点となる。
【００９２】また、図９および図１０において判るように、テストＡ節点９０８は、ＮＯＴテストＡ節点１００４となる。このＮＯＴ表記は、否定がこの条件レベルへプッシュ・ダウンされたことを示す。実際問題として、このことは、例えばｚ＝４であったテストがこの時４に等しくないＺとなることを意味する。また、ＯＲ節点９１０がＡＮＤ節点１００６となることに注意すべきである。テストＤ節点９１８を伴うＮＯＴ節点９１２は、通常のテストＤ節点１００８となる。ここで、図１０の構文解析ツリーは全ての観点において図９の構文解析ツリーと等価であることが明らかな筈である。換言すれば、図１０の構文解析ツリーは、依然としてユーザにより最初に示された如くルール５．０の論理的意味を表わす。
【００９３】従来のＯＰＳ５システムにおいては、ユーザは全体として否定されたルールを書くことができない。その代わり、ユーザは単に個々に条件を否定できるに過ぎない。対照的に、本発明、特に否定モジュール８０２は、ユーザに対してこのステップを実施する。これは、ユーザが否定されたルールとしてルールを表現することを可能にし、このことはユーザにとって更に有意義となろう。
【００９４】一旦与えられたルールが「操作」されて（もしあれば）否定がその最も低いレベル（条件命題レベル）へプッシュ・ダウンされたことが保証されると、否定モジュール６０２は次に冗長なＡＮＤ節点を排除する機能を行う。この機能は、ＡＮＤ排除モジュール８０４により行われる。冗長ＡＮＤ節点を含むルール６．０で示される事例ルールは、シンボル的に下記の如く示される。即ち、 Ｒｕｌｅ６．０ （Ａ ＡＮＤ Ｂ）ＡＮＤ（Ｃ ＯＲ Ｄ）ＡＮＤ Ｇ冗長ＡＮＤ節点の全ての連続層に対して実行が継続する。
【００９５】ルール６．０に対する抽象構文ツリーが、図１１に示される。明らかなように、冗長ＡＮＤ節点１１０４および１１０６が存在する。ＡＮＤ節点１１０６の排除がルール６．０の意味論的意義に影響を及ぼさないことに注意すべきである。ＡＮＤ排除モジュール８０４の実行は、ルール６．０をルール６．１として示される下記の修正式に変換する。即ち、 Ｒｕｌｅ６．１ Ａ ＡＮＤ Ｂ ＡＮＤ（Ｃ ＯＲ Ｄ）ＡＮＤ Ｇルール６．１に対する抽象構文ツリーは、図１２に示される。ＡＮＤ排除モジュール８０４は、冗長ＡＮＤ節点１１０６を排除するタスクを行う。明らかなように、図１１１１のテストＡ節点１１１２およびテストＢ節点１１１４は、構文解析ツリーにおいて「上げ」られた。
【００９６】しかし、ＡＮＤ排除モジュール８０４は必ずしも本発明によるＲＥＴＥネットワークの構築に必要でないことに注意すべきである。しかし、冗長ＡＮＤ節点を排除しないと、より大きな従ってより非効率的なＲＥＴＥネットワークをもたらす結果となることがある。
【００９７】ＯＲ排除モジュール８０６は、ＡＮＤ排除モジュール８０４と同様に動作する。ＯＲ排除モジュール８０６の目標は、冗長ＯＲ節点を排除することである。
【００９８】図１３は、論理和モジュール６０４に対するアーキテクチャを示す。論理和モジュール６０４は、各ルールから論理和を排除する機能を有する。論理和モジュール６０４は、発見モジュール１３０２、シャフラ・モジュール１３０４、排除モジュール１３０６およびザッパー・モジュール１３０８を含む。
【００９９】図１４は、論理和モジュール６０４の動作を示す高レベルのブロック図である。動作ブロック１４０２により示されるように、論理和モジュール６０４は最初ＣＰＵ２０２に対して各抽象構文ツリーを調べるように指令する。論理和モジュール６０４は更に、ＣＰＵ２０２に対して抽象構文ツリーを調べるように指令すると、このＣＰＵはＯＲ節点を子節点として有するＡＮＤ節点を見出すように働く。もしＯＲ節点が見出されると、次の動作が行われる。
【０１００】動作ブロック１４０４により示されるように、論理和モジュール６０４はＣＰＵ２０２に対してＯＲ節点を抽象構文ツリーにおける最も高い述語レベルへ「上げる」ように指令する。この動作は、１つのルールが２つの個別のルールに分けることができるように行われる。この動作は、抽象構文ツリーを経て何回かの繰返しを生じる。一旦論理和モジュール６０４がＯＲをその最も高い述語レベルへ移すと、これは次の動作を行う。
【０１０１】動作ブロック１４０６により示されるように、論理和モジュール６０４は、ＣＰＵ２０２に対して２つのルールを生成することによりＯＲ節点を排除するように指令する。換言すれば、論理和モジュール６０４は、論理和の各「足」毎に１つのルールを生成するよう働く。この動作は、分配則を用いることによって実行される。この動作は、ユーザにより最初に指定されたルールの意味論的意義に影響を及ぼすことはなく、これは単にＯＲのいずれか一方の側がルールの突合わせの目的には充分であるという事実を反映する。
【０１０２】図１３の論理和モジュール６０４のサブコンポーネントの各々に対するアーキテクチャは下記の如くである。
【０１０３】発見モジュール１３０２は、抽象構文ツリーの各々を調べてＯＲ節点をその子節点として有するＡＮＤ節点を見出す機能を有する。もし発見モジュール１３０２がこのようなＯＲ節点を見出すならば、発見モジュール１３０２はシャフラ・モジュール１３０４へ制御を渡す。
【０１０４】シャフラ・モジュール１３０４は、ＯＲ節点が構文解析ツリーの先頭へ移るように、与えられた抽象構文ツリーの節点を認識する。シャフラ・モジュール１３０４は、ルールの意味論的意義に影響を及ぼすことなく抽象構文ツリーを認識する。
【０１０５】シンボル記法で表現された下記の例示ルールについて考察しよう。このルールは、ルール７．０として記される。即ち、Ｒｕｌｅ７．０ （Ｃ ＯＲ Ｄ）ＡＮＤ Ｅルール７．０に対する抽象構文ツリーが図１５に示される。示されているのはプロダクション節点１５０２、１５０４および１５０６である。プロダクション節点１５０４が、例えばルール７．０と対応する。更に、２つの子節点、即ちＯＲ節点１５１０およびテストＥ節点を持つＡＮＤ節点１５０８が示される。ＯＲ節点１５１０は、その子節点としてテストＣ節点１５１４とテストＤ節点１５１６を有する。
【０１０６】分配則の使用により、ルール７．０を示すシンボル記法は下記の記法と等価であり、これはルール７．１として識別される。即ち、 Ｒｕｌｅ７．１ （Ｃ ＡＮＤ Ｅ）ＯＲ（Ｄ ＡＮＤ Ｅ）
明らかなように、ルール７．０の論理表現は、式（Ｃ ＡＮＤ Ｅ） ＯＲ （Ｄ ＡＮＤ Ｅ）に修正された。図１６は、修正されたルール７．１に対する抽象構文ツリーを示す。図示の如く、ＯＲ節点１６０２（前は、図１５のＯＲ節点１５１０）が抽象構文ツリーの先頭にある。ＯＲ節点１６０２はこの時、ルールにおける中心演算子となる。ルールの意味論的意義を維持するため、シャフラ・モジュール１３０４はまた、元のＯＲ節点１５１０の全ての兄弟（テストＥ節点１５１２）のコピーを、その各子節点即ちテスト節点１５１４および１５１６に付す。本質的に、前のＯＲ節点１５１０の下のテスト節点１５１４および１５１６は、それぞれＡＮＤ節点の下方の子節点となる。図１６においては、このことは、ＡＮＤ節点１６０４の子節点として示されるテストＣ節点１５１４およびテストＥ節点１５１２により表わされる。同様に、テストＤ節点１５１６およびテストＥ節点１５１２は、ＡＮＤ節点１６０６の子節点となる。図１６の抽象構文ツリーが図１５の抽象構文ツリーと同じ意味論的意義を有することは明らかであろう。
【０１０７】この時、論理和モジュール６０４は、ＯＲ節点１６０２を排除するよう働く。この特徴は、排除モジュール１３０６により行われる。排除モジュール１３０６は、ＯＲが存在するかどうかを判定するため、３回目にＣＰＵ２０２に抽象構文ツリーを調べるように指令する。ＯＲ節点が発見されると直ちに、排除モジュール１３０６が制御を実行ザッパー・モジュール１３０８へ渡す。
【０１０８】ザッパー・モジュール１３０８の構造は、実行されるとこれがＣＰＵ２０２に対してＯＲ節点を排除するように、またＯＲ節点の各子節点に対しては、新しいルール節点を生成するように指令する。このルール節点は、前のルール節点のクローンである。従って、ザッパー・モジュール１３０８は、ＯＲ節点の下方の各子節点をそれ自体の別個のルールへ変える。換言すれば、論理和の足の各々はこの時別個の抽象構文ツリーとして表わされる。
【０１０９】図１７は、ザッパー・モジュール１３０８の上記の動作に対する抽象構文ツリーを示している。図示の如く、ザッパー・モジュール１３０８は２つのルールを生成する。このルールは、ルール節点１５０４およびルール節点１７０２をそれらの格納場所として有する。本質的に、ザッパー・モジュール１３０８は図１６のＡＮＤ節点１６０６およびその子節点を用いて、図１７R>７のルール１７０２と対応する別個のルールを生成する。
【０１１０】上記の論議から判るように、論理和モジュール６０４は、論理和形で書かれたルールについて働いて、２つの別個のルールを生成する。否定モジュール６０２と同様に、論理和モジュール６０４は、コンピュータ・システム環境２００がＯＲ節点を含むルールを認識して処理することを許容する。本発明は、複雑なルールを用いて、これを２つの別個のルールに分割する。これは、ルールが適正なＲＥＴＥネットワーク・フォーマットで表現することができるように行われる。また、ＯＲ節点が多くのレベルにおいて起生し得ることに注意すべきである。論理和モジュール６０４は、全てのＯＲ節点が構文解析ツリーの先頭に押しやられるまでレベル単位に動作する。
【０１１１】この点において、本発明は、与えられたルールに対する抽象構文ツリーをＡＮＤ節点およびテスト節点のみが存在するように変換する。ＮＯＴ節点はないが、これはこれら節点が否定モジュール６０２により排除される故である。ＯＲ節点がないが、これはこれらが論理和モジュール６０４によって排除される故である。
【０１１２】次に、構成モジュール６０６が、ルールを構成してＲＥＴＥネットワークに構築するタスクを行う。図１８は、構成モジュール６０６の高レベルなアーキテクチャのブロック図を示す。構成モジュール６０６は、多重入力フロー・リスト・モジュール１８０２、ａｌｐｈａ節点モジュール１８０４、ダングリングａｌｐｈａルーチン１８０６、および多重入力節点モジュール１８０８を含む。
【０１１３】図１９及び図２０は、図１８の構成モジュール６０６の高レベルの動作を示すブロック図である。
【０１１４】まず図１９において、動作ブロック１９０２により示される如きＲＥＴＥネットワークの構築における最初のステップは、各テスト節点におけるシンボル・リストを調べて、全ての純粋に負の多重入力テストに対するフロー・リスト・エントリを形成することを含む。動作ブロック１９０４により示される如く、ＲＥＴＥネットワークの構築の２番目のステップは、残る各テスト節点におけるシンボル・リストを調べて、他の全ての多重入力テストに対するフロー・リスト・エントリを形成することを含む。また図１９により示される如く、動作ブロック１９０２および１９０４により記述される動作ステップは多重入力フロー・リスト・モジュール１８０２により行われる。
【０１１５】動作ブロック１９０６により示される如く、ＲＥＴＥネットワークの構築における次のステップは、テスト節点を再び調べて全ての単入力テスト（ａｌｐｈａテスト）に対するフロー・リスト・エントリおよびＲＥＴＥ節点を構成することを含む。以下に示し述べるように、ステップ１９０６はａｌｐｈａ節点モジュール１８０４により行われる。
【０１１６】次に図２０において、動作ブロック１９１０により示される如きＲＥＴＥネットワークの構築における次のステップは、正のフロー・リストを調べてダングリングａｌｐｈａテストを再整列することを含む。動作ブロック１９１２により示されるように、ＲＥＴＥネットワークの構築における次のステップは、ダングリングａｌｐｈａテストを右側のその隣接するテストへ接続することを含む。図２０により示されるように、動作ブロック１９１０および１９１２により記述される２つのステップは、ダングリングａｌｐｈａモジュール１８０６により行われる。
【０１１７】動作ブロック１９１４により示されるように、ＲＥＴＥネットワークの構築における次のステップは、多重入力テストを調べて、全ての純粋に負のテストに対する負のフロー・リストへｂｅｔａテストを取付けることを含む。このステップは、多重入力節点モジュール１８０８により行われる。
【０１１８】動作ブロック１９１６により示されるように、１つのルールに対してＲＥＴＥネットワークを構築する際の最後のステップは、各テスト節点を逐次再び調べることである。
【０１１９】先に述べた動作は、与えられたテスト節点のシンボル・リストにおける変数が正に定量化され、負に定量化され、あるいは混成されるかに従って行われる。特に、もし検査中のテストが正に定量化されたテストであれば、ＢＥＴＡテストが構成される。もし検査中のテストが混成量化であるならば、ＢＥＴＡ ＮＯＴテストが構成される。もし考察中のテストが単入力の負のテストであれば、純粋に負のテストが、ＡＮＤ ＮＯＴ節点でＲＥＴＥネットワークの正の側に接続される。上記のステップもまた、多重入力節点モジュール１８０８によって行われる。
【０１２０】この時行われる全ての接続は、フロー・リストの問題の変数の左側に現れる全ての変数もまた包含されるように構成される。このステップは、さもなければ、見過ごすおそれがあるｂｅｔａ節点を接続する働きがある。
【０１２１】ここで、フロー・リストの一般的概念について論述する。フロー・リストは、本発明の重要な特徴である。フロー・リストは、ＲＥＴＥネットワークが構築されつつある時更新される作業用主メモリ２０４（図２R>２参照）の専用ブロックである。このフロー・リストはまた、与えられたルールでテストされるオブジェクトの完全なセットを含む。更に明らかになるように、フロー・リストは、緻密なＲＥＴＥネットワークを構築する便利な方法を提供する。その理由は、与えられたテストと対応する全てのオブジェクトが相互に隣接することである。
【０１２２】望ましい実施態様において、本発明は２つのフロー・リスト、即ち正のフロー・リストと負のフロー・リストを使用する。この正のフロー・リストは、１つのルールでテストされる全ての特有な正で定量化されるオブジェクトの順序を付したリストである。負のフロー・リストは、１つのルールでテストされる全ての負で定量化された変数の順序を付したリストである。本文において明らかになるように、（１つは正の変数、１つは負の変数に対する）２つのフロー・リストを使用することで、ＲＥＴＥネットワークの構築を著しく容易にする。
【０１２３】構成モジュール６０６の各サブコンポーネント（多重入力フロー・リスト・モジュール１８０２、ａｌｐｈａ節点モジュール１８０４、ダングリングａｌｐｈａモジュール１８０６、多重入力節点モジュール１８０８）について、更に詳細に記述する。
【０１２４】動作において、また再び図１８において、多重入力フロー・リスト・モジュール１８０２は、ＣＰＵ２０２に対して各シンボル・リストを調べて、テストが２つ以上のオブジェクトを含むかどうかを判定するように指令する。多重入力フロー・リスト・モジュール１８０２は、このようなオブジェクトの検出と同時に、ＣＰＵ２０２に対してオブジェクトをフロー・リストへ加えることを指令する。付加されるオブジェクトに加えて、多重入力フロー・リスト・モジュール１８０２は、各オブジェクトがルールに現れる相対順位をフロー・リストに記憶する。
【０１２５】多重入力フロー・リスト・モジュール１８０２は、一般に、２入力テストに含まれるこれらオブジェクトを見出すための手段を含む。多重入力フロー・リスト・モジュール１８０２は更に、これらのオブジェクトを正のフロー・リストまたは負のフロー・リストのいずれかに記憶するための手段を含む。
【０１２６】望ましい実施態様においては、多重入力フロー・リスト・モジュール１８０２は与えられるルールについて抽象構文ツリーを調べ、負に定量化された多重入力テストを最初に探す。多重入力フロー・リスト・モジュール１８０２は、次に他の全ての多重入力テストについて構文ツリーを再び調べる。
【０１２７】上記の諸操作を行うためのモジュールのアーキテクチャが図２１に示される。図示の如く、多重入力フロー・リスト・モジュール１８０２は、純粋に負のフロー・リスト・モジュール２００２、純粋に正のフロー・リスト・モジュール２００４および混成量化モジュール２００６を含む。
【０１２８】図２２〜図２３は、多重入力フロー・リスト・モジュール１８０２および図２１のその対応する構造的サブコンポーネント、即ち、純粋に負のフロー・リスト・モジュール２００２、純粋に正のフロー・リスト・モジュール２００４および混成量化モジュール２００６の動作を詳細に示す高レベルのフローチャートである。特に、図２２は、純粋に負のフロー・リスト・モジュール２００２の動作を示し、図２３はモジュール２００４および２００６の動作を示す。
【０１２９】まず図２２において、動作ブロック２１０２により示されるように、純粋に負のフロー・リスト・モジュール２００２は最初に（各テスト毎にシンボル・リストを調べることにより）ＣＰＵ２０２に対して与えられたルールに対する抽象構文ツリーにおける次のテストを調べるように指令する。各テストが１つのシンボル・リストを持つことを想起しよう。最初の実行サイクルにおいて、抽象構文ツリーにおける次のテストがユーザにより書かれた最初のテストとなる。判断ブロック２１０４により示されるように、純粋に負のフロー・リスト・モジュール２００２はＣＰＵ２０２に対して考察中のテストが２つ以上の異なるオブジェクトを参照するかどうかを判定するように指令する。同じオブジェクトの２つの属性が同じであるかどうかをテストするテストが２つの異なるオブジェクトと見做されることがないことを理解すべきである。
【０１３０】もし唯１つのオブジェクトがテストにおいて参照されるならば、制御は判断ブロック２１０４により動作ブロック２１０２へ戻され（ＮＯループ参照）、ここでＣＰＵ２０２が抽象構文ツリーにおける次のテストを調べるように指令される。しかし、もし２つ以上のオブジェクトの異なるオブジェクトが存在するならば、制御は判断ブロック２１０４により判断ブロック２１０６へ送られる。
【０１３１】判断ブロック２１０６により示されるように、純粋に負のフロー・リスト・モジュール２００２がＣＰＵ２０２に対して、テストが純粋に負に定量化されるか、即ちテストにおいて参照される各オブジェクトが負に定量化されるかを判定するように指令する。もし全てのオブジェクトが負に定量化されるのでないならば、制御は動作ブロック２１０２へ戻り、ここでＣＰＵ２０２が抽象構文ツリーにおける次のテストを調べるように指令される。しかし、もしテストにおける各オブジェクトが負に定量化されるならば、判断ブロック２１０６が制御を動作ブロック２１０８へ送る。
【０１３２】動作ブロック２１０８により示されるように、純粋に負のフロー・リスト・モジュール２００２がＣＰＵ２０２に対してオブジェクトを負のフロー・リストへ加えるように指令する。オブジェクトは、テスト内のそれらのシーケンス順で付加される。その後、制御は判断ブロック２１１０へ進む。
【０１３３】判断ブロック２１１０により示されるように、純粋に負のフロー・リスト・モジュール２００２は抽象構文ツリーにおける最後のテスト節点かをテストする。もしこれが最後のテストでなければ、上記のサイクルが再開するとき、制御はＮＯループにより動作ブロック２１０２へ戻される。しかし、もし最後のテスト節点であるならば、制御は判断ブロック２１１０により図２３R>３の動作ブロック２１１２へ（２１５０を介して）送られる。
【０１３４】動作ブロック２１１２により示されるように、純粋に正のフロー・リスト・モジュール２００４がＣＰＵ２０２に対して、同じ抽象構文ツリーを再び調べるように指令する。このサイクルにおいては、抽象構文ツリーにおける次のテストは同様にユーザにより指定された最初のテストとなる。
【０１３５】判断ブロック２１１４により示されるように、純粋に正のフロー・リスト・モジュール２００４がＣＰＵ２０２に対して考察中のテストが２つ以上の異なるオブジェクトを参照するかどうかを判定するように指令する。もし唯１つのオブジェクトがこのテストにおいて参照されるならば、制御は動作ブロック２１１２へ戻され、ここでＣＰＵ２０２が抽象構文ツリーの次のテストを調べるように指令される。しかし、もし２つ以上のオブジェクトの異なるオブジェクトが存在するならば、制御は判断ブロック２１１４により判断ブロック２１１６へ送られる。
【０１３６】判断ブロック２１１６により示されるように、純粋に正のフロー・リスト・モジュール２００４がＣＰＵ２０２に対してテストが純粋に正に定量化されるかどうか、即ちテストにおいて参照された各オブジェクトが正に定量化されるかどうかを判定するように指令する。もしオブジェクトの全てが正に定量化されなければ、制御はＮＯループを介してテスト２１２６へ戻り、ここでＣＰＵ２０２はテストが混成量化を包含するかどうかを判定するように指令される。即ち、このＣＰＵは、テストにおいて参照されたあるオブジェクトが他のオブジェクトが負に定量化される一方、正に定量化されるかどうかを判定する。もしそうであれば、制御は動作ブロック２１２８へ進む。
【０１３７】動作ブロック２１２８により示されるように、混成量化モジュール２００６はＣＰＵ２０２に対してオブジェクトを負および正のフロー・リストへ加えるように指令する。オブジェクトは、テスト内に現れる順序で加えられる。その後、制御は判断ブロック２１２０へ進む。
【０１３８】もしテストが混成量化を含まなければ、制御はＮＯループを介してテスト２１１６へ戻り、ここでＣＰＵ２０２が抽象構文ツリーにおける次のテストを調べるように指令される。しかし、テストにおける各オブジェクトが正に定量化されるならば、制御は判断ブロック２１１６により動作ブロック２１１８へ送られる。
【０１３９】動作ブロック２１１８により示されるように、純粋に正のフロー・リスト・モジュール２００４はＣＰＵ２０２に対してオブジェクトを正のフロー・リストへ加えるように指令する。オブジェクトは、テスト内のそのシーケンス順に加えられる。その後、制御は動作ブロック２１１８により判断ブロック２１２０へ送られる。
【０１４０】判断ブロック２１２０により示されるように、フロー・リスト・モジュール２００４はＣＰＵ２０２に対して、問題のテストが抽象構文ツリーにおける最後のテストであるかどうかを判定するように指令する。もしこのテストが抽象構文ツリーにおける最後のテストでなければ、制御はＮＯループを介して動作ブロック２１１２へ戻される。しかし、もし問題のテストが抽象構文ツリーにおける最後のテストであるならば、制御は判断ブロック２１２０により動作ブロック２１３４へ送られ、ここで多重入力節点モジュール１８０８の動作が終了される。
【０１４１】多重入力フロー・リスト・モジュール１８０２が純粋に正、純粋に負、および混成の定量化テストを個々に処理することにより同様に実現するできることに注意すべきである。即ち、多重入力フロー・リスト・モジュール１８０２が、３つの個別のステップ、即ち、(１)純粋に正に定量化されるテスト、(２)純粋に負に定量化されるテスト、および(３)混成量化テストにおいて実現することができる。
【０１４２】しかし、望ましい実施態様においては、多重入力フロー・リスト・モジュールは２つの個々のステップ、即ち、(１)純粋に負に定量化されるテスト、および(２)他の全ての多重入力テストにおいて処理される。このような実施態様は、負に定量化されるテストの意味論的な完全性を更に充分に保護する。本実施態様はまた、テストのユーザの最初の順序がＲＥＴＥネットワークの最終的な状態において考慮できる程度を最大限にするものである。
【０１４３】図２４は、サンプル・ルール（図示せず）に対する抽象構文ツリー２２００を示している。プロダクション節点２２０２およびＡＮＤ節点２２０４が示される。更に、テスト節点２２０６、２２０８、２２１０、２２１２、２２１４および２２１６が示される。更にまた、それぞれが上記のテスト節点２２０６〜２２１６の各々に対応するシンボル・リスト２２１８、２２１９、２２２０、２２２２、２２２４および２２２６が示される。
【０１４４】シンボル・リスト２２１８は、テスト節点２２０６が負に定量化されるオブジェクトＡについてのテストを有することを示す。シンボル・リスト２２１９は、テスト節点２２０８が正に定量化されるオブジェクトＢについてのテストを有することを示す。シンボル・リスト２２２０は、テスト節点２２１０が純粋に正に定量化されるオブジェクトＣおよびＤについてのテストを有することを示す。
【０１４５】シンボル・リスト２２２２は、テスト節点２２１２がオブジェクトＥおよびＦについて参照するテストを有することを示す。シンボル・リスト２２２２は更に、オブジェクトＦが負に定量化されたオブジェクトであることを示す。このように、テスト節点２２１２により示されるテストは混成量化テストである。
【０１４６】シンボル・リスト２２２４は、テスト節点２２１４がオブジェクトＧおよびＨを参照するテストを有することを示す。シンボル・リスト２２２４は更に、オブジェクトＧおよびＨが負に定量化されることを示す。このように、テスト節点２２１４により示されるテストは、純粋に負に定量化される。シンボル・リスト２２２６は、テスト節点２２１６が正に定量化されるオブジェクトＩについてのテストを有することを示す。
【０１４７】本発明にとってＲＥＴＥネットワークを構築するために別の情報が不要であることに注意すべきである。
【０１４８】次に、構成モジュール６０６（図６）の動作について、図２２の抽象構文ツリー（ルール）に対するＲＥＴＥネットワークの構成を使用して更に説明する。
【０１４９】再び図２４において、また先に述べたように、構成モジュール６０６の最初の動作は、多重入力フロー・リスト・モジュール１８０２（図１８）の動作のそれである。多重入力フロー・リスト・モジュール１８０２の動作については、図２２〜図２３に関して詳細に述べた。構成モジュール６０６の第２の動作は、ａｌｐｈａ節点モジュール１８０４のそれである。第３の動作は、ダングリングａｌｐｈａモジュール１８０６のそれである。構成モジュール６０６の最後の動作は、多重入力節点モジュール１８０８のそれである。構成モジュール６０６のこれらサブモジュール１８０２、１８０４、１８０６および１８０８の各々について、図２４の抽象構文ツリーに対するＲＥＴＥネットワークを構築する環境において説明する。
【０１５０】図２５は、ブロック図フォーマットにおいて、正のフロー・リスト・ブロック２３１４および負のフロー・リスト・ブロック２３１６を示す。正のフロー・リスト・ブロック２３１４および負のフロー・リスト・ブロック２３１６は、メモリ装置２０４（図２）内の記憶場所である。
【０１５１】図２２に関して述べたように、多重入力フロー・リスト・モジュール１８０２の負のフロー・リスト・モジュール２１０２は、純粋に負のオブジェクトに対してフロー・リスト・エントリを最初に構成する。図２４２４に示されるルールにおいては、シンボル・リスト２２２４のオブジェクトＧおよびＨが多重入力テストの一部である純粋に負に定量化されたオブジェクトを示す。このように、シンボル・リスト２２２４のオブジェクトＧおよびＨは、フロー・リスト・エントリ２３０２および２３０４としてそれぞれ負のフロー・リスト・ブロック２３１６へ挿入される。他の純粋に負の２つの入力オブジェクトは存在しない。
【０１５２】図２３に関して述べたように、純粋に正のモジュール２００４はその後、ＣＰＵ２０２に対して図２４２４の全ての多重入力テストを調べるように指令する。純粋に正のフロー・リスト・モジュール２００４は、純粋に正のテストからのオブジェクトを正のフロー・リスト・ブロック２３１４へ加える。図２４に示されるように、シンボル・リスト２２２０のオブジェクトは、純粋に正の２つのオブジェクトであり、このため、フロー・リスト・エントリ２３０６および２３０８として正のフロー・リスト・ブロック２３１４にそれぞれ挿入される。図２４のシンボル・リストには、他の純粋に正の２つの入力オブジェクトは存在しない。
【０１５３】また図２３に関して述べたように、混成量化モジュール２００６がＣＰＵ２０２に対して混成量化テストの負のオブジェクトを負のフロー・リスト・ブロック２３１６へ加えるように指令する。シンボル・リスト２２２２のオブジェクトＦは、混成量化テストの負のオブジェクトであり、このため負のフロー・リスト・ブロック２３１６にフローリスト・エントリ点２３１０として挿入される。他の負の混成量化オブジェクトは存在しない。
【０１５４】その後、混成量化モジュール２００６が、混成量化テストの正のオブジェクトを正のフロー・リスト・ブロック２３１４へ加える。図２４に示されるように、シンボル・リスト２２２２のオブジェクトＥは、混成量化テストと対応する正の変数である。シンボル・リスト２２２２のオブジェクトＥは、フローリスト・エントリ２３１２として正のフロー・リスト・ブロック２３１４に挿入される。多重入力フロー・リスト・モジュール１８０２の動作のみが、比較的厳密な最適化されたＲＥＴＥネットワークを保証する。ユーザにより入力される多重入力テスト（ｂｅｔａテスト）の順序がＲＥＴＥネットワークの相対的な状態を決定することを理解すべきである。従って、本発明は、多重入力テストに関するユーザの順序を考慮する。
【０１５５】次に、ａｌｐｈａ節点モジュール１８０４の動作について正のフロー・リスト・ブロック２３１４および負のフロー・リスト・ブロック２３１６を修正する環境において記述する。図２６は、図２５の正のフロー・リスト・ブロック２３１４および負のフロー・リスト・ブロック２３１６の修正を示している。
【０１５６】図２６において、ａｌｐｈａ節点モジュール１８０４が多重入力フロー・リスト・モジュール１８０２と同様に働く。多重入力フロー・リスト・モジュール１８０２と同様に、ａｌｐｈａ節点モジュール１８０４がＣＰＵ２０２に対して図２４の抽象構文ツリーを調べてテスト節点を探すように指令する。
【０１５７】しかし、ａｌｐｈａ節点モジュール１８０４は、多重入力テストとは対照的に単入力テストにおいて使用されるオブジェクトを処理する。換言すれば、ａｌｐｈａ節点モジュール１８０４は、１つのオブジェクトを持つテスト節点を見出す。これらのテスト節点が最終的にａｌｐｈａテストとなる。
【０１５８】もし既に多重入力フロー・リスト・モジュール１８０２により構成されていなかったならば、これらの一入力テストに対するフローリスト・エントリは正のフロー・リスト・ブロック２３１４および（または）負のフロー・リスト・ブロック２３１６に加えられる（同じオブジェクトが１入力テストおよび２入力テストの双方にあり得、これが２入力テストの一部でもあるため、このオブジェクトに対するａｌｐｈａテストは非ダングリングａｌｐｈａテストと呼ばれることに注意）。従って、ａｌｐｈａ節点モジュール１８０４は図２４のシンボル・リストを調べて、負に定量化されるかどうかに拘わらず、フローリスト・エントリをこれが見出す順序で構成する。
【０１５９】多重入力フロー・リスト・モジュール１８０２とは対照的に、１つの入力オブジェクトをフロー・リストに入力する時、ａｌｐｈａ節点モジュール１８０４はＣＰＵ２０２に対してＲＥＴＥ ａｌｐｈａ節点を即時構成するように指令する。これは、本発明により実際に構成された最初のＲＥＴＥ節点である。
【０１６０】もし同じオブジェクトが多くの１入力テストを有するならば、多重ａｌｐｈａ節点は一方が他方の下に接続される。ａｌｐｈａ節点が最初に構成されるが、これは関連する任意のａｌｐｈａ節点の接続前にｂｅｔａ節点を接続することが非効率的であるためである。
【０１６１】図２６に示されるように、ａｌｐｈａ節点モジュール１８０４は、正のフロー・リスト・ブロック２３１４および負のフロー・リスト・ブロック２３１６を「更新」している。図示の如く、図２のシンボル・リスト２２１８の負に定量化されたオブジェクトＡが、負のフロー・リスト・ブロック２３１６におけるフローリスト・エントリ２４０２として加えられている。同様に、シンボル・リスト２２０８および２２１６のオブジェクトＢおよびＩは、それぞれ正のフロー・リスト・ブロック２３１４におけるフローリスト・エントリ点２４０４および２４０６として加えられている。図２６に更に示されるように、ａｌｐｈａ節点モジュール１８０４はまたａｌｐｈａ節点２４０８、２４１０、２４１２をそれぞれ構成している。
【０１６２】前記の節点は、ＲＥＴＥネットワークに対して構成された最初の節点である。本発明がＲＥＴＥネットワークを正のフロー・リスト・ブロック２３１４および負のフロー・リスト・ブロック２３１６から構成することを理解すべきである。このようなデータ構造が、ＲＥＴＥネットワークの構築の便利な方法を提供する。
【０１６３】この点において、本発明の多重入力フロー・リスト・モジュール１８０２およびａｌｐｈａ節点モジュール１８０４が、与えられたルールにおいて使用される各オブジェクトを識別している。更に、多重入力フロー・リスト・モジュール１８０２およびａｌｐｈａ節点モジュール１８０４が、これらのオブジェクトをフローリスト・エントリ点として正または負のフロー・リストへ入力した。
【０１６４】次に、図１８のダングリングａｌｐｈａモジュール１８０６の動作について、図２６の正のフロー・リスト２３１４および負のフロー・リスト２３１６の修正の環境において論議する。
【０１６５】一般に、ダングリングａｌｐｈａモジュール１８０６が、ダングリングａｌｐｈａ節点がユーザにより生成された順序で配置されるようにＣＰＵ２０２に対して正のフロー・リスト・ブロック２３１４を並替えることを指令する。ダングリングａｌｐｈａテストは、要素間テストにより使用されないオブジェクトについての要素内テストである。換言すれば、これはこのオブジェクトが多重入力テストにおいて参照されない場合のオブジェクトについての単一テストである。本発明はまた、ユーザにより全ての以降のテストを禁止するように指定された手段としてダングリングａｌｐｈａテストとも呼ばれる。換言すれば、本発明は、ユーザが専らダングリングａｌｐｈａテストの設置によりＲＥＴＥネットワークのサブセクションを選択的に使用可能／使用不能にすることを許容する。ダングリングａｌｐｈａテストは、可能な限り優先権を与えられる。
【０１６６】図２７に示されるように、ダングリングａｌｐｈａモジュール１８０６は、ａｌｐｈａ並替えモジュール２５０２およびａｌｐｈａ接続モジュール２５０４を含む。ａｌｐｈａ並替えモジュール２５０２は、ユーザが最初に置いた場所へダングリングａｌｐｈａテストが置替えられるように、正のフロー・リスト２３１４を修正する。しかし、ａｌｐｈａ並替えモジュール２５０２が正のフロー・リスト・ブロック２３１４のエントリのみを修正することに注意すべきである。換言すれば、ａｌｐｈａ並替えモジュール２５０２は負のフローリスト・エントリは修正しない。その理由は、負に定量化されたテストの意味論的意義を保存することである。
【０１６７】図２８に示されるように、ａｌｐｈａ並替えモジュール２５０２の動作が、図２６の正のフロー・リスト・ブロック２３１４を修正した。図２８から判るように、シンボル・リスト２２１９のオブジェクトＢがフローリスト・エントリ点２４０４から２３０６へ移されている。シンボル・リスト２２２６のオブジェクトＩは、そのテスト場所（番号６）がこれが既にその適正な場所にあることを示す故に、置替えられることがない。
【０１６８】ａｌｐｈａ並替えモジュール２５０２は、ここで述べるアルゴリズムを用いて上記の再構成を実施する。このアルゴリズムにおいては、ａｌｐｈａ並替えモジュール２５０２は各フローリスト・エントリと関連する番号を参照する。抽象構文ツリーにより最初に構文解析モジュール３０２がルール全体にオブジェクト場所を格納することを想起されたい。ａｌｐｈａ並替えモジュール２５０２は、左側から始めて各フローリスト・エントリ・テスト番号を持つダングリングａｌｐｈａテストを比較してフロー・リストにわたって反復する。この反復がダングリングａｌｐｈａ節点番号が左側のそれより大きくかつ右側のそれより小さいことを判定する時、ＣＰＵ２０２はこの場所にダングリングａｌｐｈａを挿入することを知る。次いで、全ての以降の変数の場所へ当たる。
【０１６９】次に、図２７のａｌｐｈａ接続モジュール２５０４について論述する。ａｌｐｈａ接続モジュール２５０４は、ＣＰＵ２０２に対してダングリングａｌｐｈａを隣接するフローリスト・エントリ点と接続するように指令する。この操作はまた、図２８に示される。図示の如く、ダングリングａｌｐｈａ節点２６１０は、ＡＮＤ節点２６０６によりフローリスト・エントリ点２３０６と接続されている。これは、ダングリングａｌｐｈａ節点２６１０がＲＥＴＥネットワークの残りと接続されるように行われる。フローリスト・エントリ点２４０６（オブジェクトＩ）およびその関連するａｌｐｈａ節点２４１２がＡＮＤ節点と接続されなかったことに注意すべきである。この理由は、フローリスト・エントリ２４０６が正のフロー・リスト・ブロック２３１４における最も右に離れたエントリであるためである。図には示さないが、２つの隣接するダングリングａｌｐｈａ節点が相互に接続され、次いで次の右側に隣接するフローリスト・エントリと接続されることを理解すべきである。
【０１７０】ダングリングａｌｐｈａモジュール１８０６は本発明の顕著な特徴であり、これがパワーユーザがＲＥＴＥネットワークのトポロジーに対する制御を維持することを可能にする。
【０１７１】一般に、ＢＥＴＡ節点およびＢＥＴＡ ＮＯＴ節点がＲＥＴＥネットワークのトポロジーを制御する。多重入力オブジェクトに対するフロー・リストを最初に、次いでその中にダングリングａｌｐｈａを再び挿入する理由は、非ダングリングａｌｐｈａテストが与えられたルールに存在し得る故である。非ダングリングａｌｐｈａはＢＥＴＡ節点により駆動されるが、これはこれら節点が関連する２入力テストに対する入力として要求される故である。先に述べたように、本発明は、緊密なＲＥＴＥネットワークを取得するため全てのＢＥＴＡ参照オブジェクトを一体化する。しかし、このような特徴に打ち勝つため、本発明は、ダングリングａｌｐｈａテストのユーザのシーケンスを考慮する。
【０１７２】次に構成モジュール６０６の多重入力節点モジュール１８０８について詳細に論述する。先に述べたように、多重入力節点モジュール１８０８の動作はＲＥＴＥネットワークの構築における最終的な動作を表わす。多重入力節点モジュール１８０８の動作は２つのステップからなる。
【０１７３】第１のステップは、図２０の動作ブロック１９１４において前に示したように、シンボル・リストを逐次調べて純粋に負のＢＥＴＡテスト（２つ以上のオブジェクトを含むテスト）のみを見出すことである。もし純粋に負のＢＥＴＡテストが見出されると、負のフロー・リストについてテストされたオブジェクトに対してＢＥＴＡテストが構成される。
【０１７４】第２のステップは、前に図１９の動作ブロック１９０４に示したように、（純粋に負の２入力テストのみが問題となる第１のステップとは対照的に）シンボル・リストにおける各テストの順次の再検査のステップである。シンボル・リストに与えられたテストが正に定量化された、負に定量化された、あるいは混成量化されたかに従って、ある動作が行われる。
【０１７５】一般に、もし検査中のテストが正に定量化された多重入力テストであれば、ＢＥＴＡテストが構成される。もし検査中のテストが混成量化されたテストであれば、ＢＥＴＡ ＮＯＴテストが構成される。もし問題のテストが純粋に負のテスト（即ち、負のフロー・リストから外されるａｌｐｈａ節点あるいはｂｅｔａ節点）であれば、純粋に負のテストがＡＮＤ ＮＯＴ節点でＲＥＴＥネットワークの正の側に接続される。
【０１７６】多重入力節点モジュール１８０８の上記の動作は、図２４に示したルールに対するＲＥＴＥネットワークの継続的構築を参照すれば更によく理解される。図２８において、ダングリングａｌｐｈａモジュール１８０６がユーザにより指定される如きその元の場所に対するダングリングａｌｐｈａテスト（オブジェクトＢのテスト）を認識して、これをＡＮＤ節点（ＡＮＤ節点２６０６）でＲＥＴＥネットワークに接続したことを想起されたい。
【０１７７】先に述べたように、多重入力節点モジュール１８０８の動作における最初のステップは、純粋に負の２入力テスト（２つ以上のオブジェクトに対するテスト）に対するＢＥＴＡテストの構成のステップである。動作においては、多重入力節点モジュール１８０８は、ＣＰＵ２０２に対して図２４のシンボル・リストを調べて全ての純粋に負の２入力テストを見出すように指令する。図２５に示した事例においては、ＣＰＵ２０２が唯１つのこのようなテスト、即ち、オブジェクトＧおよびＨを参照するテスト２２１４が存在することを判定する。図２９から判るように、多重入力節点モジュール１８０８は、ＣＰＵ２０２に対してＢＥＴＡテスト節点２７０２を介してオブジェクトＧおよびＨを接続するように指令する。他の純粋に負の２入力テストは存在しない。このため、上記の操作後のＲＥＴＥネットワークの状態は、図２９に示される如くである。
【０１７８】次に、多重入力節点モジュール１８０８の第２のステップについて、図２４のルールに対するＲＥＴＥネットワークの構築に関して記述する。先に述べたように、多重入力節点モジュール１８０８は、ＣＰＵ２０２に対して各テストを再び調べて、テストの種類に応じてこのテストについてある動作を行うように指令する。
【０１７９】一例において、図２４のシンボル・リストを逐次調べることは、テスト２２０６（オブジェクトＡに対するテスト）が検査中の最初のテストであることを示す。テスト２２０６は、オブジェクトＡに対する純粋に負のテストである。図３０に示されるように、この種のテストに応答して、多重入力節点モジュール１８０８はＣＰＵ２０２に対してオブジェクトＡ（負のフロー・リストに見出される）をＡＮＤ ＮＯＴ節点で正のフロー・リスト・ブロック２３１４に接続するように指令する。
【０１８０】ルールにおける最初のテスト（テスト２２０６）の動作を完了した後、多重入力節点モジュール１８０８はＣＰＵに対してこのルールの次のテストを調べるように指令する。図２４のルールの次のテストは、テスト２２０８のテスト（オブジェクトＢに対するテスト）である。テスト２２０８を調べると、テスト２２０８がオブジェクトＢに対する純粋に正の１入力テストであることが示される。このような場合、多重入力節点モジュール１８０８は通常、ＣＰＵ２０２に対してオブジェクトＢをＡＮＤ節点を介して（全てのａｌｐｈａ節点が前にａｌｐｈａ節点モジュール１８０４により構成されたことを想起されたい）ＲＥＴＥネットワークと接続するように指令する。しかし、本例においては、オブジェクトに対するａｌｐｈａテストが既に節点２６０６を介してＲＥＴＥネットワークに接続されている。従って、テスト２２０８に対して動作を行う必要はない。
【０１８１】その後、多重入力節点モジュール１８０８はもう一度ＣＰＵ２０２に対して図２４のルールにおける次のテストを調べるように指令する。図２４のルールにおけるこの次のテストは、テスト２２１０（オブジェクトＣおよびＤに対するテスト）のそれである。テスト２２１０を調べると、テスト２２１０がオブジェクトＣおよびＤに対する純粋に正の２入力テストであることが示される。図３１に示されるように、この種のテストに応答して、多重入力節点モジュール１８０８はＣＰＵ２０２に対してオブジェクトＣおよびＤをＢＥＴＡテスト節点２９０２を介して接続するように指令する。
【０１８２】その後、多重入力節点モジュール１８０８はもう一度ＣＰＵ２０２に対して図２４のルールにおける次のテストを調べるように指令する。図２４のルールにおける次のテストは、テスト２２１２（オブジェクトＥおよびＦに対するテスト）のそれである。テスト２２１２を調べると、テスト２２１２は、オブジェクトＥが正に定量化され、オブジェクトＦが負に定量化されたものである混成量化されたテストであることが示される。
【０１８３】図３２に示されるように、この種のテストに応答して、多重入力節点モジュール１８０８はＣＰＵ２０２に対してオブジェクトＥおよびＦをＢＥＴＡ ＮＯＴ節点３００４で接続するように指令する。しかし、図２４のルールにおいてオブジェクトＥが最初にＲＥＴＥネットワークと接続されねばならないことを知るべきである。従って、この種の状況においては、多重入力節点モジュール１８０８は最初にＣＰＵ２０２に対してオブジェクトＥをＡＮＤ節点３００２によりＲＥＴＥネットワークに接続することを指令する。一般に、多重入力節点モジュール１８０８は最初にフロー・リストにおける最も左側のオブジェクトが実際に問題となるテストを構成する前にＲＥＴＥネットワークに接続されるかどうかを判定する。
【０１８４】その後、多重入力節点モジュール１８０８はもう一度ＣＰＵ２０２に対して図２４のルールにおける次のテストを調べるように指令する。図２４のルールにおける次のテストは、テスト２２１４（オブジェクトＧおよびＨに対するテスト）のそれである。テスト２２１４を調べると、テスト２２１４が純粋に負に定量化された２入力テストであることが示される。図３３に示されるように、この種のテストに応答して、多重入力節点モジュール１８０８はＣＰＵ２０２に対してＢＥＴＡテスト節点２７０２をＡＮＤ ＮＯＴ節点３１０２を介してＲＥＴＥネットワークに接続するように指令する。オブジェクトＧおよびＨに対するＢＥＴＡテストが多重入力節点モジュール１８０８の最初の動作により構成される最初のテストであったことを想起されたい。多重入力節点モジュール１８０８の第２の動作においては、ＣＰＵ２０２に対してＢＥＴＡテスト２７０２をＲＥＴＥネットワークの残部に接続するように指令するだけである。
【０１８５】その後、多重入力節点モジュール１８０８はもう一度ＣＰＵ２０２に対してルールにおける次のテストを調べるように指令する。図２４のルールにおける次のテストは、テスト２２１６（オブジェクトＩに対する正に定量化されたテスト）である。テスト２２１６はまた、図２４のルールにおける最後のテストでもある。テスト２２１４を調べると、テスト２２１４はオブジェクトＩに対する純粋に正の１入力テストであることが示される。この場合、多重入力節点モジュール１８０８はＣＰＵ２０２に対してオブジェクトＢをＡＮＤ節点３２０２を介して接続するように指令する（ａｌｐｈａ節点２４１０が前にａｌｐｈａ節点モジュール１８０４により構成されたことを想起されたい）。
【０１８６】その後、多重入力節点モジュール１８０８はもう一度ＣＰＵ２０２に対して図２４のルールにおける次の入力テストを調べるように指令する。しかし、この時ＣＰＵ２０２は、多重入力節点モジュール１８０８に対して、これ以上のテストがルールに存在しないことを指令する。これに応答して、多重入力節点モジュール１８０８はＣＰＵ２０２に対してＡＮＤ節点３２０２をプロダクション節点２２０２に接続するよう指令する。
【０１８７】プロダクション節点２２０２が図２４のプロダクション節点２２０２であることに注意すべきである。換言すれば、ＲＥＴＥネットワークは、プロダクション節点２２０２を「放す」のである。更に、先に述べたように、プロダクション節点２２０２は、図２４のルールに関する全ての情報に対する中心の場所である。この種のデータ構造は、与えられたルールに対するＲＥＴＥネットワークを構成して構築する便利な方法である。
【０１８８】次に、暗黙条件モジュール６０８について論述する。暗黙条件モジュール６０８は、あるルールのＲＨＳの全ての暗黙条件が知識ベースに実際に存在することを保証するようにルール・セットに対して作用する。暗黙条件モジュール６０８は、事物が未決定の点である衝突するセットに落込むことを許さない。
【０１８９】図３６に示されるように、暗黙条件モジュール６０８は、オブジェクト・リスト・モジュール３４０２と、検証モジュール３４０４と、挿入モジュール３４０６とを含む。
【０１９０】一般に、暗黙条件モジュール６０８は、各ルールについて動作してあるルールのＲＨＳの全ての暗黙条件が実際に知識ベースに存在することを保証する。
【０１９１】検証モジュール３４０４は、ＣＰＵ２０２にオブジェクト・リストについて最初に反復してオブジェクトがルールのＬＨＳに存在するかどうかを判定するように指令する。もしオブジェクトがルールのＬＨＳに存在しなければ、検証モジュール３４０４はＣＰＵ２０２に対してＲＨＳにおけるオブジェクトの存在がオブジェクトの新しい生成によるものかどうかを判定するように指令する。オブジェクトの新しい生成は、ルールのＬＨＳの暗黙条件ではあり得ないことを意味する。
【０１９３】もし暗黙条件が見出されると、挿入モジュール３４０６が実行されて、ＣＰＵ２０２に対してオブジェクトをルールに対するＲＥＴＥネットワークに挿入することを指令する。従って、挿入モジュール３４０６は、暗黙条件をルールのＬＨＳに加える。
【０１９４】本発明の詳細な記述におけるこれまでの論議は、与えられたルールに対するＲＥＴＥネットワークの処理および構築（各ルール毎に暗黙条件をＲＥＴＥネットワークに加えることを含む）と関連するものであった。
【０１９５】もし多くのルールが存在するものとすれば、多くの個々のＲＥＴＥネットワークが構築される。
【０１９６】発明の背景の章に論述されたように、ＲＥＴＥネットワークの１つの重要な特徴は、ルール間に共通のテスト節点を共用することである。この特徴は、時に最適化ＲＥＴＥネットワークと呼ばれる。従来のＲＥＴＥネットワーク構築システムにおいては、ＲＥＴＥネットワークの構築に際して最適化ステップは統合化ステップである。換言すれば、ルールが構成される時最適化が生起する。従来のＲＥＴＥ構築システムにおいては、ＲＥＴＥネットワークは最初に１つのルールに対して構築される。その後、次のルールに対するＲＥＴＥネットワークが構築される時、コンパイラは既に前に構成されたテストを構成することはない。これは、最適化が実際のＲＥＴＥネットワーク構成に組込まれる場合である。
【０１９７】対照的に、本発明の各ルールは、それ自体の個々のＲＥＴＥネットワークにより構築される。従って、本発明における最適化は、個々のステップが生起する時で、結果冗長テストが構成された時に生起する。本文に述べたように、個々のＲＥＴＥネットワークが各ルール毎に構築された後に最適化が生起する必要はない。本発明は、最適化を構成モジュール６０６と統合化できるようにするものである。
【０１９８】次に、本発明の最適化モジュール６１０について論述する。
【０１９９】従来のＲＥＴＥネットワーク・システムにおいては、与えられたＲＥＴＥテスト・モードが多数のＲＥＴＥ節点の直系の親（即ち、右側入力又は左側）として供される。このため、１つのルール内あるいは幾つかのルールにわたり複数回現れる同じ条件は、ＲＥＴＥネットワーク内で一回だけ表現されるに過ぎない。このようなＲＥＴＥ節点を数多く再使用することが最適化とされる。最適化は、処理速度およびメモリの利用を著しく改善することができる。
【０２００】本実施例においては、ＲＥＴＥネットワークは最適化により、あるいはこれによらずに構築することができる。最適化によらないＲＥＴＥネットワークの構築の利点は、結果として得られるＲＥＴＥネットワークがデバッグおよび理解が容易であることである。このため、ユーザが最初にルールを構築してデバッグし、次いでＲＥＴＥネットワークをより良好な性能となるように「調整」することを可能にする。
【０２０１】本例においては、最適化は各ルート節点を調べることにより達成される。これは、与えられたデータ・オブジェクトのタイプを含む全てのＲＥＴＥネットワークのテスト節点を見出すために行われる。このプロセスは、可能な統合化のための全ての候補となるＲＥＴＥ節点を識別する。
【０２０２】この統合化は次の２つの形態を取る。即ち、１．テストの組合わせ２．入力の共有テストは下記の如く組合わされる。即ち、１．変数名を共通にすること：与えられたデータ・オブジェクトのタイプに関する変数を含む全てのテストが、関連する変数が共通名を持つように変更される。
【０２０３】２．要素内テストを組合わせること：連続するａｌｐｈａ節点が合成されたテストを持つ１つのａｌｐｈａ節点に「纏められる」（例えば、２つのａｌｐｈａテスト、ｘ．ｃｏｌｏｒ＝’Ｂｌｕｅ’ａｎｄ ｘ．ｗｈｅｅｌ＝４，が色および車輪の双方をテストする１つのａｌｐｈａテストとなる）。
【０２０４】３．要素間テストを組合わせること：ｂｅｔａ節点の如き連続的な多重入力テスト節点が、合成されたテストを持つ１つのテスト節点に「纏められる」。このプロセスは、ａｌｐｈａテストに用いられるものと非常によく似ている。
【０２０５】入力は下記の如く共有される：１．同じＲＥＴＥテスト節点が識別されること２．見出された各セットの同じテスト節点毎に、１つの節点が保持され、他は削除される。ＲＥＴＥネットワークにおけるリンクが、削除された節点と接続された節点がこの時残りの節点と接続されるように変更される。
【図面の簡単な説明】
【図１】本発明の動作を示す高レベルのブロック図である。
【図２】本発明のアーキテクチャ環境２００を示す高レベルのブロック図である。
【図３】本発明のＲＥＴＥネットワーク構築モジュール２０６のアーキテクチャを示す高レベルのブロック図である。
【図４】本発明の構文解析モジュール３０２の動作を示すブロック図である。
【図５】本発明の与えられたルールに対する構文解析ツリー５００の典型的なデータ構造を示すブロック図である。
【図６】本発明の変換モジュール３０４のアーキテクチャを示すブロック図である。
【図７】本発明の変換モジュール３０４の動作を示すブロック図である。
【図８】本発明の否定モジュール６０２のアーキテクチャを示すブロック図である。
【図９】否定されたルールを示す構文解析ツリー９００に対するデータ構造を示すブロック図である。
【図１０】否定を排除するように本発明の下方否定モジュール９０２により修飾される図９の構文解析ツリー９００に対するデータ構造を示すブロック図である。
【図１１】冗長ＡＮＤ節点を有するルールを表わす構文解析ツリー１１００に対するデータ構造を示すブロック図である。
【図１２】冗長ＡＮＤ節点を除去するため本発明のＡＮＤ排除モジュール８０４により修正される図１１の構文解析ツリー１１００に対するデータ構造を示すブロック図である。
【図１３】本発明の論理和モジュール６０４のアーキテクチャを示すブロック図である。
【図１４】論理和モジュール６０４の動作を示すブロック図である。
【図１５】内部に論理和条件を持つルールを示す構文解析ツリー１５００に対するデータ構造を示すブロック図である。
【図１６】本発明のシャフラ・モジュール１３０４が如何にして構文解析ツリーの最も高い動作レベルへ論理和をプッシュするかを示すように修正された図１５の構文解析ツリー１５００に対するデータ構造を示すブロック図である。
【図１７】論理和を排除するように、２つの構文解析ツリーに本発明の排除モジュール１３０６により修正される図１６の構文解析ツリーに対するデータ構造を示すブロック図である。
【図１８】本発明の構成モジュール６０６のアーキテクチャを示すブロック図である。
【図１９】本発明の構成モジュール６０６の動作を示すブロック図である。
【図２０】本発明の構成モジュール６０６の動作を示す、図１９の続きのブロック図である。
【図２１】本発明の多重入力フロー・リスト・モジュール１８０２のアーキテクチャを示すブロック図である。
【図２２】本発明の多重入力フロー・リスト・モジュール１８０２の動作を示すフローチャートである。
【図２３】本発明の多重入力フロー・リスト・モジュール１８０２の動作を示す、図２２の続きのフローチャートである。
【図２４】事例のルールに対する抽象構文ツリーを示す図である。
【図２５】図２２の事例に対して多重入力フロー・リスト・モジュール１８０２により構成されるフローリストの内容を示す図である。
【図２６】図２２の事例に対するａｌｐｈａ節点モジュール１８０４により構成されるフローリストの内容を示す図である。
【図２７】ａｌｐｈａ再整列ルーチン１８０６のアーキテクチャを示す図である。（図２８乃至図３５は、図２４R>４における事例の抽象構文ツリーに対するＲＥＴＥネットワーク構造のシーケンスを示す。）
【図２８】ａｌｐｈａ再整列ルーチン１８０６により生じたａｌｐｈａ節点接続の結果を示す図である。
【図２９】ステップ１９１４における多重入力節点モジュール１８０８により処理される第１の否定テストの結果を示す図である。
【図３０】多重入力ハンドラ・モジュール１９１６により処理される第２のテストの結果を示す図である。
【図３１】多重入力ハンドラ・モジュール１９１６の連続結果を示す図である。
【図３２】多重入力ハンドラ・モジュール１９１６の連続結果を示す図である。
【図３３】多重入力ハンドラ・モジュール１９１６の連続結果を示す図である。
【図３４】多重入力ハンドラ・モジュール１９１６の連続結果を示す図である。
【図３５】多重入力ハンドラ・モジュール１９１６の連続結果を示す図である。
【図３６】ＲＥＴＥネットワーク暗黙条件モジュール６０８のアーキテクチャを示す図である。
【符号の説明】
１０１ 動作ブロック １０２ 動作ブロック
２００ コンピュータ環境 ２０２ ＣＰＵ
２０４ メモリ装置
２０６ ＲＥＴＥネットワーク・モジュール
２０８ Ｉ／Ｏデバイス ２１２ バッファ
２１４ ホスト・バス ２１６ システム・バス
３０２ 構文解析モジュール ３０４ 変換モジュール
４０２ 動作ブロック ４０４ 変換モジュール
５００ 構文解析ツリー ５０２ プロダクション節点
５０４ プロダクション節点 ５０８ ＡＮＤ節点
５１０ テストＡ節点 ５１２ テストＢ節点
５１４ テストＣ節点 ５１６ テストＤ節点
５１８ 数式節点 ５２４ シンボル・リスト節点
６０２ 否定モジュール ６０４ 論理和モジュール
６０６ 構成モジュール ６０８ 暗黙条件モジュール
６１０ 最適化モジュール ７０４ 動作ブロック
７０６ 動作ブロック ７０８ 動作ブロック
７１０ 動作ブロック ７１２ 動作ブロック
８０２ 否定モジュール ８０４ ＡＮＤ排除モジュール
８０６ ＯＲ排除モジュール ９００ 構文解析ツリー
９０４ ＮＯＴ節点 ９０６ ＡＮＤ節点
９０８ テストＡ節点 ９１０ ＯＲ節点
９１２ ＮＯＴ節点 ９１８ テストＤ節点
１００２ ＯＲ節点 １００４ ＮＯＴテストＡ節点
１００６ ＡＮＤ節点 １００８ 正規テストＤ節点
１１００ 構文解析ツリー １１０６ 冗長ＡＮＤ節点
１１１２ テストＡ節点 １１１４ テストＢ節点
１３０２ 発見モジュール １３０４ シャフラ・モジュール
１３０６ 排除モジュール １３０８ ザッパー・モジュール
１４０２ 動作ブロック １４０４ 動作ブロック
１４０６ 動作ブロック １５００ 構文解析ツリー
１５０２ プロダクション節点 １５０４ プロダクション節点
１５０６ プロダクション節点 １５０８ ＡＮＤ節点
１５１０ ＯＲ節点 １５１２ テストＥ節点
１５１４ テストＣ節点 １５１６ テストＤ節点
１６０２ ＯＲ節点 １６０４ ＡＮＤ節点
１６０６ ＡＮＤ節点 １７０２ ルール節点
１８０２ 多重入力フロー・リスト・モジュール
１８０４ ａｌｐｈａ節点モジュール
１８０６ ダングリングａｌｐｈａモジュール
１８０８ 多重入力節点モジュール １９０２ 動作ブロック
１９０４ 動作ブロック １９０６ 動作ブロック
１９１０ 動作ブロック １９１２ 動作ブロック
１９１４ 動作ブロック １９１６ 多重入力節点ハンドラ
２００２ 純粋に負のフロー・リスト・モジュール
２００４ 純粋に正のフロー・リスト・モジュール
２００６ 混成量化モジュール
２１０２ 負のフロー・リスト・モジュール
２１０８ 動作ブロック ２１１２ 動作ブロック
２１１８ 動作ブロック ２１２８ 動作ブロック
２２０２ プロダクション節点 ２２０６ テスト節点
２２０８ テスト節点 ２２１０ テスト節点
２２１２ テスト節点 ２２１４ テスト節点
２２１６ シンボル・リスト ２２１９ シンボル・リスト
２２２２ シンボル・リスト ２２２４ シンボル・リスト
２２２６ シンボル・リスト ２３０４ フロー・リスト・エントリ
２３０６ フロー・リスト・エントリ ２３０８ フロー・リスト・エントリ
２３１０ フローリスト・エントリ点
２３１４ 正のフロー・リスト・ブロック
２３１６ 負のフロー・リスト・ブロック２４０４ フローリスト・エントリ点
２４０６ フローリスト・エントリ点 ２４０８ ａｌｐｈａ節点
２４１０ ａｌｐｈａ節点 ２４１２ ａｌｐｈａ節点
２５０２ ａｌｐｈａ並替えモジュール ２５０４ ａｌｐｈａ接続モジュール
２６１０ ダングリングａｌｐｈａ節点 ２７０２ ＢＥＴＡテスト節点
２９０２ ＢＥＴＡテスト節点 ３００２ ＡＮＤ節点
３１０２ ＡＮＤ ＮＯＴ節点 ３２０２ ＡＮＤ節点
３４０２ オブジェクト・リスト・モジュール
３４０４ 検証モジュール ３４０６ 挿入モジュール
【０００１】
【産業上の利用分野】本発明は、知識ベース即ちエキスパート・コンピュータ・システムにおいて使用される知識ベースを構築するためのシステムおよび方法に関する。特に、本発明は、知識ベース・コンピュータ・システムにおいて使用されるルールのＲＥＴＥパターン・マッチング・ネットワークを構築するためのシステムおよび方法に関する。
【０００２】
【関連技術】コンピュータにおいて動作するエキスパート・システムのための知識ベースは、典型的にはルールからなっている。これらのルールは、一般にＩＦ−ＴＨＥＮステートメントの形態で表現される。このルールのＩＦ部分は、パターンを形成する条件（システムにおけるオブジェクトに対するテスト）のコレクションを表わす。
【０００３】たくさんのパターンのコレクションとたくさんのオブジェクトのコレクションとのマッチングは、推論エンジンの１つの動作である。推論エンジンは、人工知能およびエキスパート・システムにおける論証構成要素である。推論エンジンは、典型的に３つの構成要素あるいは方法、即ち、(１)オブジェクトのコレクションと与えられたルールとの突合わせ、(２)その条件がオブジェクトに完全にマッチするルールのリストから１つのルールを選択し、(３)選択されたルールの発火（始動）を含む。
【０００４】推論エンジンにおける最も時間を費やす段階は、マッチング・プロセスである。例えば、１０００のオブジェクトと１０００のルールを持つシステムおよび方法であって、各ルールが３つの条件を持つ場合を考えよう。非常に簡単な実現方式においては、各ルールは全てのオブジェクトと比較される。これは、各実行サイクル毎に１兆回以上の突合わせ操作をもたらす。
【０００５】ＲＥＴＥのパターン・マッチング・アルゴリズムは、作業の小さな部分（即ち、１兆回より遥かに少ない突合わせ作業）のみでこの事例の結果を達成することができる複雑なアルゴリズムである。ＲＥＴＥパターン・マッチング・アルゴリズムについては、Ｃ．Ｌ．Ｆｏｒｇｙ著「ＲＥＴＥ： Ａ ＦＡＳＴＡＬＧＯＲＩＴＨＭ ＦＯＲ ＴＨＥ ＭＡＮＹ ＰＡＴＴＥＲＮ／ＭＡＮＹ ＯＡＢＪＥＣＴ ＰＡＴＴＥＲＮ ＭＡＴＣＨ ＰＲＯＢＬＥＭ」（「Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ」、第１９巻、１７〜３７頁、１９８２年）、およびＣ．Ｌ．Ｆｏｒｇｙ著「ＭＥＡＳＵＲＥＭＥＮＴＳ ＯＮ ＰＲＯＤＵＣＴＩＯＮ ＳＹＳＴＥＭＳ」（Ｄｅｐａｒｔｍｅｎｔ ｏｆ ＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，Ｃａｒｎｅｇｉｅ−Ｍｅｌｌｏｎ Ｕｎｉｖ．，米国ペンシルバニア州ピッツバーグ、１９８３年）に記載されている。以降ＲＥＴＥのパターン・マッチング・アルゴリズムについては、本発明により解決される問題の理解のため必要な程度にのみ記述する。
【０００６】このＲＥＴＥのパターン・マッチング・アルゴリズムは、突合わせ要素または方法に対する「分割征服」手法を実現する。与えられたルールを構成する条件がテストされる。１つの条件の失敗は、以降の条件のテストを阻止する。突合わせを行うため、ＲＥＴＥのパターン・マッチング・アルゴリズムは、ルールの前提となるものから組み立てられた（まとめられた）増補識別ネットワーク（本文では、ＲＥＴＥネットワークと呼ぶ）を使用する。各オブジェクトが、このオブジェクトのみに関する条件に対して最初にテストされる。次いで、これらのテストを通ったオブジェクトは、多くのオブジェクトを必要とするテストを行うために他のオブジェクトと一緒にされる。全てのテストを通ったオブジェクトのコレクションは、選択および発火（始動）の候補となる。
【０００７】このＲＥＴＥネットワークは、接続された節点のネットワークを含む。これらの節点とは、ｒｏｏｔ（根）節点、ａｌｐｈａ（アルファ）節点、ｂｅｔａ（ベータ）節点、ａｎｄ（アンド）節点、ｂｅｔａ ｎｏｔ（ベータ否定）節点、ａｎｄ ｎｏｔ（アンド否定）節点、ｔｅｒｍｉｎａｌ（終端）節点およびｇａｍｍａ（ガンマ）節点を含む。各オブジェクト・タイプ毎に１つのｒｏｏｔ節点がある。
【０００８】ｒｏｏｔ節点は、テストされるオブジェクトに対するエントリ点を表わす。ｒｏｏｔ節点は、そのオブジェクト・タイプに基づいてネットワークにおける子節点にそのオブジェクトを同報する。
【０００９】ａｌｐｈａ節点は、要素内（ｉｎｔｒａ−ｅｌｅｍｅｎｔ）テストを表わす。要素内テストは、１つのオブジェクトに対してテストを行う。要素内テストは、オブジェクトの属性がルールにおいて指定される如き定数値を有するかどうかと関連し得る。要素内テストはまた、オブジェクトの属性が述語による定数と関連しているかどうかと関係し得る。要素内テストは、更に、同じオブジェクトの２つの属性が指定された関連の下で一致するかどうかと関連し得る。これらのテストは、ルールの前提において負に定量化される変数について行われる。これらのテストはまた、正に定量化される変数についても行われる。即ち、これらのテストは、変数の不在ならびに変数の存在を検証するため使用され得る。
【００１０】ｂｅｔａ節点およびｂｅｔａ ｎｏｔ節点は、要素間（ｉｎｔｅｒ−ｅｌｅｍｅｎｔ）テストを表わす。要素内テストと異なり、要素間テストは多重データ・オブジェクトの試験属性をテストする。これらのテストは、２つ以上のデータ・オブジェクト間にある関係があるかどうかを判定する。ｂｅｔａ節点は、（１）純粋に負に定量化されるか、あるいは（２）純粋に正に定量化されるデータ・オブジェクトのセットをテストするため用いられる。正に定量化された変数と負に定量化された変数の組合わせに関するテストは、混成量化テストと呼ばれる。これらは、ｂｅｔａ ｎｏｔ節点によりＲＥＴＥネットワークにおいて実現される。ｇａｍｍａ節点は、ｂｅｔａ節点の変形である。ｂｅｔａ節点と同様に、これらの節点は要素間テストを実行する。しかしながら、ｂｅｔａ節点と異なり、これらの節点は、１つのソースからその入力の全てを受取り、ｂｅｔａ節点は左側の入力と右側の入力を有するが、ｇａｍｍａ節点は左側入力のみを有する。
【００１１】全ての要素間テストは、幾つかのデータ・オブジェクトが一緒にされてこれらが１つの点におけるテストに使用できるようにすることを必要とする。ｂｅｔａ節点は２つの入力を持つため、これらはオブジェクトの組合わせに役立つ。しかし、時には、全てのオブジェクトは１つの点（おそらくは、例えば、前のｂｅｔａ節点）において既に使用可能である。もしこの１つの点が要素間テストに対する入力として供し得るならば、２番目の入力は余分である。このため、幾つかの従来のシステムは、この異例な場合を許容するため、ｇａｍｍａ節点とｂｅｔａ節点を区別する。
【００１２】ａｎｄ節点は、後続の節点により後でテストするためのオブジェクトの組合わせを生成するように用いられる。これら節点は、一切のテストを行わない。これらは、単にデータ・オブジェクトのマージを容易にする。ａｎｄ ｎｏｔ節点は、ａｎｄ節点の変形例である。これらは、正に定量化された変数テストの結果を負に定量化された変数テストの結果と統合する。上記のａｌｐｈａ、ｂｅｔａおよびｇａｍｍａテストと関連して見ると、ａｎｄ ｎｏｔ節点はテスト不在の意味を構成する。
【００１３】ｔｅｒｍｉｎａｌ節点は、与えられたルールに対するＲＥＴＥネットワークの底部を表わす。各ルールは唯１つのｔｅｒｍｉｎａｌ節点を有する。
【００１４】同じテストを繰返して行うことを避けるため、ＲＥＴＥネットワークはメモリ節点を使用する。メモリ節点は、ネットワーク内の状態としてのオブジェクトとの突合わせ結果を記憶する。これらの節点は、ａｌｐｈａメモリ節点とｂｅｔａメモリ節点と呼ばれる。メモリ節点を構成するため、ネットワーク内の節点間を通過するオブジェクトは「トークン」と呼ばれ、これは１つのタグおよび１つのオブジェクト・リストからなる。タグは、なにかが知識ベースに加えられたことを示す＋か、あるいはなにかが知識ベースから取除かれたことを示す−であり得る。トークンと関連するオブジェクトのリストは、システムがルールの前提における連続するオブジェクトに対して突合わせを試みるかあるいは既に突合わせた如きオブジェクトの順列と対応する。
【００１５】動作は以下のとおりである。ａｌｐｈａ節点の入力に到着するトークンが関連するテストを満足する時は常に、ａｌｐｈａ節点の子節点へ送られる。もしこのトークンがテストを満足しなければ、子節点へは送られない。もし１つのオブジェクトが全ての要素内テストを満足する（これはまだ全ての要素間テストを満足しないかも知れないが）ならば、このオブジェクトはルールと「部分的に一致する」と言われる。ルールの前提の条件と部分的に一致するオブジェクトと対応するトークンは、ａｌｐｈａメモリ節点に記憶される。もし同じルールあるいは異なるルールの２つのオブジェクトが部分的に一致する全く同じテストを持つならば、ネットワークはこの２つに対してａｌｐｈａメモリ節点を共有する。
【００１６】トークンがｂｅｔａ節点の左側入力に分配されると、ｂｅｔａ節点は入来トークンを、その右側の親のａｌｐｈａ節点に関連するａｌｐｈａメモリ節点に記憶された各トークンと比較する。左側のトークンと一致する各右側トークンの場合は、新しいトークンが構成され、子のｂｅｔａメモリ節点に記憶される。このトークンは、次に子の節点に送られる。新しいトークンは左側のトークンと同じタグを持ち、オブジェクトのリストは左側および右側のトークンに対するオブジェクトの編集物となる。
【００１７】＋タグを持つトークンがｔｅｒｍｉｎａｌ節点に入る時は常に、それは衝突（conflict）セットに関連ルールの（トークンと対応する）インスタンシエーションを加える。−タグを持つトークンの到着は、衝突セットからの対応ルールのインスタンシエーションの削除をもたらす。
【００１８】明らかなように、知識ベースに対して最も後のルールの始動によりなされた変更のみが各サイクル毎に処理されねばならない。これらの変更は、ネットワークを介して「フィルタ」し、関連する場合に、ネットワークに記憶された状態が更新される。これは、ＲＥＴＥのパターン・マッチング・アルゴリズムの重要な属性である。このネットワークの出力は、衝突セットに対する束縛変数の仕様（拘束要因、突合わせたオブジェクト）を含む。
【００１９】ＲＥＴＥネットワークは、ＯＰＳ５（コンピュータ言語）に基づくコンピュータ・システムを用いて初めて実現された。このＯＰＳ５システムは、Ｃ．Ｌ．Ｆｏｒｇｙ著「ＯＰＳ５ ＵＳＥＲＳ ＭＡＮＵＡＬ」（Ｄｅｐａｒｔｍｅｎｔｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｃａｒｎｅｇｉｅ−ＭｅｌｌｏｎＵｎｉｖ．、１９８１年）に記載されている。
【００２０】ＯＰＳ５に基づくコンピュータ・システムにおいて、ユーザは、ルールの左側（ＬＨＳ）即ち前提を論理積形態にフォーマットしなければならない。換言すれば、ＲＥＴＥネットワークは、論理積形態で表現されるルールのみを処理することができる。ｐ１と名付けられた典型的なＯＰＳ５ルールは、下記の構文を用いて表現される。即ち、（ｐ ｐ１ （Ｃ１ ↑ａｔｒｒ１ ＜ｘ＞ ↑ａｔｔｒ２ １２）
（Ｃ２ ↑ａｔｔｒ１ １５ ↑ａｔｔｒ２ ＜ｘ＞）
−（Ｃ３ ↑ａｔｔｒ１ ＜ｘ＞）
（ｒｅｍｏｖｅ ２））
ルールｐ１は、そのＬＨＳに３つの条件を有する。これらの条件は、閉じ括弧のセットにより識別される。
【００２１】第１の条件（ルールの最初の行）は３つの個々のテストを有する。最初のテストは、オブジェクトがタイプＣ１であるかどうかに対応する。第２のテストは、タイプＣ１のオブジェクトが属性↑ａｔｔｒ１およびある値＜ｘ＞を持つかどうかに対応する。どんな値でも変数ｘと一致し得る。（ある変数による値の指定の示唆については以下において論述する。）第３のテストは、タイプＣ１のオブジェクトが１２に等しい値を持つ属性↑ａｔｔｒ２を有するかどうかに対応する。
【００２２】第２の条件（ルールの２行目）もまた、３つの個々のテストを有する。最初のテストは、オブジェクトがタイプＣ２であるかどうかに対応する。第２のテストは、タイプＣ２のオブジェクトが１５に等しい値を持つ属性↑ａｔｔｒ１を持つかどうかに対応する。第３のテストは、タイプＣ２のオブジェクトが値＜ｘ＞を持つ属性↑ａｔｔｒ２を持つかどうかに対応する。
【００２３】第３の条件（ルールの３番目の行）は、２つの個々のテストのみを有する。この条件が否定である（−参照）ことに注意を要する。最初のテストは、オブジェクトがタイプＣ３であるかどうかに対応する。第２のテストは、タイプＣ３のオブジェクトが属性↑ａｔｔｒ１および値＜ｘ＞を持つかどうかに対応する。
【００２４】ルールｐ１は、コンピュータ・システムおよび方法に第１の条件を満足するオブジェクトが存在し、また第２の条件を満足するオブジェクトが存在し、かつ第３の条件を満足するオブジェクトが存在するならば、始動される。このことが、３つの例示条件間の関係が論理積関係を示すことに注意する必要がある。
【００２５】ルール１においては、変数ｘが各条件に対する１回のテスト、即ち、第１の条件におけるオブジェクト・タイプＣ１の↑ａｔｔｒ１、第２の条件のオブジェクト・タイプＣ２の↑ａｔｔｒ２、および第３の条件におけるオブジェクト・タイプＣ３の↑ａｔｔｒ１において指定されることに注意されたい。変数ｘの共通指定の結果は、ルールが始動するためには、ＯＰＳ５言語コンピュータ・システムのアーキテクチャが、オブジェクトＣ１、Ｃ２およびＣ３と、それらの対応する属性（それぞれ、↑ａｔｔｒ１，↑ａｔｔｒ２，↑ａｔｔｒ１）が同じ値を有することを要求する。ＯＰＳ５に基づくコンピュータ・システムにおいては、これは異なるオブジェクトの属性が等しいかどうかをテストする唯一の方法である。
【００２６】ＯＰＳ５システムのＲＥＴＥネットワーク構築アーキテクチャは、ユーザが１つの条件において異なるオブジェクトの属性が同じであるかどうかをテストすることを許さず、ユーザがオブジェクト・タイプが最初に定義される時テストを包含しなければならないことを理解すべきである。以下に述べるように、この制限は著しい短所である。
【００２７】また、ユーザがオブジェクト・タイプが最初に定義される時与えられたオブジェクト・タイプについて全ての要素内テストを指定しなければならないことも理解すべきである。以下に述べるように、上記の制限は同様にＯＰＳ５ＲＥＴＥネットワーク構築アーキテクチャの著しい短所である。
【００２８】ＯＰＳ５システムは、要素内テスト、即ち単一のオブジェクトに対するテストを求めて、ルールの各条件を逐次調べることによりＲＥＴＥネットワークを構築する。各条件に対して、ネットワーク・コンパイラは、特定のオブジェクト・タイプの要素内テストを調べるテスト節点を一体に繋ぐ（与えられる条件、従ってオブジェクトに対して幾つかの要素内テストが存在し得る）。ＯＰＳ５システムは、ユーザがルールを書いた正確な順序で要素内テストの各々についてａｌｐｈａ節点を構築する。
【００２９】一旦ネットワーク・コンパイラが要素内テストを終了すると、このコンパイラはルールの各条件を再び調べて、要素間テストについて調べる節点を付加する。ＯＰＳ５に基づくシステムは、ｂｅｔａ節点を最初に構築する。ｂｅｔａ節点は、同様にユーザが書いたように正確に同じ順序で構築される。ＯＰＳ５システムは、次にｂｅｔａ ｎｏｔ節点を構築する。このｂｅｔａ ｎｏｔ節点もまた、ユーザが書いたのと正確に同じ順序で構築される。ＯＰＳ５システムにおいては、ｂｅｔａ節点またはｂｅｔａ ｎｏｔ節点の右側の入力は常にａｌｐｈａ節点から入るが、その左側入力はａｌｐｈａ節点またはｂｅｔａ節点から入り得る。
【００３０】次に、ＯＰＳ５コンパイラは各ルール毎にｔｅｒｍｉｎａｌ節点を付加する。
【００３１】明らかなように、ＯＰＳ５システムは「高制御」アーキテクチャを使用する。用語「高制御」とは、ユーザが結果として得るＲＥＴＥネットワーク構造に対して完全な制御を有するシステムおよび方法を意味する。高制御システムは、最適のＲＥＴＥネットワークが構築できるように、ユーザがルールを書く上でＯＰＳ５システムの制約に対する高度の馴染みを持つことを許容する。ＲＥＴＥネットワークの最適化が進むほど、マッチング・プロセスが早くなる。このようなユーザは、時に「パワー・ユーザ」と呼ばれる。効率のよいＲＥＴＥネットワークを構築する際、このような高制御のアーキテクチャに馴染みの少ないユーザは大きな問題に遭遇し易い。
【００３２】先に述べたように、ＯＰＳ５ ＲＥＴＥネットワーク構築アーキテクチャにおける１つの大きな問題は、ルールの前提内のオブジェクトについてのテストの仕様を処理する柔軟性に関する。ＯＰＳ５システムにおいては、ユーザは、オブジェクト・タイプが最初に定義される時、特定のオブジェクトに関する全てのテスト（要素内テストか、あるいは要素間テストか）を指定しなければならない。ＯＰＳ５アーキテクチャは、オブジェクトについての全てのテストが１つの条件内に分類されることを必要とする。ＯＰＳ５アーキテクチャは柔軟性に非常に欠ける。
【００３３】上記の制約は、ユーザが１つのオブジェクトについて任意のテスト、あるいは幾つかのオブジェクトについて相互に関連するテストを書くことを妨げる。ＯＰＳ５アーキテクチャは、ユーザが考えてルールを表現できる方法を決定する。これは、ＯＰＳ５システムの著しい制約である。
【００３４】ＯＰＳ５アーキテクチャにおける別の問題は、論理和を使用する能力に関する。ＯＰＳ５システムは論理和（即ち、ＯＲと関連する条件）を認識せず、ＲＥＴＥネットワークは論理積プロセスのみである。換言すれば、ＲＥＴＥネットワークは成功主義である。オブジェクトは与えられたテストにパスするかあるいはパスしない。ある場合にはパスするが、他の場合にはそうでない中間の根拠がない。論理和の使用は、この「中間の」根拠の使用を意味する。従って、ＲＥＴＥネットワークは、本質的に論理和向きと見做すことができない。ＯＰＳ５においては、ユーザは２つの個々のルールを構築しなければならない。特に、ユーザは論理和の各節に対して１つのルールを作らねばならない。
【００３５】ＯＰＳ５アーキテクチャにおける別の重要な問題は、ユーザが否定ルールを書く能力に関する。ＯＰＳ５システムは、複雑な否定的前提を認識しない。ユーザは、ルールを肯定的に枠付けしたステートメントで書かざるを得ない。
【００３６】ＯＰＳ５アーキテクチャの別の問題は、ＲＥＴＥに基づくシステムにおけるルールの動作（ＲＨＳ）部分を実施するために、ＲＨＳで参照されたオブジェクトがルールのＬＨＳに拘束されねばならないという要件に関する。ＯＰＳ５に基づくシステムにおいては、ユーザは、ルールのＲＨＳにおいて操作されるオブジェクトがルールのＬＨＳで参照されることを確実にしなければならない。この要件を満たすことができないと、システムの誤動作をまねく結果となることがある。
【００３７】上記のことは標準的なＲＥＴＥネットワークの処理について述べたが、他の構成およびＲＥＴＥ処理の強化は可能である。例示に過ぎないが、ＲＥＴＥネットワーク処理の修正についてはＭ．Ｉ．Ｓｃｈｏｒ等著「Ａｄｖａｎｃｅｓ ＩｎＲＥＴＥ Ｐａｔｔｅｒｎ Ｍａｔｃｈｉｎｇ」（ＩＢＭ Ｔ．Ｊ．Ｗａｔｓｏｎ Ｒｅｓｅａｒｃｈ Ｃｅｎｔｅｒ，ニューヨーク州ヨークタウン・ハイツ、１９８６年）に記載されている。
【００３８】ＲＥＴＥパターン・マッチング・アルゴリズムに対する別の拡張は「ＴＲＥＡＴアルゴリズム」である。このＴＲＥＡＴアルゴリズムについては、Ｄ．Ｐ．Ｍｉｒａｎｋｅｒ著「Ｔｒｅａｔ： Ａ Ｂｅｔｔｅｒ Ｗａｙ ｆｏｒ ＡＩＰｒｏｄｕｃｔｉｏｎ Ｓｙｓｔｅｍｓ」（Ｐｒｅｃｅｅｄｎｇｓ ｏｆ ６ｔｈＮａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ ＡｒｔｉｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅ、カナダ、ＷＡ、シアトル、１９８７年７月１３日〜１７日、４２〜４７頁）に記載されている。同文献に記載の如く、主な相違は、ＴＲＥＡＴアルゴリズムがネットワークにおける部分的結果をセーブしないことである。これは、ＲＥＴＥアルゴリズムより小さなメモリを使用するという利点を有する。
【００３９】
【発明の目的】以下に示すように、本発明は、ＲＥＴＥパターン・マッチング・アルゴリズムの広範囲な拡張に等しく適用し得るものである。
【００４０】本発明の一目的は、オブジェクトに対する任意に指定されたテストを有するルールを処理することができるＲＥＴＥネットワーク構築システムおよび方法を開発することにある。
【００４１】本発明の別の目的は、論理和によってオブジェクトに対するテストを関連させるルールを処理できるＲＥＴＥネットワーク構築システムおよび方法の開発にある。
【００４２】本発明の更に別の目的は、否定ルールを処理できるＲＥＴＥネットワーク構築システムおよび方法の開発にある。
【００４３】本発明の更に他の目的は、ルールの前提に指定されない暗黙の条件を有するルールを処理できるＲＥＴＥネットワーク構築システムおよび方法の開発にある。
【００４４】上記および他の目的については、本発明のシステムおよび方法により達成される。
【００４５】
【発明の概要】本発明は、従来のＲＥＴＥネットワーク生成システムおよび方法においてはこれまで得られない利点を提供する。本発明は、ＲＥＴＥネットワーク・システムの要件および利点を維持しながらＲＥＴＥネットワークを構成する、斬新な試みを用いるコンピュータ・システムおよび方法である。当業者には明らかなように、本発明は、ＲＥＴＥネットワークの種々の増強により統合化が可能であり、本発明の趣旨から逸脱することなく修正可能である。
【００４６】本発明は、主としてコンピュータによる人工知能あるいはエキスパート・システム構築ツールの環境において使用されることが予期される。しかし、本発明は、専用の人工知能またはエキスパート・システム・コンピュータ・システムと統合化が可能である。
【００４７】一実施例においては、本発明のシステムおよび方法は、オブジェクトに対する任意の指定されたテストを有するルールを処理することができる。ユーザは、オブジェクトの順序を心配することなくルールを書くことができる（このような心配は、従来のＲＥＴＥネットワーク生成システムおよび方法には存在する）。同時に、本発明のシステムおよび方法は、ユーザがＲＥＴＥネットワークのトポロジーをかなりの程度制御することを可能にする。
【００４８】本発明のシステムおよび方法は、(１)ＲＥＴＥネットワークの全体的なトポロジーを制御するため要素間テスト（例えば、ｂｅｔａ、ｂｅｔａ ｎｏｔ）のユーザにより書かれる如き相対的順序付けを可能にし、(２)前記要素間テストの相対的順序付けを考慮し、(３)オブジェクトの１の属性は複雑なテストにおいて参照されないが、オブジェクトの別の属性に対するテストの順序付けをできる限り考慮し、(４)ＲＥＴＥネットワークのサブセット全体が前記テストの成否の結果として可能化あるいは不能化されるかをその配置が制御するので、前記要素内テストがＲＥＴＥネットワークの性能を調整することを許容し、および（または）(５)負に定量化されたテストの意味論的意義を保存することにより、上記の特徴を達成する。
【００４９】別の実施例においては、本発明のシステムおよび方法は、ＲＥＴＥネットワークが性格において本質的に論理積的である（即ち、条件が一緒に＊＊ＡＮＤされることを要求する）故に、（典型的にＯＲ演算子により識別される）論理和形態で表わされるルールを認識し処理することができ、本発明はこのルールをＲＥＴＥネットワークを構築するように内部的に修正する。これを達成するため、本発明は、ＯＲ節を持つルールの前提を使用する。論理の標準的な論理和ルールを用いて、これを論理和正規形に変換する。この操作の結果、一緒にＯＲされる１組の論理積節をもたらすことになる。変換の後、本発明は論理積節について処理して各節毎に個々のルールを形成する。
【００５０】別の実施例においては、本発明のシステムおよび方法は、否定ルール（典型的には、ＮＯＴ演算子により識別される）を認識する。ＲＥＴＥネットワークはルールの任意の否定を取扱うことができないため、本発明のシステムおよび方法は、論理和ルールの場合のように、ルールを内部的に修正してＲＥＴＥネットワークを構築する。本発明のシステムおよび方法は、否定節に対してこれを肯定節に変換するためド・モルガンの法則を用いることによりこの変換を行う。
【００５１】別の実施例においては、本発明のシステムおよび方法は、暗黙条件を取扱う。本発明は、ルールの右側（ＲＨＳ）における各オブジェクトを検査して、これがルールの左側（ＬＨＳ）にあることを保証する。もしオブジェクトがＲＨＳに存在するがＬＨＳになければ、これは暗黙条件になる候補である。もし本発明がオブジェクトがＬＨＳの暗黙条件であると判定するならば、このオブジェクトをＲＥＴＥネットワークに加える。
【００５２】本発明の種々の目的、特徴および付随する利点については、本発明の以降の詳細な記述により更によく理解されよう。詳細な記述は、添付図面を参照する。
【００５３】
【実施例】本発明は、ＲＥＴＥネットワークを構築するためのシステムおよび方法である。本発明のシステムおよび方法は、従来のＲＥＴＥネットワーク構築システムおよび方法においてはこれまで得られなかった利点を提供する。本発明は、コンピュータに基づくエキスパート・システムの開発シェルおよび専用エキスパート・システムと共に統合化が可能である。図１は、本発明の動作を全般的に示す高レベルのブロック図である。動作ブロック１０１に示されるように、本発明はまず、１階述語論理あるいは相当の形態と機能的に実質上等価である構文でルールをユーザが入力することを可能にする。１階述語論理は、例えば、ルールを論理和、論理積あるいは否定形で表現することを許容する。
【００５４】動作ブロック１０２は、本発明の第２の動作を示す。動作ブロック１０２は、ルールについて動作（変換）してＲＥＴＥネットワークを表わすデータ構造を生成する。更に、動作ブロック１０２は、オブジェクトに対するテストを任意指定したルールを認識して処理するように動作する。動作ブロック１０２は、更に、論理和関係を持つオブジェクトに対する２つ以上のテストを有するルールを認識して処理するように動作する。動作ブロック１０２は更に、論理積関係を有するオブジェクトに対する２つ以上のテストを有するルールを認識して処理するように動作する。
【００５５】動作ブロック１０２に対応する構造は、本発明のＲＥＴＥネットワーク・モジュール２０６（最初に図２に関して論述する）である。以下において明らかになるように、本発明のＲＥＴＥネットワーク・モジュール２０６は、ユーザがルールをより多くの意義を持ちかつ理解可能なように表現することを可能にする。
【００５６】動作ブロック１０４は、ＲＥＴＥネットワークを表わす結果として得るデータ構造を示している。
【００５７】次に図２において、本発明のＲＥＴＥネットワーク・モジュール２０６のコンピュータ環境２００が示される。コンピュータ環境２００は、一般に、中央処理装置（ＣＰＵ）２０２と、ＲＥＴＥネットワーク・モジュール２０６を格納する主メモリ２０４と、入出力（Ｉ／Ｏ）デバイス２０８と、バッファ２１２とを含む。ＣＰＵ２０２、主メモリ２０４およびバッファ２１２は、ホスト・バス２１４を介して通信する。Ｉ／Ｏデバイス２０８およびバッファ２１２は、システム・バス２１６を介して通信する。
【００５８】望ましい実施態様においては、図２に示した形態は、ＩＢＭ ＰＳ／２パーソナル・コンピュータのワークステーション環境の形態である。ＩＢＭＰＳ／２は、「ＩＢＭ ＰＳ／２ Ｇｕｉｄｅ ｔｏ Ｏｐｅｒａｔｉｏｎｓ Ｍａｎｕａｌ」（米国ニューヨーク、アーモンク）に詳細に説明されている。
【００５９】コンピュータ環境２００を構成するコンピュータの構成要素／サブシステムは従来の設計であることを理解すべきである。現在入手可能な、あるいは将来開発される適当なコンピュータ構成要素／サブシステムを使用することができる。単なる例示として、本発明は、メインフレーム・コンピュータの如き他の形態で統合することが可能である。また、本発明は典型的には別のソフトウエア・モジュール（図示せず）と関連して動作することも理解すべきである。このような付加的なソフトウエア・モジュールは、エキスパート・システムのアプリケーションを開発できるようにするために必要となろう。
【００６０】また、ＲＥＴＥネットワーク・モジュール２０６は種々の他の形態において提供できることも理解すべきである。単なる例示として、ＲＥＴＥネットワーク・モジュール２０６は、ハードウエアまたは読出し専用メモリ（ＲＯＭ）デバイス（図示せず）に構成することができるファームウエアの形態を取ることもできる。更にまた、ＲＥＴＥネットワーク・モジュール２０６は、各ＲＯＭがＲＥＴＥネットワーク・モジュール２０６により実行されるものと類似する特定の動作を実行する、多重構成ＲＯＭの形態を取ることもできる。
【００６１】ＲＥＴＥネットワーク・モジュール２０６の高レベルの構造的表示が図３に示される。図示の如く、ＲＥＴＥネットワーク・モジュール２０６は、パーサ（構文解析）モジュール３０２と変換モジュール３０４とを含む。
【００６２】構文解析モジュール３０２は、ユーザにより入力されるルールを抽出して解釈し、またメモリ装置２０４（図２）に格納されたこれらルールを表わすデータを生成する機能を有する。一旦メモリ装置２０４に格納されると、このルールは、ＲＥＴＥネットワークを構築するため変換モジュール３０４により操作することができる。一般に、当技術において構文解析系（パーサ）は周知である。更に、大半のコンピュータ・システムは構文解析系を典型的に使用する。しかし、構文解析系は、通常は各システムの特定の要件を満たすように注文設計されている。
【００６３】図４は、本発明の構文解析モジュール３０２の高レベルの動作を示すブロック図である。動作ブロック４０２により示されるように、構文解析モジュール３０２は、ＣＰＵ２０２に対して最初に各ルール（前述の如く、１階述語論理と類似する構文で表現される）を調べることを指令する。動作ブロック４０４により示されるように、構文解析モジュール３０２は、ＣＰＵ２０２に各ルール毎に１つの抽象構文ツリーを生成するように命令する。動作ブロック４０６により示されるように、構文解析モジュール４０２は次に、変換モジュール３０４により後で処理するため、メモリ装置２０４に各ルールに対する抽象構文ツリーを記憶するように指令する。
【００６４】当業者には、１階述語論理に従う多数の言語が開発できることが明らかであろう。本発明の望ましい実施態様においては、構文解析モジュール３０２は、ＫＲＬと本発明者が呼ぶ構文におけるルールを認識して処理することができる。ＫＲＬは知識表現言語である。ＫＲＬ構文は、「Ｔｈｅ ＩＮＴＥＧＲＡＴＥＤ ＲＥＡＳＯＮＩＮＧ ＳＨＥＬＬ ＲＥＦＥＲＥＮＣＥ ＭＡＮＵＡＬ，ＩＢＭ」（１９８９年）に詳細に説明されている。
【００６５】ＫＲＬルールは、Ｉｆ−Ｔｈｅｎステートメントの形態で構成される。本発明においては、ユーザは、ＫＲＬルールのＩｆ部分を論理積、論理和あるいは否定形のいずれかで入力することができる。以下において明らになるように、本発明は、ユーザがルールのＩｆ部分を論理積、論理和あるいは否定形のいずれかで入力することを許容する構文言語を処理するために使用することができる。
【００６６】ＫＲＬ構文は、本発明が認識し処理できる唯一の言語である。現在入手可能な、あるいは将来開発される他の言語（構文）を使用することができる。当業者には明らかなように、このような状況においては、構文解析モジュール３０２は、実際に使用される構文の様式に見合うように修正（特別注文）されねばならないことになる。
【００６７】本論の目的にとって、僅かに高いレベルの抽象化でＫＲＬルールを表わすことが役立とう。この抽象化は、本文ではＫＲＬショートハンドと呼ぶ。
【００６８】ＫＲＬショートハンドにおいては、１つの文字で完全な要素内テストあるいは要素間テストが表わされる。例えば、車（オブジェクト）の色（属性）が青（属性値）であるかどうかをテストするルール条件においては、ＫＲＬは下記の如くになる。即ち、 ｘ： ｃａｒ Ｉｆ ｘ.ｃｏｌｏｒ ＝ 'Ｂｌｕｅ' ｔｈｅｎ... ＫＲＬショートハンドでは、簡単に書くことになる。即ち、 Ｉｆ Ａ ｔｈｅｎ....ここで、Ａは条件テスト全体を意味すると見做される。
【００６９】ＲＥＴＥネットワーク構成の目的のためにルールの顕著な要素を理解するための手段を除いて、ＫＲＬに勝るＫＲＬショートハンドの利点はない。
【００７０】本発明の望ましい実施態様は実際にはＫＲＬを使用すると理解すべきであるが、本文における全ての事例ルールはＫＲＬショートハンドで示される。
【００７１】再びＫＲＬの事例について見れば、Ｒｕｌｅ １．０で示されるルールのＬＨＳの表記は、下記のように論理積形で書くことができる。即ち、 Ｒｕｌｅ １.０．
ＫＲＬでは、ｘ： ｃａｒ： Ｉｆ ｘ.ｃｏｌｏｒ＝'Ｂｌｕｅ' ａｎｄ ｘ.ｗｈｅｅｌｓ＝４ ｔｈｅｎ.... ＫＲＬショートハンドでは、Ｉｆ Ａ ａｎｄ Ｂ ｔｈｅｎ...ＫＲＬショートハンドでは、シンボルＡおよびＢはそれぞれ、ルール１．０内の個々のテストを示す。各テストは、１つのオブジェクトについての要素内テスト、あるいは幾つかのオブジェクトについての要素間テストと対応し得る。以下に述べるように、本発明は、オブジェクトに対するテストの任意仕様を認識することができる。例えば、テストＡは、車の色が青であるかどうかと対応する。テストＢは、同じオブジェクトが４つの車輪（別の属性値の対）を持つかどうかと対応する。
【００７２】従来のＲＥＴＥネットワーク構築システムおよび方法は、本発明とは異なり、テストの上記の任意の論理積を認識して処理することができない。
【００７３】以下は、論理和形で書かれたＲｕｌｅ２．０で示されるＫＲＬルールのＬＨＳの表記である。即ち、 Ｒｕｌｅ２．０ Ｉｆ Ａ ｏｒ Ｂ ｔｈｅｎ．．．
下記は、それぞれＲｕｌｅ３．０および３．１で示される、否定形で書かれた２つのＫＲＬルールのＬＨＳの表記である。即ち、 Ｒｕｌｅ３．０ Ｉｆ ＮＯＴ（Ａ ａｎｄ Ｂ） ｔｈｅｎ．．．
Ｒｕｌｅ３．１ Ｉｆ ＮＯＴ（Ａ ｏｒ Ｂ） ｔｈｅｎ．．．
本発明の構文解析モジュール３０２は、論理積、論理和あるいは否定形のいずれかで表わされるルールを処理（構文解析）するように設計される。構文解析モジュール３０２はまた、オブジェクトに対するテストの任意仕様を処理するように設計される。更に、構文解析モジュール３０２は、ルールの能動部分（即ち、ＲＨＳ）を処理するように設計される。
【００７４】動作ブロック４０４に関して先に述べたように、構文解析モジュール３０２は各ＫＲＬルールに対して１つの抽象構文ツリーを生成する。抽象構文ツリーは当技術においては周知である。この抽象構文ツリーは、変換モジュール３０４により後で処理されるように、メモリ装置２０４に表現を示す便利な方法である。データ構造はメモリ装置２０４に格納される。望ましいモードにおいて、抽象構文ツリーはＫＲＬルールを表わすデータ構造である。
【００７５】単なる例示として、ＫＲＬショートハンドで示されるＲｕｌｅ４．０で示したＫＲＬルールの下記の抽象化について考察しよう。即ち、 Ｒｕｌｅ４．０ Ｉｆ(Ａ ａｎｄ Ｂ ａｎｄ Ｃａｎｄ Ｄ) ｔｈｅｎ...図５は、構文解析モジュール３０２により構築されたＲｕｌｅ４．０と対応する抽象構文ツリーを示す。Ｒｕｌｅ４．０に対する抽象構文ツリーは、プロダクション節点５０４、ＡＮＤ節点５０８、テストＡ節点５１０、テストＢ節点５１２、テストＣ節点５１４およびテストＤ節点５１６を含む。プロダクション節点５０４は、このルールに対するメモリ装置２０４内の場所である。各ルールは、関連するプロダクション節点を有する。また、プロダクション節点５０２および５０６も示される。プロダクション節点５０２および５０６は、各プロダクション節点が接続されることを示すため示される。
【００７６】ＡＮＤ節点５０８は、抽象構文ツリーの最も高いレベルである。ＡＮＤ節点５０８は、テストＡ、Ｂ、Ｃ、Ｄ間、即ちテストＡ節点５１０、テストＢ節点５１２、テストＣ節点５１４、テストＤ節点５１６の論理積関係を示す。
【００７７】また、数式節点５１８も示される。数式節点５１８は、テストＡ（テスト節点５１０）において行うことができる数学的演算を表わす。例えば、＝、＞または＜、＞＝、＜＝、＝タイプの数学的演算を実施することができる。例えば、ある数学式は下記のテストである。即ち、ｘ＝４。図５に更に示されるのは、本発明のシンボル・リスト節点５２４である。シンボル・リスト節点５２４は、テスト節点５１０の数式節点５１８において使用される特有な変数の合計リストである。本発明のシンボル・リスト節点は、各テスト条件において生じるオブジェクトを要約する便利な方法を提供する。以下に述べるように、シンボル・リストは本発明の重要な特質である。シンボル・リストは、フロー・リスト（以下に述べる）を許容し、従ってＲＥＴＥネットワークを容易に構成する。ここでは、シンボル・リストが、与えられたテストと関連する全ての特有な（全ての異なる型（種類）の）変数を含むメモリ装置２０４に格納されたリストを表わすと理解することが重要である。
【００７８】以下に述べるように、与えられたルールに対するＲＥＴＥネットワークを構築するため必要である重要な情報は、どのオブジェクトがルールの各条件テストと関連するか、どれだけが特有であり、オブジェクトが負に定量化されるかどうかである。特に、与えられたテスト節点に含まれるオブジェクトの量は、テスト節点がＲＥＴＥネットワークにおいて１入力節点あるいは２入力節点として表わされるかを決定する。
【００７９】変換モジュール３０４の高レベルのブロック図が図６に示される。図示の如く、変換モジュール３０４は、否定モジュール６０２と、論理和モジュール６０４と、構成モジュール６０６と、暗黙条件モジュール６０８と、最適化モジュール６１０を含む。これらのモジュールの動作は、図７に関して説明する。
【００８０】図７は、変換モジュール３０４の動作を高レベルで示すブロック図である。動作ブロック７０４（これは、「ｎｏｔ処理」と呼ばれる）により示されるように、変換モジュール３０４は、各抽象構文ツリーを最初に調べてこのルールが否定されるかどうかを判定するようにＣＰＵ２０２に対して命令する。もしこのルールが否定されるならば、変換モジュール３０４はＣＰＵ２０２に対して否定を排除するように命令する。望ましい実施態様においては、これは変換モジュール３０４により行われる最初の動作である。変換モジュール３０４においては、この動作は否定モジュール６０２（図６）によって行われる。しかし、動作ブロック７０４により示される動作は必ずしも変換モジュール３０４により最初に行われる動作である必要がないことを理解すべきである。しかし、もし否定が最初に指定されなければ、別のＯＲ節点が導入され、更に処理が要求されることになる。このため、望ましい実施態様では、否定を最初に排除することにする。他のメソッドは本質的にそれほど有効ではない。
【００８１】動作ブロック７０６（「ＯＲ処理」と呼ぶ）により表わされる如く、変換モジュール３０４は、各抽象構文ツリーを再び調べて、論理和形で表わされるルールを論理積正規形に変換するようにＣＰＵ２０２に命令する。この動作は、論理和モジュール６０４（図６R>６）により行われる。
【００８２】望ましい実施態様においては、上記の論理和フォーマット動作は、変換モジュール３０４により行われる第２の動作である。しかし、動作ブロック７０６により示される動作は必ずしも変換モジュール３０４により行われる第２の動作である必要はないことを理解すべきである。例えば、動作ブロック７０６により示される動作は、動作ブロック７０４により示される動作が後に続く最初の動作であってもよい。しかし、先に述べたように、望ましい実施態様は否定を最初に排除する。
【００８３】ブロック７０４、７０６により示される動作は、ＲＥＴＥネットワークの構築に先立ち生起する先行処理である。これらの動作は、ユーザが与えられたルールを否定形および（または）論理和形で表わすことを可能にする。これらの動作は、本発明の重要な特徴である。
【００８４】動作ブロック７０８により示されるように、変換モジュール３０４は次に、ＣＰＵ２０２に対して本発明のＲＥＴＥネットワークを構築するように命令する。動作ブロック７０８は、ＲＥＴＥネットワークの実際の構築プロセスを示す。この動作は、構成モジュール６０６（図６）によって行われる。
【００８５】動作ブロック７１０により示されるように、変換モジュール３０４は、必要に応じて、ＣＰＵ２０２に暗黙条件を加えることを指令する。動作ブロック７１０は、ルールのＲＨＳにおける各オブジェクトを調べてこれがルールのＬＨＳに存在することを保証するプロセスを示す。この動作は、暗黙条件モジュール６０８（図６）により行われる。
【００８６】動作ブロック７１２により示されるように、変換モジュール３０４は、最後にＣＰＵ２０２に対して本発明のＲＥＴＥネットワークを最適化するように指令する。動作ブロック７１２は、２つ以上のルールに現れるテストが同じテスト節点を共有するように、ＲＥＴＥネットワークを再構成するプロセスを示す。この動作は、最適化モジュール６１０（図６）により行われる。
【００８７】次に変換モジュール３０４の構造について論述する。否定モジュール６０２が図８において（図６のその一般形態に加えて）拡張された形態で示されることに注意する。図示の如く、否定モジュール６０２は、下方否定モジュール８０２と、ＡＮＤ排除モジュール８０４と、ＯＲ排除モジュール８０６とを含む。
【００８８】下方否定モジュール８０２は、コンピュータ環境２００が否定ルールを認識するように提供される。以下に示すＲｕｌｅ５．０は、構文記法で表わされる否定ルールの事例である。即ち、 Ｒｕｌｅ５．０ Ｉｆ ＮＯＴ(Ａ ａｎｄ（Ｂ ｏｒ Ｃ）ａｎｄ ＮＯＴ Ｄ）
上記の如く、式全体またはＬＨＳが否定される。
【００８９】Ｒｕｌｅ５．０に対する抽象構文ツリーが図９に示される。
【００９０】以下は、図９の抽象構文ツリーと関連して図８に示した（下方）否定モジュール８０２の動作の論議である。下方否定モジュール８０２は、各ルール（従って、ルール５．０）に対する抽象構文ツリーを調べて、これが否定されるルールであるかどうかを判定するようにＣＰＵ２０２に対して指令する。ルール５．０の事例においては、下方否定モジュール８０２は、ルール５．０が否定されることを判定する。次いで、下方否定モジュール８０２は、ルール５．０の抽象構文ツリーについて動作して否定節点を排除する。これは、ド・モルガン理論および（または）２重否定の法則をルール５．０のＬＨＳに対して用いることにより行われる。換言すれば、ＮＯＴ節点９０４により示される否定は、ルール５．０内の個々の命題（条件）へプッシュ・ダウンされる。
【００９１】ルール５．０のＬＨＳに否定を分配することは、結果として下記の構文記法を得る。即ち、 ＬＨＳ＝ＮＯＴ Ａ ＯＲ（ＮＯＴ Ｂ ＡＮＤ ＮＯＴ Ｃ）ＯＲ Ｄ図１０は、図１０に示した如き否定が下方否定モジュール８０２によりプッシュ・ダウンされた後の修正された抽象構文ツリーを示している。図９のＡＮＤ節点９０６の否定は図１０のＯＲ節点１００２と等価であることを注目すべきである。換言すれば、これらは、式ＮＯＴ（Ａ ａｎｄ Ｂ）＝ＮＯＴ Ａ ｏｒＮＯＴ Ｂを表わす。後者の式は、論理和を除いて、ＲＥＴＥネットワークに対する適正なフォーマットである。同様に、否定ＯＲ節点は、ＡＮＤ節点となる。
【００９２】また、図９および図１０において判るように、テストＡ節点９０８は、ＮＯＴテストＡ節点１００４となる。このＮＯＴ表記は、否定がこの条件レベルへプッシュ・ダウンされたことを示す。実際問題として、このことは、例えばｚ＝４であったテストがこの時４に等しくないＺとなることを意味する。また、ＯＲ節点９１０がＡＮＤ節点１００６となることに注意すべきである。テストＤ節点９１８を伴うＮＯＴ節点９１２は、通常のテストＤ節点１００８となる。ここで、図１０の構文解析ツリーは全ての観点において図９の構文解析ツリーと等価であることが明らかな筈である。換言すれば、図１０の構文解析ツリーは、依然としてユーザにより最初に示された如くルール５．０の論理的意味を表わす。
【００９３】従来のＯＰＳ５システムにおいては、ユーザは全体として否定されたルールを書くことができない。その代わり、ユーザは単に個々に条件を否定できるに過ぎない。対照的に、本発明、特に否定モジュール８０２は、ユーザに対してこのステップを実施する。これは、ユーザが否定されたルールとしてルールを表現することを可能にし、このことはユーザにとって更に有意義となろう。
【００９４】一旦与えられたルールが「操作」されて（もしあれば）否定がその最も低いレベル（条件命題レベル）へプッシュ・ダウンされたことが保証されると、否定モジュール６０２は次に冗長なＡＮＤ節点を排除する機能を行う。この機能は、ＡＮＤ排除モジュール８０４により行われる。冗長ＡＮＤ節点を含むルール６．０で示される事例ルールは、シンボル的に下記の如く示される。即ち、 Ｒｕｌｅ６．０ （Ａ ＡＮＤ Ｂ）ＡＮＤ（Ｃ ＯＲ Ｄ）ＡＮＤ Ｇ冗長ＡＮＤ節点の全ての連続層に対して実行が継続する。
【００９５】ルール６．０に対する抽象構文ツリーが、図１１に示される。明らかなように、冗長ＡＮＤ節点１１０４および１１０６が存在する。ＡＮＤ節点１１０６の排除がルール６．０の意味論的意義に影響を及ぼさないことに注意すべきである。ＡＮＤ排除モジュール８０４の実行は、ルール６．０をルール６．１として示される下記の修正式に変換する。即ち、 Ｒｕｌｅ６．１ Ａ ＡＮＤ Ｂ ＡＮＤ（Ｃ ＯＲ Ｄ）ＡＮＤ Ｇルール６．１に対する抽象構文ツリーは、図１２に示される。ＡＮＤ排除モジュール８０４は、冗長ＡＮＤ節点１１０６を排除するタスクを行う。明らかなように、図１１１１のテストＡ節点１１１２およびテストＢ節点１１１４は、構文解析ツリーにおいて「上げ」られた。
【００９６】しかし、ＡＮＤ排除モジュール８０４は必ずしも本発明によるＲＥＴＥネットワークの構築に必要でないことに注意すべきである。しかし、冗長ＡＮＤ節点を排除しないと、より大きな従ってより非効率的なＲＥＴＥネットワークをもたらす結果となることがある。
【００９７】ＯＲ排除モジュール８０６は、ＡＮＤ排除モジュール８０４と同様に動作する。ＯＲ排除モジュール８０６の目標は、冗長ＯＲ節点を排除することである。
【００９８】図１３は、論理和モジュール６０４に対するアーキテクチャを示す。論理和モジュール６０４は、各ルールから論理和を排除する機能を有する。論理和モジュール６０４は、発見モジュール１３０２、シャフラ・モジュール１３０４、排除モジュール１３０６およびザッパー・モジュール１３０８を含む。
【００９９】図１４は、論理和モジュール６０４の動作を示す高レベルのブロック図である。動作ブロック１４０２により示されるように、論理和モジュール６０４は最初ＣＰＵ２０２に対して各抽象構文ツリーを調べるように指令する。論理和モジュール６０４は更に、ＣＰＵ２０２に対して抽象構文ツリーを調べるように指令すると、このＣＰＵはＯＲ節点を子節点として有するＡＮＤ節点を見出すように働く。もしＯＲ節点が見出されると、次の動作が行われる。
【０１００】動作ブロック１４０４により示されるように、論理和モジュール６０４はＣＰＵ２０２に対してＯＲ節点を抽象構文ツリーにおける最も高い述語レベルへ「上げる」ように指令する。この動作は、１つのルールが２つの個別のルールに分けることができるように行われる。この動作は、抽象構文ツリーを経て何回かの繰返しを生じる。一旦論理和モジュール６０４がＯＲをその最も高い述語レベルへ移すと、これは次の動作を行う。
【０１０１】動作ブロック１４０６により示されるように、論理和モジュール６０４は、ＣＰＵ２０２に対して２つのルールを生成することによりＯＲ節点を排除するように指令する。換言すれば、論理和モジュール６０４は、論理和の各「足」毎に１つのルールを生成するよう働く。この動作は、分配則を用いることによって実行される。この動作は、ユーザにより最初に指定されたルールの意味論的意義に影響を及ぼすことはなく、これは単にＯＲのいずれか一方の側がルールの突合わせの目的には充分であるという事実を反映する。
【０１０２】図１３の論理和モジュール６０４のサブコンポーネントの各々に対するアーキテクチャは下記の如くである。
【０１０３】発見モジュール１３０２は、抽象構文ツリーの各々を調べてＯＲ節点をその子節点として有するＡＮＤ節点を見出す機能を有する。もし発見モジュール１３０２がこのようなＯＲ節点を見出すならば、発見モジュール１３０２はシャフラ・モジュール１３０４へ制御を渡す。
【０１０４】シャフラ・モジュール１３０４は、ＯＲ節点が構文解析ツリーの先頭へ移るように、与えられた抽象構文ツリーの節点を認識する。シャフラ・モジュール１３０４は、ルールの意味論的意義に影響を及ぼすことなく抽象構文ツリーを認識する。
【０１０５】シンボル記法で表現された下記の例示ルールについて考察しよう。このルールは、ルール７．０として記される。即ち、Ｒｕｌｅ７．０ （Ｃ ＯＲ Ｄ）ＡＮＤ Ｅルール７．０に対する抽象構文ツリーが図１５に示される。示されているのはプロダクション節点１５０２、１５０４および１５０６である。プロダクション節点１５０４が、例えばルール７．０と対応する。更に、２つの子節点、即ちＯＲ節点１５１０およびテストＥ節点を持つＡＮＤ節点１５０８が示される。ＯＲ節点１５１０は、その子節点としてテストＣ節点１５１４とテストＤ節点１５１６を有する。
【０１０６】分配則の使用により、ルール７．０を示すシンボル記法は下記の記法と等価であり、これはルール７．１として識別される。即ち、 Ｒｕｌｅ７．１ （Ｃ ＡＮＤ Ｅ）ＯＲ（Ｄ ＡＮＤ Ｅ）
明らかなように、ルール７．０の論理表現は、式（Ｃ ＡＮＤ Ｅ） ＯＲ （Ｄ ＡＮＤ Ｅ）に修正された。図１６は、修正されたルール７．１に対する抽象構文ツリーを示す。図示の如く、ＯＲ節点１６０２（前は、図１５のＯＲ節点１５１０）が抽象構文ツリーの先頭にある。ＯＲ節点１６０２はこの時、ルールにおける中心演算子となる。ルールの意味論的意義を維持するため、シャフラ・モジュール１３０４はまた、元のＯＲ節点１５１０の全ての兄弟（テストＥ節点１５１２）のコピーを、その各子節点即ちテスト節点１５１４および１５１６に付す。本質的に、前のＯＲ節点１５１０の下のテスト節点１５１４および１５１６は、それぞれＡＮＤ節点の下方の子節点となる。図１６においては、このことは、ＡＮＤ節点１６０４の子節点として示されるテストＣ節点１５１４およびテストＥ節点１５１２により表わされる。同様に、テストＤ節点１５１６およびテストＥ節点１５１２は、ＡＮＤ節点１６０６の子節点となる。図１６の抽象構文ツリーが図１５の抽象構文ツリーと同じ意味論的意義を有することは明らかであろう。
【０１０７】この時、論理和モジュール６０４は、ＯＲ節点１６０２を排除するよう働く。この特徴は、排除モジュール１３０６により行われる。排除モジュール１３０６は、ＯＲが存在するかどうかを判定するため、３回目にＣＰＵ２０２に抽象構文ツリーを調べるように指令する。ＯＲ節点が発見されると直ちに、排除モジュール１３０６が制御を実行ザッパー・モジュール１３０８へ渡す。
【０１０８】ザッパー・モジュール１３０８の構造は、実行されるとこれがＣＰＵ２０２に対してＯＲ節点を排除するように、またＯＲ節点の各子節点に対しては、新しいルール節点を生成するように指令する。このルール節点は、前のルール節点のクローンである。従って、ザッパー・モジュール１３０８は、ＯＲ節点の下方の各子節点をそれ自体の別個のルールへ変える。換言すれば、論理和の足の各々はこの時別個の抽象構文ツリーとして表わされる。
【０１０９】図１７は、ザッパー・モジュール１３０８の上記の動作に対する抽象構文ツリーを示している。図示の如く、ザッパー・モジュール１３０８は２つのルールを生成する。このルールは、ルール節点１５０４およびルール節点１７０２をそれらの格納場所として有する。本質的に、ザッパー・モジュール１３０８は図１６のＡＮＤ節点１６０６およびその子節点を用いて、図１７R>７のルール１７０２と対応する別個のルールを生成する。
【０１１０】上記の論議から判るように、論理和モジュール６０４は、論理和形で書かれたルールについて働いて、２つの別個のルールを生成する。否定モジュール６０２と同様に、論理和モジュール６０４は、コンピュータ・システム環境２００がＯＲ節点を含むルールを認識して処理することを許容する。本発明は、複雑なルールを用いて、これを２つの別個のルールに分割する。これは、ルールが適正なＲＥＴＥネットワーク・フォーマットで表現することができるように行われる。また、ＯＲ節点が多くのレベルにおいて起生し得ることに注意すべきである。論理和モジュール６０４は、全てのＯＲ節点が構文解析ツリーの先頭に押しやられるまでレベル単位に動作する。
【０１１１】この点において、本発明は、与えられたルールに対する抽象構文ツリーをＡＮＤ節点およびテスト節点のみが存在するように変換する。ＮＯＴ節点はないが、これはこれら節点が否定モジュール６０２により排除される故である。ＯＲ節点がないが、これはこれらが論理和モジュール６０４によって排除される故である。
【０１１２】次に、構成モジュール６０６が、ルールを構成してＲＥＴＥネットワークに構築するタスクを行う。図１８は、構成モジュール６０６の高レベルなアーキテクチャのブロック図を示す。構成モジュール６０６は、多重入力フロー・リスト・モジュール１８０２、ａｌｐｈａ節点モジュール１８０４、ダングリングａｌｐｈａルーチン１８０６、および多重入力節点モジュール１８０８を含む。
【０１１３】図１９及び図２０は、図１８の構成モジュール６０６の高レベルの動作を示すブロック図である。
【０１１４】まず図１９において、動作ブロック１９０２により示される如きＲＥＴＥネットワークの構築における最初のステップは、各テスト節点におけるシンボル・リストを調べて、全ての純粋に負の多重入力テストに対するフロー・リスト・エントリを形成することを含む。動作ブロック１９０４により示される如く、ＲＥＴＥネットワークの構築の２番目のステップは、残る各テスト節点におけるシンボル・リストを調べて、他の全ての多重入力テストに対するフロー・リスト・エントリを形成することを含む。また図１９により示される如く、動作ブロック１９０２および１９０４により記述される動作ステップは多重入力フロー・リスト・モジュール１８０２により行われる。
【０１１５】動作ブロック１９０６により示される如く、ＲＥＴＥネットワークの構築における次のステップは、テスト節点を再び調べて全ての単入力テスト（ａｌｐｈａテスト）に対するフロー・リスト・エントリおよびＲＥＴＥ節点を構成することを含む。以下に示し述べるように、ステップ１９０６はａｌｐｈａ節点モジュール１８０４により行われる。
【０１１６】次に図２０において、動作ブロック１９１０により示される如きＲＥＴＥネットワークの構築における次のステップは、正のフロー・リストを調べてダングリングａｌｐｈａテストを再整列することを含む。動作ブロック１９１２により示されるように、ＲＥＴＥネットワークの構築における次のステップは、ダングリングａｌｐｈａテストを右側のその隣接するテストへ接続することを含む。図２０により示されるように、動作ブロック１９１０および１９１２により記述される２つのステップは、ダングリングａｌｐｈａモジュール１８０６により行われる。
【０１１７】動作ブロック１９１４により示されるように、ＲＥＴＥネットワークの構築における次のステップは、多重入力テストを調べて、全ての純粋に負のテストに対する負のフロー・リストへｂｅｔａテストを取付けることを含む。このステップは、多重入力節点モジュール１８０８により行われる。
【０１１８】動作ブロック１９１６により示されるように、１つのルールに対してＲＥＴＥネットワークを構築する際の最後のステップは、各テスト節点を逐次再び調べることである。
【０１１９】先に述べた動作は、与えられたテスト節点のシンボル・リストにおける変数が正に定量化され、負に定量化され、あるいは混成されるかに従って行われる。特に、もし検査中のテストが正に定量化されたテストであれば、ＢＥＴＡテストが構成される。もし検査中のテストが混成量化であるならば、ＢＥＴＡ ＮＯＴテストが構成される。もし考察中のテストが単入力の負のテストであれば、純粋に負のテストが、ＡＮＤ ＮＯＴ節点でＲＥＴＥネットワークの正の側に接続される。上記のステップもまた、多重入力節点モジュール１８０８によって行われる。
【０１２０】この時行われる全ての接続は、フロー・リストの問題の変数の左側に現れる全ての変数もまた包含されるように構成される。このステップは、さもなければ、見過ごすおそれがあるｂｅｔａ節点を接続する働きがある。
【０１２１】ここで、フロー・リストの一般的概念について論述する。フロー・リストは、本発明の重要な特徴である。フロー・リストは、ＲＥＴＥネットワークが構築されつつある時更新される作業用主メモリ２０４（図２R>２参照）の専用ブロックである。このフロー・リストはまた、与えられたルールでテストされるオブジェクトの完全なセットを含む。更に明らかになるように、フロー・リストは、緻密なＲＥＴＥネットワークを構築する便利な方法を提供する。その理由は、与えられたテストと対応する全てのオブジェクトが相互に隣接することである。
【０１２２】望ましい実施態様において、本発明は２つのフロー・リスト、即ち正のフロー・リストと負のフロー・リストを使用する。この正のフロー・リストは、１つのルールでテストされる全ての特有な正で定量化されるオブジェクトの順序を付したリストである。負のフロー・リストは、１つのルールでテストされる全ての負で定量化された変数の順序を付したリストである。本文において明らかになるように、（１つは正の変数、１つは負の変数に対する）２つのフロー・リストを使用することで、ＲＥＴＥネットワークの構築を著しく容易にする。
【０１２３】構成モジュール６０６の各サブコンポーネント（多重入力フロー・リスト・モジュール１８０２、ａｌｐｈａ節点モジュール１８０４、ダングリングａｌｐｈａモジュール１８０６、多重入力節点モジュール１８０８）について、更に詳細に記述する。
【０１２４】動作において、また再び図１８において、多重入力フロー・リスト・モジュール１８０２は、ＣＰＵ２０２に対して各シンボル・リストを調べて、テストが２つ以上のオブジェクトを含むかどうかを判定するように指令する。多重入力フロー・リスト・モジュール１８０２は、このようなオブジェクトの検出と同時に、ＣＰＵ２０２に対してオブジェクトをフロー・リストへ加えることを指令する。付加されるオブジェクトに加えて、多重入力フロー・リスト・モジュール１８０２は、各オブジェクトがルールに現れる相対順位をフロー・リストに記憶する。
【０１２５】多重入力フロー・リスト・モジュール１８０２は、一般に、２入力テストに含まれるこれらオブジェクトを見出すための手段を含む。多重入力フロー・リスト・モジュール１８０２は更に、これらのオブジェクトを正のフロー・リストまたは負のフロー・リストのいずれかに記憶するための手段を含む。
【０１２６】望ましい実施態様においては、多重入力フロー・リスト・モジュール１８０２は与えられるルールについて抽象構文ツリーを調べ、負に定量化された多重入力テストを最初に探す。多重入力フロー・リスト・モジュール１８０２は、次に他の全ての多重入力テストについて構文ツリーを再び調べる。
【０１２７】上記の諸操作を行うためのモジュールのアーキテクチャが図２１に示される。図示の如く、多重入力フロー・リスト・モジュール１８０２は、純粋に負のフロー・リスト・モジュール２００２、純粋に正のフロー・リスト・モジュール２００４および混成量化モジュール２００６を含む。
【０１２８】図２２〜図２３は、多重入力フロー・リスト・モジュール１８０２および図２１のその対応する構造的サブコンポーネント、即ち、純粋に負のフロー・リスト・モジュール２００２、純粋に正のフロー・リスト・モジュール２００４および混成量化モジュール２００６の動作を詳細に示す高レベルのフローチャートである。特に、図２２は、純粋に負のフロー・リスト・モジュール２００２の動作を示し、図２３はモジュール２００４および２００６の動作を示す。
【０１２９】まず図２２において、動作ブロック２１０２により示されるように、純粋に負のフロー・リスト・モジュール２００２は最初に（各テスト毎にシンボル・リストを調べることにより）ＣＰＵ２０２に対して与えられたルールに対する抽象構文ツリーにおける次のテストを調べるように指令する。各テストが１つのシンボル・リストを持つことを想起しよう。最初の実行サイクルにおいて、抽象構文ツリーにおける次のテストがユーザにより書かれた最初のテストとなる。判断ブロック２１０４により示されるように、純粋に負のフロー・リスト・モジュール２００２はＣＰＵ２０２に対して考察中のテストが２つ以上の異なるオブジェクトを参照するかどうかを判定するように指令する。同じオブジェクトの２つの属性が同じであるかどうかをテストするテストが２つの異なるオブジェクトと見做されることがないことを理解すべきである。
【０１３０】もし唯１つのオブジェクトがテストにおいて参照されるならば、制御は判断ブロック２１０４により動作ブロック２１０２へ戻され（ＮＯループ参照）、ここでＣＰＵ２０２が抽象構文ツリーにおける次のテストを調べるように指令される。しかし、もし２つ以上のオブジェクトの異なるオブジェクトが存在するならば、制御は判断ブロック２１０４により判断ブロック２１０６へ送られる。
【０１３１】判断ブロック２１０６により示されるように、純粋に負のフロー・リスト・モジュール２００２がＣＰＵ２０２に対して、テストが純粋に負に定量化されるか、即ちテストにおいて参照される各オブジェクトが負に定量化されるかを判定するように指令する。もし全てのオブジェクトが負に定量化されるのでないならば、制御は動作ブロック２１０２へ戻り、ここでＣＰＵ２０２が抽象構文ツリーにおける次のテストを調べるように指令される。しかし、もしテストにおける各オブジェクトが負に定量化されるならば、判断ブロック２１０６が制御を動作ブロック２１０８へ送る。
【０１３２】動作ブロック２１０８により示されるように、純粋に負のフロー・リスト・モジュール２００２がＣＰＵ２０２に対してオブジェクトを負のフロー・リストへ加えるように指令する。オブジェクトは、テスト内のそれらのシーケンス順で付加される。その後、制御は判断ブロック２１１０へ進む。
【０１３３】判断ブロック２１１０により示されるように、純粋に負のフロー・リスト・モジュール２００２は抽象構文ツリーにおける最後のテスト節点かをテストする。もしこれが最後のテストでなければ、上記のサイクルが再開するとき、制御はＮＯループにより動作ブロック２１０２へ戻される。しかし、もし最後のテスト節点であるならば、制御は判断ブロック２１１０により図２３R>３の動作ブロック２１１２へ（２１５０を介して）送られる。
【０１３４】動作ブロック２１１２により示されるように、純粋に正のフロー・リスト・モジュール２００４がＣＰＵ２０２に対して、同じ抽象構文ツリーを再び調べるように指令する。このサイクルにおいては、抽象構文ツリーにおける次のテストは同様にユーザにより指定された最初のテストとなる。
【０１３５】判断ブロック２１１４により示されるように、純粋に正のフロー・リスト・モジュール２００４がＣＰＵ２０２に対して考察中のテストが２つ以上の異なるオブジェクトを参照するかどうかを判定するように指令する。もし唯１つのオブジェクトがこのテストにおいて参照されるならば、制御は動作ブロック２１１２へ戻され、ここでＣＰＵ２０２が抽象構文ツリーの次のテストを調べるように指令される。しかし、もし２つ以上のオブジェクトの異なるオブジェクトが存在するならば、制御は判断ブロック２１１４により判断ブロック２１１６へ送られる。
【０１３６】判断ブロック２１１６により示されるように、純粋に正のフロー・リスト・モジュール２００４がＣＰＵ２０２に対してテストが純粋に正に定量化されるかどうか、即ちテストにおいて参照された各オブジェクトが正に定量化されるかどうかを判定するように指令する。もしオブジェクトの全てが正に定量化されなければ、制御はＮＯループを介してテスト２１２６へ戻り、ここでＣＰＵ２０２はテストが混成量化を包含するかどうかを判定するように指令される。即ち、このＣＰＵは、テストにおいて参照されたあるオブジェクトが他のオブジェクトが負に定量化される一方、正に定量化されるかどうかを判定する。もしそうであれば、制御は動作ブロック２１２８へ進む。
【０１３７】動作ブロック２１２８により示されるように、混成量化モジュール２００６はＣＰＵ２０２に対してオブジェクトを負および正のフロー・リストへ加えるように指令する。オブジェクトは、テスト内に現れる順序で加えられる。その後、制御は判断ブロック２１２０へ進む。
【０１３８】もしテストが混成量化を含まなければ、制御はＮＯループを介してテスト２１１６へ戻り、ここでＣＰＵ２０２が抽象構文ツリーにおける次のテストを調べるように指令される。しかし、テストにおける各オブジェクトが正に定量化されるならば、制御は判断ブロック２１１６により動作ブロック２１１８へ送られる。
【０１３９】動作ブロック２１１８により示されるように、純粋に正のフロー・リスト・モジュール２００４はＣＰＵ２０２に対してオブジェクトを正のフロー・リストへ加えるように指令する。オブジェクトは、テスト内のそのシーケンス順に加えられる。その後、制御は動作ブロック２１１８により判断ブロック２１２０へ送られる。
【０１４０】判断ブロック２１２０により示されるように、フロー・リスト・モジュール２００４はＣＰＵ２０２に対して、問題のテストが抽象構文ツリーにおける最後のテストであるかどうかを判定するように指令する。もしこのテストが抽象構文ツリーにおける最後のテストでなければ、制御はＮＯループを介して動作ブロック２１１２へ戻される。しかし、もし問題のテストが抽象構文ツリーにおける最後のテストであるならば、制御は判断ブロック２１２０により動作ブロック２１３４へ送られ、ここで多重入力節点モジュール１８０８の動作が終了される。
【０１４１】多重入力フロー・リスト・モジュール１８０２が純粋に正、純粋に負、および混成の定量化テストを個々に処理することにより同様に実現するできることに注意すべきである。即ち、多重入力フロー・リスト・モジュール１８０２が、３つの個別のステップ、即ち、(１)純粋に正に定量化されるテスト、(２)純粋に負に定量化されるテスト、および(３)混成量化テストにおいて実現することができる。
【０１４２】しかし、望ましい実施態様においては、多重入力フロー・リスト・モジュールは２つの個々のステップ、即ち、(１)純粋に負に定量化されるテスト、および(２)他の全ての多重入力テストにおいて処理される。このような実施態様は、負に定量化されるテストの意味論的な完全性を更に充分に保護する。本実施態様はまた、テストのユーザの最初の順序がＲＥＴＥネットワークの最終的な状態において考慮できる程度を最大限にするものである。
【０１４３】図２４は、サンプル・ルール（図示せず）に対する抽象構文ツリー２２００を示している。プロダクション節点２２０２およびＡＮＤ節点２２０４が示される。更に、テスト節点２２０６、２２０８、２２１０、２２１２、２２１４および２２１６が示される。更にまた、それぞれが上記のテスト節点２２０６〜２２１６の各々に対応するシンボル・リスト２２１８、２２１９、２２２０、２２２２、２２２４および２２２６が示される。
【０１４４】シンボル・リスト２２１８は、テスト節点２２０６が負に定量化されるオブジェクトＡについてのテストを有することを示す。シンボル・リスト２２１９は、テスト節点２２０８が正に定量化されるオブジェクトＢについてのテストを有することを示す。シンボル・リスト２２２０は、テスト節点２２１０が純粋に正に定量化されるオブジェクトＣおよびＤについてのテストを有することを示す。
【０１４５】シンボル・リスト２２２２は、テスト節点２２１２がオブジェクトＥおよびＦについて参照するテストを有することを示す。シンボル・リスト２２２２は更に、オブジェクトＦが負に定量化されたオブジェクトであることを示す。このように、テスト節点２２１２により示されるテストは混成量化テストである。
【０１４６】シンボル・リスト２２２４は、テスト節点２２１４がオブジェクトＧおよびＨを参照するテストを有することを示す。シンボル・リスト２２２４は更に、オブジェクトＧおよびＨが負に定量化されることを示す。このように、テスト節点２２１４により示されるテストは、純粋に負に定量化される。シンボル・リスト２２２６は、テスト節点２２１６が正に定量化されるオブジェクトＩについてのテストを有することを示す。
【０１４７】本発明にとってＲＥＴＥネットワークを構築するために別の情報が不要であることに注意すべきである。
【０１４８】次に、構成モジュール６０６（図６）の動作について、図２２の抽象構文ツリー（ルール）に対するＲＥＴＥネットワークの構成を使用して更に説明する。
【０１４９】再び図２４において、また先に述べたように、構成モジュール６０６の最初の動作は、多重入力フロー・リスト・モジュール１８０２（図１８）の動作のそれである。多重入力フロー・リスト・モジュール１８０２の動作については、図２２〜図２３に関して詳細に述べた。構成モジュール６０６の第２の動作は、ａｌｐｈａ節点モジュール１８０４のそれである。第３の動作は、ダングリングａｌｐｈａモジュール１８０６のそれである。構成モジュール６０６の最後の動作は、多重入力節点モジュール１８０８のそれである。構成モジュール６０６のこれらサブモジュール１８０２、１８０４、１８０６および１８０８の各々について、図２４の抽象構文ツリーに対するＲＥＴＥネットワークを構築する環境において説明する。
【０１５０】図２５は、ブロック図フォーマットにおいて、正のフロー・リスト・ブロック２３１４および負のフロー・リスト・ブロック２３１６を示す。正のフロー・リスト・ブロック２３１４および負のフロー・リスト・ブロック２３１６は、メモリ装置２０４（図２）内の記憶場所である。
【０１５１】図２２に関して述べたように、多重入力フロー・リスト・モジュール１８０２の負のフロー・リスト・モジュール２１０２は、純粋に負のオブジェクトに対してフロー・リスト・エントリを最初に構成する。図２４２４に示されるルールにおいては、シンボル・リスト２２２４のオブジェクトＧおよびＨが多重入力テストの一部である純粋に負に定量化されたオブジェクトを示す。このように、シンボル・リスト２２２４のオブジェクトＧおよびＨは、フロー・リスト・エントリ２３０２および２３０４としてそれぞれ負のフロー・リスト・ブロック２３１６へ挿入される。他の純粋に負の２つの入力オブジェクトは存在しない。
【０１５２】図２３に関して述べたように、純粋に正のモジュール２００４はその後、ＣＰＵ２０２に対して図２４２４の全ての多重入力テストを調べるように指令する。純粋に正のフロー・リスト・モジュール２００４は、純粋に正のテストからのオブジェクトを正のフロー・リスト・ブロック２３１４へ加える。図２４に示されるように、シンボル・リスト２２２０のオブジェクトは、純粋に正の２つのオブジェクトであり、このため、フロー・リスト・エントリ２３０６および２３０８として正のフロー・リスト・ブロック２３１４にそれぞれ挿入される。図２４のシンボル・リストには、他の純粋に正の２つの入力オブジェクトは存在しない。
【０１５３】また図２３に関して述べたように、混成量化モジュール２００６がＣＰＵ２０２に対して混成量化テストの負のオブジェクトを負のフロー・リスト・ブロック２３１６へ加えるように指令する。シンボル・リスト２２２２のオブジェクトＦは、混成量化テストの負のオブジェクトであり、このため負のフロー・リスト・ブロック２３１６にフローリスト・エントリ点２３１０として挿入される。他の負の混成量化オブジェクトは存在しない。
【０１５４】その後、混成量化モジュール２００６が、混成量化テストの正のオブジェクトを正のフロー・リスト・ブロック２３１４へ加える。図２４に示されるように、シンボル・リスト２２２２のオブジェクトＥは、混成量化テストと対応する正の変数である。シンボル・リスト２２２２のオブジェクトＥは、フローリスト・エントリ２３１２として正のフロー・リスト・ブロック２３１４に挿入される。多重入力フロー・リスト・モジュール１８０２の動作のみが、比較的厳密な最適化されたＲＥＴＥネットワークを保証する。ユーザにより入力される多重入力テスト（ｂｅｔａテスト）の順序がＲＥＴＥネットワークの相対的な状態を決定することを理解すべきである。従って、本発明は、多重入力テストに関するユーザの順序を考慮する。
【０１５５】次に、ａｌｐｈａ節点モジュール１８０４の動作について正のフロー・リスト・ブロック２３１４および負のフロー・リスト・ブロック２３１６を修正する環境において記述する。図２６は、図２５の正のフロー・リスト・ブロック２３１４および負のフロー・リスト・ブロック２３１６の修正を示している。
【０１５６】図２６において、ａｌｐｈａ節点モジュール１８０４が多重入力フロー・リスト・モジュール１８０２と同様に働く。多重入力フロー・リスト・モジュール１８０２と同様に、ａｌｐｈａ節点モジュール１８０４がＣＰＵ２０２に対して図２４の抽象構文ツリーを調べてテスト節点を探すように指令する。
【０１５７】しかし、ａｌｐｈａ節点モジュール１８０４は、多重入力テストとは対照的に単入力テストにおいて使用されるオブジェクトを処理する。換言すれば、ａｌｐｈａ節点モジュール１８０４は、１つのオブジェクトを持つテスト節点を見出す。これらのテスト節点が最終的にａｌｐｈａテストとなる。
【０１５８】もし既に多重入力フロー・リスト・モジュール１８０２により構成されていなかったならば、これらの一入力テストに対するフローリスト・エントリは正のフロー・リスト・ブロック２３１４および（または）負のフロー・リスト・ブロック２３１６に加えられる（同じオブジェクトが１入力テストおよび２入力テストの双方にあり得、これが２入力テストの一部でもあるため、このオブジェクトに対するａｌｐｈａテストは非ダングリングａｌｐｈａテストと呼ばれることに注意）。従って、ａｌｐｈａ節点モジュール１８０４は図２４のシンボル・リストを調べて、負に定量化されるかどうかに拘わらず、フローリスト・エントリをこれが見出す順序で構成する。
【０１５９】多重入力フロー・リスト・モジュール１８０２とは対照的に、１つの入力オブジェクトをフロー・リストに入力する時、ａｌｐｈａ節点モジュール１８０４はＣＰＵ２０２に対してＲＥＴＥ ａｌｐｈａ節点を即時構成するように指令する。これは、本発明により実際に構成された最初のＲＥＴＥ節点である。
【０１６０】もし同じオブジェクトが多くの１入力テストを有するならば、多重ａｌｐｈａ節点は一方が他方の下に接続される。ａｌｐｈａ節点が最初に構成されるが、これは関連する任意のａｌｐｈａ節点の接続前にｂｅｔａ節点を接続することが非効率的であるためである。
【０１６１】図２６に示されるように、ａｌｐｈａ節点モジュール１８０４は、正のフロー・リスト・ブロック２３１４および負のフロー・リスト・ブロック２３１６を「更新」している。図示の如く、図２のシンボル・リスト２２１８の負に定量化されたオブジェクトＡが、負のフロー・リスト・ブロック２３１６におけるフローリスト・エントリ２４０２として加えられている。同様に、シンボル・リスト２２０８および２２１６のオブジェクトＢおよびＩは、それぞれ正のフロー・リスト・ブロック２３１４におけるフローリスト・エントリ点２４０４および２４０６として加えられている。図２６に更に示されるように、ａｌｐｈａ節点モジュール１８０４はまたａｌｐｈａ節点２４０８、２４１０、２４１２をそれぞれ構成している。
【０１６２】前記の節点は、ＲＥＴＥネットワークに対して構成された最初の節点である。本発明がＲＥＴＥネットワークを正のフロー・リスト・ブロック２３１４および負のフロー・リスト・ブロック２３１６から構成することを理解すべきである。このようなデータ構造が、ＲＥＴＥネットワークの構築の便利な方法を提供する。
【０１６３】この点において、本発明の多重入力フロー・リスト・モジュール１８０２およびａｌｐｈａ節点モジュール１８０４が、与えられたルールにおいて使用される各オブジェクトを識別している。更に、多重入力フロー・リスト・モジュール１８０２およびａｌｐｈａ節点モジュール１８０４が、これらのオブジェクトをフローリスト・エントリ点として正または負のフロー・リストへ入力した。
【０１６４】次に、図１８のダングリングａｌｐｈａモジュール１８０６の動作について、図２６の正のフロー・リスト２３１４および負のフロー・リスト２３１６の修正の環境において論議する。
【０１６５】一般に、ダングリングａｌｐｈａモジュール１８０６が、ダングリングａｌｐｈａ節点がユーザにより生成された順序で配置されるようにＣＰＵ２０２に対して正のフロー・リスト・ブロック２３１４を並替えることを指令する。ダングリングａｌｐｈａテストは、要素間テストにより使用されないオブジェクトについての要素内テストである。換言すれば、これはこのオブジェクトが多重入力テストにおいて参照されない場合のオブジェクトについての単一テストである。本発明はまた、ユーザにより全ての以降のテストを禁止するように指定された手段としてダングリングａｌｐｈａテストとも呼ばれる。換言すれば、本発明は、ユーザが専らダングリングａｌｐｈａテストの設置によりＲＥＴＥネットワークのサブセクションを選択的に使用可能／使用不能にすることを許容する。ダングリングａｌｐｈａテストは、可能な限り優先権を与えられる。
【０１６６】図２７に示されるように、ダングリングａｌｐｈａモジュール１８０６は、ａｌｐｈａ並替えモジュール２５０２およびａｌｐｈａ接続モジュール２５０４を含む。ａｌｐｈａ並替えモジュール２５０２は、ユーザが最初に置いた場所へダングリングａｌｐｈａテストが置替えられるように、正のフロー・リスト２３１４を修正する。しかし、ａｌｐｈａ並替えモジュール２５０２が正のフロー・リスト・ブロック２３１４のエントリのみを修正することに注意すべきである。換言すれば、ａｌｐｈａ並替えモジュール２５０２は負のフローリスト・エントリは修正しない。その理由は、負に定量化されたテストの意味論的意義を保存することである。
【０１６７】図２８に示されるように、ａｌｐｈａ並替えモジュール２５０２の動作が、図２６の正のフロー・リスト・ブロック２３１４を修正した。図２８から判るように、シンボル・リスト２２１９のオブジェクトＢがフローリスト・エントリ点２４０４から２３０６へ移されている。シンボル・リスト２２２６のオブジェクトＩは、そのテスト場所（番号６）がこれが既にその適正な場所にあることを示す故に、置替えられることがない。
【０１６８】ａｌｐｈａ並替えモジュール２５０２は、ここで述べるアルゴリズムを用いて上記の再構成を実施する。このアルゴリズムにおいては、ａｌｐｈａ並替えモジュール２５０２は各フローリスト・エントリと関連する番号を参照する。抽象構文ツリーにより最初に構文解析モジュール３０２がルール全体にオブジェクト場所を格納することを想起されたい。ａｌｐｈａ並替えモジュール２５０２は、左側から始めて各フローリスト・エントリ・テスト番号を持つダングリングａｌｐｈａテストを比較してフロー・リストにわたって反復する。この反復がダングリングａｌｐｈａ節点番号が左側のそれより大きくかつ右側のそれより小さいことを判定する時、ＣＰＵ２０２はこの場所にダングリングａｌｐｈａを挿入することを知る。次いで、全ての以降の変数の場所へ当たる。
【０１６９】次に、図２７のａｌｐｈａ接続モジュール２５０４について論述する。ａｌｐｈａ接続モジュール２５０４は、ＣＰＵ２０２に対してダングリングａｌｐｈａを隣接するフローリスト・エントリ点と接続するように指令する。この操作はまた、図２８に示される。図示の如く、ダングリングａｌｐｈａ節点２６１０は、ＡＮＤ節点２６０６によりフローリスト・エントリ点２３０６と接続されている。これは、ダングリングａｌｐｈａ節点２６１０がＲＥＴＥネットワークの残りと接続されるように行われる。フローリスト・エントリ点２４０６（オブジェクトＩ）およびその関連するａｌｐｈａ節点２４１２がＡＮＤ節点と接続されなかったことに注意すべきである。この理由は、フローリスト・エントリ２４０６が正のフロー・リスト・ブロック２３１４における最も右に離れたエントリであるためである。図には示さないが、２つの隣接するダングリングａｌｐｈａ節点が相互に接続され、次いで次の右側に隣接するフローリスト・エントリと接続されることを理解すべきである。
【０１７０】ダングリングａｌｐｈａモジュール１８０６は本発明の顕著な特徴であり、これがパワーユーザがＲＥＴＥネットワークのトポロジーに対する制御を維持することを可能にする。
【０１７１】一般に、ＢＥＴＡ節点およびＢＥＴＡ ＮＯＴ節点がＲＥＴＥネットワークのトポロジーを制御する。多重入力オブジェクトに対するフロー・リストを最初に、次いでその中にダングリングａｌｐｈａを再び挿入する理由は、非ダングリングａｌｐｈａテストが与えられたルールに存在し得る故である。非ダングリングａｌｐｈａはＢＥＴＡ節点により駆動されるが、これはこれら節点が関連する２入力テストに対する入力として要求される故である。先に述べたように、本発明は、緊密なＲＥＴＥネットワークを取得するため全てのＢＥＴＡ参照オブジェクトを一体化する。しかし、このような特徴に打ち勝つため、本発明は、ダングリングａｌｐｈａテストのユーザのシーケンスを考慮する。
【０１７２】次に構成モジュール６０６の多重入力節点モジュール１８０８について詳細に論述する。先に述べたように、多重入力節点モジュール１８０８の動作はＲＥＴＥネットワークの構築における最終的な動作を表わす。多重入力節点モジュール１８０８の動作は２つのステップからなる。
【０１７３】第１のステップは、図２０の動作ブロック１９１４において前に示したように、シンボル・リストを逐次調べて純粋に負のＢＥＴＡテスト（２つ以上のオブジェクトを含むテスト）のみを見出すことである。もし純粋に負のＢＥＴＡテストが見出されると、負のフロー・リストについてテストされたオブジェクトに対してＢＥＴＡテストが構成される。
【０１７４】第２のステップは、前に図１９の動作ブロック１９０４に示したように、（純粋に負の２入力テストのみが問題となる第１のステップとは対照的に）シンボル・リストにおける各テストの順次の再検査のステップである。シンボル・リストに与えられたテストが正に定量化された、負に定量化された、あるいは混成量化されたかに従って、ある動作が行われる。
【０１７５】一般に、もし検査中のテストが正に定量化された多重入力テストであれば、ＢＥＴＡテストが構成される。もし検査中のテストが混成量化されたテストであれば、ＢＥＴＡ ＮＯＴテストが構成される。もし問題のテストが純粋に負のテスト（即ち、負のフロー・リストから外されるａｌｐｈａ節点あるいはｂｅｔａ節点）であれば、純粋に負のテストがＡＮＤ ＮＯＴ節点でＲＥＴＥネットワークの正の側に接続される。
【０１７６】多重入力節点モジュール１８０８の上記の動作は、図２４に示したルールに対するＲＥＴＥネットワークの継続的構築を参照すれば更によく理解される。図２８において、ダングリングａｌｐｈａモジュール１８０６がユーザにより指定される如きその元の場所に対するダングリングａｌｐｈａテスト（オブジェクトＢのテスト）を認識して、これをＡＮＤ節点（ＡＮＤ節点２６０６）でＲＥＴＥネットワークに接続したことを想起されたい。
【０１７７】先に述べたように、多重入力節点モジュール１８０８の動作における最初のステップは、純粋に負の２入力テスト（２つ以上のオブジェクトに対するテスト）に対するＢＥＴＡテストの構成のステップである。動作においては、多重入力節点モジュール１８０８は、ＣＰＵ２０２に対して図２４のシンボル・リストを調べて全ての純粋に負の２入力テストを見出すように指令する。図２５に示した事例においては、ＣＰＵ２０２が唯１つのこのようなテスト、即ち、オブジェクトＧおよびＨを参照するテスト２２１４が存在することを判定する。図２９から判るように、多重入力節点モジュール１８０８は、ＣＰＵ２０２に対してＢＥＴＡテスト節点２７０２を介してオブジェクトＧおよびＨを接続するように指令する。他の純粋に負の２入力テストは存在しない。このため、上記の操作後のＲＥＴＥネットワークの状態は、図２９に示される如くである。
【０１７８】次に、多重入力節点モジュール１８０８の第２のステップについて、図２４のルールに対するＲＥＴＥネットワークの構築に関して記述する。先に述べたように、多重入力節点モジュール１８０８は、ＣＰＵ２０２に対して各テストを再び調べて、テストの種類に応じてこのテストについてある動作を行うように指令する。
【０１７９】一例において、図２４のシンボル・リストを逐次調べることは、テスト２２０６（オブジェクトＡに対するテスト）が検査中の最初のテストであることを示す。テスト２２０６は、オブジェクトＡに対する純粋に負のテストである。図３０に示されるように、この種のテストに応答して、多重入力節点モジュール１８０８はＣＰＵ２０２に対してオブジェクトＡ（負のフロー・リストに見出される）をＡＮＤ ＮＯＴ節点で正のフロー・リスト・ブロック２３１４に接続するように指令する。
【０１８０】ルールにおける最初のテスト（テスト２２０６）の動作を完了した後、多重入力節点モジュール１８０８はＣＰＵに対してこのルールの次のテストを調べるように指令する。図２４のルールの次のテストは、テスト２２０８のテスト（オブジェクトＢに対するテスト）である。テスト２２０８を調べると、テスト２２０８がオブジェクトＢに対する純粋に正の１入力テストであることが示される。このような場合、多重入力節点モジュール１８０８は通常、ＣＰＵ２０２に対してオブジェクトＢをＡＮＤ節点を介して（全てのａｌｐｈａ節点が前にａｌｐｈａ節点モジュール１８０４により構成されたことを想起されたい）ＲＥＴＥネットワークと接続するように指令する。しかし、本例においては、オブジェクトに対するａｌｐｈａテストが既に節点２６０６を介してＲＥＴＥネットワークに接続されている。従って、テスト２２０８に対して動作を行う必要はない。
【０１８１】その後、多重入力節点モジュール１８０８はもう一度ＣＰＵ２０２に対して図２４のルールにおける次のテストを調べるように指令する。図２４のルールにおけるこの次のテストは、テスト２２１０（オブジェクトＣおよびＤに対するテスト）のそれである。テスト２２１０を調べると、テスト２２１０がオブジェクトＣおよびＤに対する純粋に正の２入力テストであることが示される。図３１に示されるように、この種のテストに応答して、多重入力節点モジュール１８０８はＣＰＵ２０２に対してオブジェクトＣおよびＤをＢＥＴＡテスト節点２９０２を介して接続するように指令する。
【０１８２】その後、多重入力節点モジュール１８０８はもう一度ＣＰＵ２０２に対して図２４のルールにおける次のテストを調べるように指令する。図２４のルールにおける次のテストは、テスト２２１２（オブジェクトＥおよびＦに対するテスト）のそれである。テスト２２１２を調べると、テスト２２１２は、オブジェクトＥが正に定量化され、オブジェクトＦが負に定量化されたものである混成量化されたテストであることが示される。
【０１８３】図３２に示されるように、この種のテストに応答して、多重入力節点モジュール１８０８はＣＰＵ２０２に対してオブジェクトＥおよびＦをＢＥＴＡ ＮＯＴ節点３００４で接続するように指令する。しかし、図２４のルールにおいてオブジェクトＥが最初にＲＥＴＥネットワークと接続されねばならないことを知るべきである。従って、この種の状況においては、多重入力節点モジュール１８０８は最初にＣＰＵ２０２に対してオブジェクトＥをＡＮＤ節点３００２によりＲＥＴＥネットワークに接続することを指令する。一般に、多重入力節点モジュール１８０８は最初にフロー・リストにおける最も左側のオブジェクトが実際に問題となるテストを構成する前にＲＥＴＥネットワークに接続されるかどうかを判定する。
【０１８４】その後、多重入力節点モジュール１８０８はもう一度ＣＰＵ２０２に対して図２４のルールにおける次のテストを調べるように指令する。図２４のルールにおける次のテストは、テスト２２１４（オブジェクトＧおよびＨに対するテスト）のそれである。テスト２２１４を調べると、テスト２２１４が純粋に負に定量化された２入力テストであることが示される。図３３に示されるように、この種のテストに応答して、多重入力節点モジュール１８０８はＣＰＵ２０２に対してＢＥＴＡテスト節点２７０２をＡＮＤ ＮＯＴ節点３１０２を介してＲＥＴＥネットワークに接続するように指令する。オブジェクトＧおよびＨに対するＢＥＴＡテストが多重入力節点モジュール１８０８の最初の動作により構成される最初のテストであったことを想起されたい。多重入力節点モジュール１８０８の第２の動作においては、ＣＰＵ２０２に対してＢＥＴＡテスト２７０２をＲＥＴＥネットワークの残部に接続するように指令するだけである。
【０１８５】その後、多重入力節点モジュール１８０８はもう一度ＣＰＵ２０２に対してルールにおける次のテストを調べるように指令する。図２４のルールにおける次のテストは、テスト２２１６（オブジェクトＩに対する正に定量化されたテスト）である。テスト２２１６はまた、図２４のルールにおける最後のテストでもある。テスト２２１４を調べると、テスト２２１４はオブジェクトＩに対する純粋に正の１入力テストであることが示される。この場合、多重入力節点モジュール１８０８はＣＰＵ２０２に対してオブジェクトＢをＡＮＤ節点３２０２を介して接続するように指令する（ａｌｐｈａ節点２４１０が前にａｌｐｈａ節点モジュール１８０４により構成されたことを想起されたい）。
【０１８６】その後、多重入力節点モジュール１８０８はもう一度ＣＰＵ２０２に対して図２４のルールにおける次の入力テストを調べるように指令する。しかし、この時ＣＰＵ２０２は、多重入力節点モジュール１８０８に対して、これ以上のテストがルールに存在しないことを指令する。これに応答して、多重入力節点モジュール１８０８はＣＰＵ２０２に対してＡＮＤ節点３２０２をプロダクション節点２２０２に接続するよう指令する。
【０１８７】プロダクション節点２２０２が図２４のプロダクション節点２２０２であることに注意すべきである。換言すれば、ＲＥＴＥネットワークは、プロダクション節点２２０２を「放す」のである。更に、先に述べたように、プロダクション節点２２０２は、図２４のルールに関する全ての情報に対する中心の場所である。この種のデータ構造は、与えられたルールに対するＲＥＴＥネットワークを構成して構築する便利な方法である。
【０１８８】次に、暗黙条件モジュール６０８について論述する。暗黙条件モジュール６０８は、あるルールのＲＨＳの全ての暗黙条件が知識ベースに実際に存在することを保証するようにルール・セットに対して作用する。暗黙条件モジュール６０８は、事物が未決定の点である衝突するセットに落込むことを許さない。
【０１８９】図３６に示されるように、暗黙条件モジュール６０８は、オブジェクト・リスト・モジュール３４０２と、検証モジュール３４０４と、挿入モジュール３４０６とを含む。
【０１９０】一般に、暗黙条件モジュール６０８は、各ルールについて動作してあるルールのＲＨＳの全ての暗黙条件が実際に知識ベースに存在することを保証する。
【０１９１】検証モジュール３４０４は、ＣＰＵ２０２にオブジェクト・リストについて最初に反復してオブジェクトがルールのＬＨＳに存在するかどうかを判定するように指令する。もしオブジェクトがルールのＬＨＳに存在しなければ、検証モジュール３４０４はＣＰＵ２０２に対してＲＨＳにおけるオブジェクトの存在がオブジェクトの新しい生成によるものかどうかを判定するように指令する。オブジェクトの新しい生成は、ルールのＬＨＳの暗黙条件ではあり得ないことを意味する。
【０１９３】もし暗黙条件が見出されると、挿入モジュール３４０６が実行されて、ＣＰＵ２０２に対してオブジェクトをルールに対するＲＥＴＥネットワークに挿入することを指令する。従って、挿入モジュール３４０６は、暗黙条件をルールのＬＨＳに加える。
【０１９４】本発明の詳細な記述におけるこれまでの論議は、与えられたルールに対するＲＥＴＥネットワークの処理および構築（各ルール毎に暗黙条件をＲＥＴＥネットワークに加えることを含む）と関連するものであった。
【０１９５】もし多くのルールが存在するものとすれば、多くの個々のＲＥＴＥネットワークが構築される。
【０１９６】発明の背景の章に論述されたように、ＲＥＴＥネットワークの１つの重要な特徴は、ルール間に共通のテスト節点を共用することである。この特徴は、時に最適化ＲＥＴＥネットワークと呼ばれる。従来のＲＥＴＥネットワーク構築システムにおいては、ＲＥＴＥネットワークの構築に際して最適化ステップは統合化ステップである。換言すれば、ルールが構成される時最適化が生起する。従来のＲＥＴＥ構築システムにおいては、ＲＥＴＥネットワークは最初に１つのルールに対して構築される。その後、次のルールに対するＲＥＴＥネットワークが構築される時、コンパイラは既に前に構成されたテストを構成することはない。これは、最適化が実際のＲＥＴＥネットワーク構成に組込まれる場合である。
【０１９７】対照的に、本発明の各ルールは、それ自体の個々のＲＥＴＥネットワークにより構築される。従って、本発明における最適化は、個々のステップが生起する時で、結果冗長テストが構成された時に生起する。本文に述べたように、個々のＲＥＴＥネットワークが各ルール毎に構築された後に最適化が生起する必要はない。本発明は、最適化を構成モジュール６０６と統合化できるようにするものである。
【０１９８】次に、本発明の最適化モジュール６１０について論述する。
【０１９９】従来のＲＥＴＥネットワーク・システムにおいては、与えられたＲＥＴＥテスト・モードが多数のＲＥＴＥ節点の直系の親（即ち、右側入力又は左側）として供される。このため、１つのルール内あるいは幾つかのルールにわたり複数回現れる同じ条件は、ＲＥＴＥネットワーク内で一回だけ表現されるに過ぎない。このようなＲＥＴＥ節点を数多く再使用することが最適化とされる。最適化は、処理速度およびメモリの利用を著しく改善することができる。
【０２００】本実施例においては、ＲＥＴＥネットワークは最適化により、あるいはこれによらずに構築することができる。最適化によらないＲＥＴＥネットワークの構築の利点は、結果として得られるＲＥＴＥネットワークがデバッグおよび理解が容易であることである。このため、ユーザが最初にルールを構築してデバッグし、次いでＲＥＴＥネットワークをより良好な性能となるように「調整」することを可能にする。
【０２０１】本例においては、最適化は各ルート節点を調べることにより達成される。これは、与えられたデータ・オブジェクトのタイプを含む全てのＲＥＴＥネットワークのテスト節点を見出すために行われる。このプロセスは、可能な統合化のための全ての候補となるＲＥＴＥ節点を識別する。
【０２０２】この統合化は次の２つの形態を取る。即ち、１．テストの組合わせ２．入力の共有テストは下記の如く組合わされる。即ち、１．変数名を共通にすること：与えられたデータ・オブジェクトのタイプに関する変数を含む全てのテストが、関連する変数が共通名を持つように変更される。
【０２０３】２．要素内テストを組合わせること：連続するａｌｐｈａ節点が合成されたテストを持つ１つのａｌｐｈａ節点に「纏められる」（例えば、２つのａｌｐｈａテスト、ｘ．ｃｏｌｏｒ＝’Ｂｌｕｅ’ａｎｄ ｘ．ｗｈｅｅｌ＝４，が色および車輪の双方をテストする１つのａｌｐｈａテストとなる）。
【０２０４】３．要素間テストを組合わせること：ｂｅｔａ節点の如き連続的な多重入力テスト節点が、合成されたテストを持つ１つのテスト節点に「纏められる」。このプロセスは、ａｌｐｈａテストに用いられるものと非常によく似ている。
【０２０５】入力は下記の如く共有される：１．同じＲＥＴＥテスト節点が識別されること２．見出された各セットの同じテスト節点毎に、１つの節点が保持され、他は削除される。ＲＥＴＥネットワークにおけるリンクが、削除された節点と接続された節点がこの時残りの節点と接続されるように変更される。
【図面の簡単な説明】
【図１】本発明の動作を示す高レベルのブロック図である。
【図２】本発明のアーキテクチャ環境２００を示す高レベルのブロック図である。
【図３】本発明のＲＥＴＥネットワーク構築モジュール２０６のアーキテクチャを示す高レベルのブロック図である。
【図４】本発明の構文解析モジュール３０２の動作を示すブロック図である。
【図５】本発明の与えられたルールに対する構文解析ツリー５００の典型的なデータ構造を示すブロック図である。
【図６】本発明の変換モジュール３０４のアーキテクチャを示すブロック図である。
【図７】本発明の変換モジュール３０４の動作を示すブロック図である。
【図８】本発明の否定モジュール６０２のアーキテクチャを示すブロック図である。
【図９】否定されたルールを示す構文解析ツリー９００に対するデータ構造を示すブロック図である。
【図１０】否定を排除するように本発明の下方否定モジュール９０２により修飾される図９の構文解析ツリー９００に対するデータ構造を示すブロック図である。
【図１１】冗長ＡＮＤ節点を有するルールを表わす構文解析ツリー１１００に対するデータ構造を示すブロック図である。
【図１２】冗長ＡＮＤ節点を除去するため本発明のＡＮＤ排除モジュール８０４により修正される図１１の構文解析ツリー１１００に対するデータ構造を示すブロック図である。
【図１３】本発明の論理和モジュール６０４のアーキテクチャを示すブロック図である。
【図１４】論理和モジュール６０４の動作を示すブロック図である。
【図１５】内部に論理和条件を持つルールを示す構文解析ツリー１５００に対するデータ構造を示すブロック図である。
【図１６】本発明のシャフラ・モジュール１３０４が如何にして構文解析ツリーの最も高い動作レベルへ論理和をプッシュするかを示すように修正された図１５の構文解析ツリー１５００に対するデータ構造を示すブロック図である。
【図１７】論理和を排除するように、２つの構文解析ツリーに本発明の排除モジュール１３０６により修正される図１６の構文解析ツリーに対するデータ構造を示すブロック図である。
【図１８】本発明の構成モジュール６０６のアーキテクチャを示すブロック図である。
【図１９】本発明の構成モジュール６０６の動作を示すブロック図である。
【図２０】本発明の構成モジュール６０６の動作を示す、図１９の続きのブロック図である。
【図２１】本発明の多重入力フロー・リスト・モジュール１８０２のアーキテクチャを示すブロック図である。
【図２２】本発明の多重入力フロー・リスト・モジュール１８０２の動作を示すフローチャートである。
【図２３】本発明の多重入力フロー・リスト・モジュール１８０２の動作を示す、図２２の続きのフローチャートである。
【図２４】事例のルールに対する抽象構文ツリーを示す図である。
【図２５】図２２の事例に対して多重入力フロー・リスト・モジュール１８０２により構成されるフローリストの内容を示す図である。
【図２６】図２２の事例に対するａｌｐｈａ節点モジュール１８０４により構成されるフローリストの内容を示す図である。
【図２７】ａｌｐｈａ再整列ルーチン１８０６のアーキテクチャを示す図である。（図２８乃至図３５は、図２４R>４における事例の抽象構文ツリーに対するＲＥＴＥネットワーク構造のシーケンスを示す。）
【図２８】ａｌｐｈａ再整列ルーチン１８０６により生じたａｌｐｈａ節点接続の結果を示す図である。
【図２９】ステップ１９１４における多重入力節点モジュール１８０８により処理される第１の否定テストの結果を示す図である。
【図３０】多重入力ハンドラ・モジュール１９１６により処理される第２のテストの結果を示す図である。
【図３１】多重入力ハンドラ・モジュール１９１６の連続結果を示す図である。
【図３２】多重入力ハンドラ・モジュール１９１６の連続結果を示す図である。
【図３３】多重入力ハンドラ・モジュール１９１６の連続結果を示す図である。
【図３４】多重入力ハンドラ・モジュール１９１６の連続結果を示す図である。
【図３５】多重入力ハンドラ・モジュール１９１６の連続結果を示す図である。
【図３６】ＲＥＴＥネットワーク暗黙条件モジュール６０８のアーキテクチャを示す図である。
【符号の説明】
１０１ 動作ブロック １０２ 動作ブロック
２００ コンピュータ環境 ２０２ ＣＰＵ
２０４ メモリ装置
２０６ ＲＥＴＥネットワーク・モジュール
２０８ Ｉ／Ｏデバイス ２１２ バッファ
２１４ ホスト・バス ２１６ システム・バス
３０２ 構文解析モジュール ３０４ 変換モジュール
４０２ 動作ブロック ４０４ 変換モジュール
５００ 構文解析ツリー ５０２ プロダクション節点
５０４ プロダクション節点 ５０８ ＡＮＤ節点
５１０ テストＡ節点 ５１２ テストＢ節点
５１４ テストＣ節点 ５１６ テストＤ節点
５１８ 数式節点 ５２４ シンボル・リスト節点
６０２ 否定モジュール ６０４ 論理和モジュール
６０６ 構成モジュール ６０８ 暗黙条件モジュール
６１０ 最適化モジュール ７０４ 動作ブロック
７０６ 動作ブロック ７０８ 動作ブロック
７１０ 動作ブロック ７１２ 動作ブロック
８０２ 否定モジュール ８０４ ＡＮＤ排除モジュール
８０６ ＯＲ排除モジュール ９００ 構文解析ツリー
９０４ ＮＯＴ節点 ９０６ ＡＮＤ節点
９０８ テストＡ節点 ９１０ ＯＲ節点
９１２ ＮＯＴ節点 ９１８ テストＤ節点
１００２ ＯＲ節点 １００４ ＮＯＴテストＡ節点
１００６ ＡＮＤ節点 １００８ 正規テストＤ節点
１１００ 構文解析ツリー １１０６ 冗長ＡＮＤ節点
１１１２ テストＡ節点 １１１４ テストＢ節点
１３０２ 発見モジュール １３０４ シャフラ・モジュール
１３０６ 排除モジュール １３０８ ザッパー・モジュール
１４０２ 動作ブロック １４０４ 動作ブロック
１４０６ 動作ブロック １５００ 構文解析ツリー
１５０２ プロダクション節点 １５０４ プロダクション節点
１５０６ プロダクション節点 １５０８ ＡＮＤ節点
１５１０ ＯＲ節点 １５１２ テストＥ節点
１５１４ テストＣ節点 １５１６ テストＤ節点
１６０２ ＯＲ節点 １６０４ ＡＮＤ節点
１６０６ ＡＮＤ節点 １７０２ ルール節点
１８０２ 多重入力フロー・リスト・モジュール
１８０４ ａｌｐｈａ節点モジュール
１８０６ ダングリングａｌｐｈａモジュール
１８０８ 多重入力節点モジュール １９０２ 動作ブロック
１９０４ 動作ブロック １９０６ 動作ブロック
１９１０ 動作ブロック １９１２ 動作ブロック
１９１４ 動作ブロック １９１６ 多重入力節点ハンドラ
２００２ 純粋に負のフロー・リスト・モジュール
２００４ 純粋に正のフロー・リスト・モジュール
２００６ 混成量化モジュール
２１０２ 負のフロー・リスト・モジュール
２１０８ 動作ブロック ２１１２ 動作ブロック
２１１８ 動作ブロック ２１２８ 動作ブロック
２２０２ プロダクション節点 ２２０６ テスト節点
２２０８ テスト節点 ２２１０ テスト節点
２２１２ テスト節点 ２２１４ テスト節点
２２１６ シンボル・リスト ２２１９ シンボル・リスト
２２２２ シンボル・リスト ２２２４ シンボル・リスト
２２２６ シンボル・リスト ２３０４ フロー・リスト・エントリ
２３０６ フロー・リスト・エントリ ２３０８ フロー・リスト・エントリ
２３１０ フローリスト・エントリ点
２３１４ 正のフロー・リスト・ブロック
２３１６ 負のフロー・リスト・ブロック２４０４ フローリスト・エントリ点
２４０６ フローリスト・エントリ点 ２４０８ ａｌｐｈａ節点
２４１０ ａｌｐｈａ節点 ２４１２ ａｌｐｈａ節点
２５０２ ａｌｐｈａ並替えモジュール ２５０４ ａｌｐｈａ接続モジュール
２６１０ ダングリングａｌｐｈａ節点 ２７０２ ＢＥＴＡテスト節点
２９０２ ＢＥＴＡテスト節点 ３００２ ＡＮＤ節点
３１０２ ＡＮＤ ＮＯＴ節点 ３２０２ ＡＮＤ節点
３４０２ オブジェクト・リスト・モジュール
３４０４ 検証モジュール ３４０６ 挿入モジュール
【特許請求の範囲】
【請求項１】１組の入力されたルールを有効なリーティ（ＲＥＴＥ）ネットワークに組織化する、リーティ・ネットワーク組織化方法であって、前記ルールの各々は、論理積、否定、論理和形式を用いて任意に特定され得るテスト条件を有しており、（ａ）各ルールに対してデータ構造を構築し、記憶装置内に前記データ構造を格納するステップと、（ｂ）前記データ構造を、論理積形式であり且つ他のデータ構造に変形するステップと、（ｃ）変形された前記データ構造から、用いられているオブジェクトを抽出し、フロー・リストを作成し、当該フロー・リストに、全ての異なる型の前記オブジェクトを格納するステップと、（ｄ）前記異なる型のオブジェクトの各々に対して、前記フロー・リスト上に前記リーティ・ネットワークを構成するテスト・ノードを構築するステップとを含むリーティ・ネットワーク組織化方法。
【請求項２】各ルールに対してデータ構造を構築する前記ステップ（請求項１（ａ））が、前記ルールの各テスト条件についてのシンボル・リストを生成し且つ格納するステップを含み、前記シンボル・マークが、与えられたテストに対する全ての用いられているオブジェクトを含んでいることを特徴とする請求項１記載のリーティ・ネットワーク組織化方法。
【請求項３】前記変形ステップ（請求項１（ｂ））が、（ａ）各ルールに対する前記データ構造を検査し、前記ルールから否定形式を除去するステップと、（ｂ）各ルールに対する前記データ構造を検査し、前記ルールから論理和形式を除去するステップとを含む請求項１記載のリーティ・ネットワーク組織化方法。
【請求項４】フロー・リストを作成する前記ステップ（請求項１（ｃ））が、正のフロー・リスト及び負のフロー・リストを作成するステップを含む請求項１記載のリーティ・ネットワーク組織化方法。
【請求項５】フロー・リストを作成する前記ステップ（請求項１（ｃ））が、（ａ）純粋に負の多重入力テストに含まれるオブジェクトを負の前記フロー・リストに付加するステップと、（ｂ）純粋に正の多重入力テストに含まれるオブジェクトを正の前記フロー・リストに付加するステップと、（ｃ）混成量化多重入力テストに含まれるオブジェクトを、その極性により正又は負の前記フロー・リストに付加するステップと、（ｄ）単入力テストに含まれるオブジェクト及びアルファ（ａｌｐｈａ）節点を、その極性により正又は負の前記フロー・リストに付加するステップとをさらに含む請求項４記載のリーティ・ネットワーク組織化方法。
【請求項６】前記異なる型のオブジェクトの各々に対し、前記フロー・リスト上に少なくとも１のテスト・ノードを構築する前記ステップ（請求項１（ｄ））が、（ａ）前記ルールの各テスト条件を検査するステップと、（ｂ）最初に、純粋に負に定量化されたテスト条件に対し、ベータ（ｂｅｔａ）節点を作成するステップと、（ｃ）テスト条件が純粋に正又は混成で定量化されていることに依存して、ベータ（ｂｅｔａ）節点又はベータ否定（ｂｅｔａ ｎｏｔ）節点を作成し、純粋に負のベータ（ｂｅｔａ）節点をアンド否定（ａｎｄ ｎｏｔ）節点で前記フロー・リストに接続するステップとを含む請求項１記載のリーティ・ネットワーク組織化方法。
【請求項７】暗黙条件を前記ルールに付加するステップを含む請求項１記載のリーティ・ネットワーク組織化方法。
【請求項８】暗黙条件を前記ルールに付加する前記ステップが、（ａ）前記ルールの右側を検査して、オブジェクトについての特有のリストを作成するステップと、（ｂ）前記ルールの左側を検査して、前記ルールの右側にあるルールが前記ルールの左側にあるかどうかを判定するステップと、（ｃ）前記ルールの左側にないオブジェクトを前記ルールの開始により生成すべきか判定するステップと、（ｄ）前記オブジェクトが前記ルールの開始により生成されない場合、前記ルールの左側に前記オブジェクトを付加するステップとを含む請求項７記載のリーティ・ネットワーク組織化方法。
【請求項１】１組の入力されたルールを有効なリーティ（ＲＥＴＥ）ネットワークに組織化する、リーティ・ネットワーク組織化方法であって、前記ルールの各々は、論理積、否定、論理和形式を用いて任意に特定され得るテスト条件を有しており、（ａ）各ルールに対してデータ構造を構築し、記憶装置内に前記データ構造を格納するステップと、（ｂ）前記データ構造を、論理積形式であり且つ他のデータ構造に変形するステップと、（ｃ）変形された前記データ構造から、用いられているオブジェクトを抽出し、フロー・リストを作成し、当該フロー・リストに、全ての異なる型の前記オブジェクトを格納するステップと、（ｄ）前記異なる型のオブジェクトの各々に対して、前記フロー・リスト上に前記リーティ・ネットワークを構成するテスト・ノードを構築するステップとを含むリーティ・ネットワーク組織化方法。
【請求項２】各ルールに対してデータ構造を構築する前記ステップ（請求項１（ａ））が、前記ルールの各テスト条件についてのシンボル・リストを生成し且つ格納するステップを含み、前記シンボル・マークが、与えられたテストに対する全ての用いられているオブジェクトを含んでいることを特徴とする請求項１記載のリーティ・ネットワーク組織化方法。
【請求項３】前記変形ステップ（請求項１（ｂ））が、（ａ）各ルールに対する前記データ構造を検査し、前記ルールから否定形式を除去するステップと、（ｂ）各ルールに対する前記データ構造を検査し、前記ルールから論理和形式を除去するステップとを含む請求項１記載のリーティ・ネットワーク組織化方法。
【請求項４】フロー・リストを作成する前記ステップ（請求項１（ｃ））が、正のフロー・リスト及び負のフロー・リストを作成するステップを含む請求項１記載のリーティ・ネットワーク組織化方法。
【請求項５】フロー・リストを作成する前記ステップ（請求項１（ｃ））が、（ａ）純粋に負の多重入力テストに含まれるオブジェクトを負の前記フロー・リストに付加するステップと、（ｂ）純粋に正の多重入力テストに含まれるオブジェクトを正の前記フロー・リストに付加するステップと、（ｃ）混成量化多重入力テストに含まれるオブジェクトを、その極性により正又は負の前記フロー・リストに付加するステップと、（ｄ）単入力テストに含まれるオブジェクト及びアルファ（ａｌｐｈａ）節点を、その極性により正又は負の前記フロー・リストに付加するステップとをさらに含む請求項４記載のリーティ・ネットワーク組織化方法。
【請求項６】前記異なる型のオブジェクトの各々に対し、前記フロー・リスト上に少なくとも１のテスト・ノードを構築する前記ステップ（請求項１（ｄ））が、（ａ）前記ルールの各テスト条件を検査するステップと、（ｂ）最初に、純粋に負に定量化されたテスト条件に対し、ベータ（ｂｅｔａ）節点を作成するステップと、（ｃ）テスト条件が純粋に正又は混成で定量化されていることに依存して、ベータ（ｂｅｔａ）節点又はベータ否定（ｂｅｔａ ｎｏｔ）節点を作成し、純粋に負のベータ（ｂｅｔａ）節点をアンド否定（ａｎｄ ｎｏｔ）節点で前記フロー・リストに接続するステップとを含む請求項１記載のリーティ・ネットワーク組織化方法。
【請求項７】暗黙条件を前記ルールに付加するステップを含む請求項１記載のリーティ・ネットワーク組織化方法。
【請求項８】暗黙条件を前記ルールに付加する前記ステップが、（ａ）前記ルールの右側を検査して、オブジェクトについての特有のリストを作成するステップと、（ｂ）前記ルールの左側を検査して、前記ルールの右側にあるルールが前記ルールの左側にあるかどうかを判定するステップと、（ｃ）前記ルールの左側にないオブジェクトを前記ルールの開始により生成すべきか判定するステップと、（ｄ）前記オブジェクトが前記ルールの開始により生成されない場合、前記ルールの左側に前記オブジェクトを付加するステップとを含む請求項７記載のリーティ・ネットワーク組織化方法。
【図１】
【図３】
【図２】
【図４】
【図６】
【図５】
【図７】
【図９】
【図８】
【図１０】
【図１３】
【図２５】
【図１１】
【図１２】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２６】
【図２３】
【図２４】
【図２７】
【図３６】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３】
【図２】
【図４】
【図６】
【図５】
【図７】
【図９】
【図８】
【図１０】
【図１３】
【図２５】
【図１１】
【図１２】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２６】
【図２３】
【図２４】
【図２７】
【図３６】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【特許番号】第２７４１７１５号
【登録日】平成１０年（１９９８）１月３０日
【発行日】平成１０年（１９９８）４月２２日
【国際特許分類】
【出願番号】特願平３−６３４４５
【出願日】平成３年（１９９１）３月２７日
【公開番号】特開平５−８８８９４
【公開日】平成５年（１９９３）４月９日
【審査請求日】平成３年（１９９１）３月２７日
【審判番号】平７−１３５０４
【審判請求日】平成７年（１９９５）６月２６日
【出願人】（９９９９９９９９９）インターナショナル・ビジネス・マシーンズ・コーポレイション
【合議体】
【登録日】平成１０年（１９９８）１月３０日
【発行日】平成１０年（１９９８）４月２２日
【国際特許分類】
【出願日】平成３年（１９９１）３月２７日
【公開番号】特開平５−８８８９４
【公開日】平成５年（１９９３）４月９日
【審査請求日】平成３年（１９９１）３月２７日
【審判番号】平７−１３５０４
【審判請求日】平成７年（１９９５）６月２６日
【出願人】（９９９９９９９９９）インターナショナル・ビジネス・マシーンズ・コーポレイション
【合議体】
[ Back to top ]