(57)【要約】  Ｑフレームワーク、または短縮してＱＦＸを、ＦＳＴに対する動作意味の保存を実現する汎用的な方法で効率的な木変換を実施するために提供する。このＦＳＴは、その表現内の動作情報をＦＳＴに対する多様な種類の表現にわたってサポートする。他の特徴として、ＱＦＸはまた、木変換の実施中に順序および非順序入れ子情報を保存すること、非決定性のデータ構造から決定性のデータ構造への変換をサポートすることも可能にし、動作意味を有する機械上での積演算を可能にする。
2010503932.tif 000002
【特許請求の範囲】
【請求項１】
コンピューティングシステム内の少なくとも１つの木データ構造を少なくとも１つのモジュール式有限状態トランスデューサ（ＭＦＳＴ）に変換する方法であって、
動作情報を定義するための動作意味を含む少なくとも１つの有限状態機械（ＦＳＭ）を表す少なくとも１つの木データ構造１４０ａを受信するステップ１００と、
前記少なくとも１つの木データ構造１４０ａにより表された任意の種類のＦＳＭモデルに対して、前記少なくとも１つの木データ構造１４０ａの前記動作情報を少なくとも１つのＭＦＳＴ１９０内に保存しつつ、前記少なくとも１つの木データ構造を前記少なくとも１つのＭＦＳＴ１９０に変換するステップ１２０と
を備えることを特徴とする方法。
【請求項２】
請求項１に記載の方法において、前記受信するステップ１００は、動作情報を定義するための動作意味を含む少なくとも１つの有限状態トランスデューサ（ＦＳＴ）を表す少なくとも１つの木データ構造１０４ａを受信するステップを含むことを特徴とする方法。
【請求項３】
請求項１に記載の方法において、前記変換するステップ１２０は、前記少なくとも１つの木データ構造１４０ａを、前記少なくとも１つの木構造１４０ａにより表されるＦＳＭモデルの種類に関係なく、前記少なくとも１つのＭＦＳＴ内に前記動作情報を保存する変換エンジン１８０により実装された拡張可能な予め定義された翻訳文法１７０で変換するステップを含むことを特徴とする方法。
【請求項４】
請求項１に記載の方法において、前記変換するステップ１２０は、前記少なくとも１つの木データ構造１４０ａを、前記少なくとも１つの木構造１４０ａにより表されるＦＳＭモデルの種類に関係なく、前記少なくとも１つの木データ構造１４０ａの順序入れ子情報および非順序入れ子情報の両方を保存する予め定義された翻訳文法１７０で変換するステップを含むことを特徴とする方法。
【請求項５】
請求項１に記載の方法において、前記受信するステップ１００は、動作情報を定義するための動作意味を含む前記少なくとも１つのＦＳＭを表す少なくとも１つの有向グラフデータ構造を受信するステップを含むことを特徴とする方法。
【請求項６】
請求項６に記載の方法において、前記受信するステップ１００は、動作情報を定義するための動作意味を含む前記少なくとも１つのＦＳＭを表す少なくとも１つのＸＭＬ（ｅｘｔｅｎｓｉｂｌｅ  ｍａｒｋｕｐ  ｌａｎｇｕａｇｅ）文書を受信するステップを含むことを特徴とする方法。
【請求項７】
請求項１に記載の方法において、前記変換するステップ１２０は、前記少なくとも１つのＭＦＳＴ１９０内に前記少なくとも１つの木データ構造１４０ａの前記動作情報を保存しつつ、少なくとも２つの木データ構造の積を取るステップを含むことを特徴とする方法。
【請求項８】
請求項１に記載の方法において、前記受信するステップ１００は、少なくとも１つの非決定性の木データ構造を受信するステップを含み、前記変換するステップ１２０は、前記少なくとも１つの非決定性のデータ構造を決定性のＭＦＳＴ１９０に変換するステップを含むことを特徴とする方法。
【請求項９】
請求項１に記載の方法を実施するためのコンピュータ実行可能命令を備えることを特徴とするコンピュータ可読媒体。
【請求項１０】
少なくとも１つの木データ構造を少なくとも１つのモジュール式有限状態トランスデューサ（ＭＦＳＴ）に変換するためのコンピューティングシステムであって、
少なくとも１つの有限状態機械（ＦＳＭ）を表す少なくとも１つの木データ構造１４０ａにおいて、前記少なくとも１つの木データ構造１４０ａは任意の種類のＦＳＭ記憶モデルで表される木データ構造と
前記少なくとも１つの木データ構造１４０ａを少なくとも１つのＭＦＳＴ１９０に変換するための変換エンジンコンポーネント１８０であって、前記少なくとも１つの木データ構造１４０ａに含まれる順序入れ子情報および非順序入れ子情報の両方をマッチングすることを含む変換エンジンコンポーネントと
を備えることを特徴とするコンピューティングシステム。
【請求項１１】
請求項１０に記載のコンピューティングシステムにおいて、前記少なくとも１つの木データ構造１４０ａは、少なくとも１つの有限状態トランスデューサ（ＦＳＴ）を表す少なくとも１つの有向グラフであることを特徴とするコンピューティングシステム。
【請求項１２】
請求項１０に記載のコンピューティングシステムにおいて、前記変換エンジンコンポーネント１８０は、前記少なくとも１つの木データ構造を、前記少なくとも１つのＭＦＳＴ１９０内に前記順序入れ子情報および前記非順序入れ子情報の両方を保存する予め定義された翻訳文法１７０を参照して、前記少なくとも１つのＭＦＳＴ１９０に変換することを特徴とするコンピューティングシステム。
【請求項１３】
請求項１０に記載のコンピューティングシステムにおいて、前記少なくとも１つの木データ構造１４０ａは、少なくとも１つの非決定性の木データ構造を含み、前記変換エンジンコンポーネント１８０は、前記少なくとも１つの非決定性のデータ構造を決定性のＭＦＳＴ１９０に変換することを特徴とするコンピューティングシステム。
【請求項１４】
コンピューティングシステムにおいて有向グラフデータ構造のモジュール式有限状態トランスデューサ（ＭＦＳＴ）への変換のための変換フレームワークであって、
コンピューティングシステムにおいて有限状態機械（ＦＳＭ）を表すための、様々な種類の複数の有向グラフデータ構造１４０ａを記憶する手段と
前記複数の有向グラフデータ構造１４０ａを、予め定義された木文法１７０に基づいて分析し、前記複数の有向グラフデータ構造１４０ａを、前記複数の有向グラフデータ構造１４０ａの動作意味情報を保存しつつ、少なくとも１つのＭＦＳＴ１９０に変換するトランスデューサ１５０と
を備えることを特徴する変換フレームワーク。
【請求項１５】
請求項１４に記載の変換フレームワークにおいて、前記トランスデューサ１５０は、少なくとも１つの制御フロー分析アルゴリズムを、任意の種類の有向グラフ表現にわたって前記複数の有向グラフデータ構造の前記動作意味情報を保存する前記複数の有向グラフデータ構造により表される前記有限状態機械（ＦＳＭ）上で実施することを特徴とする変換フレームワーク。
【請求項１６】
請求項１４に記載の変換フレームワークにおいて、前記トランスデューサ１５０は、前記複数の有向グラフデータ構造の変換に関連して特殊化された束縛処理を実施する変換エンジン１８０を含み、前記特殊化された束縛処理は、前記複数の有向グラフデータ構造１４０ａのパターンをマッチングするためのパターンマッチングプロセス中に前記動作意味情報に対する束縛を実施することを含むことを特徴とする変換フレームワーク。
【請求項１７】
請求項１４に記載の変換フレームワークにおいて、前記トランスデューサ１５０は、前記動作意味情報を保存しつつ、前記複数の有向グラフデータ構造１４０ａの内の１つの有向グラフデータ構造により定義されるように少なくとも１つのトランスデューサ定義を埋め込むことを特徴とする変換フレームワーク。
【請求項１８】
請求項１４に記載の変換フレームワークにおいて、前記トランスデューサ１５０は、起動レコード内のスロットに前記複数の有向グラフデータ構造１４０ａの変数束縛をコンパイルすることを特徴とする変換フレームワーク。
【請求項１９】
請求項１４に記載の変換フレームワークにおいて、前記トランスデューサ１５０は、前記複数の有向グラフデータ構造１４０ａにより表される前記有限状態機械（ＦＳＭ）のレジスタ分析を実施することを特徴とする変換フレームワーク。
【請求項２０】
請求項１４に記載の変換フレームワークにおいて、前記予め定義された木文法に従って有向グラフデータ構造を定義する、前記複数の有向グラフデータ構造の内の１つの有向グラフデータ構造を受信するためのインタフェースＩ１を、さらに備えることを特徴とする変換フレームワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に有限状態トランスデューサのような有限オートマトンに関し、より具体的にはその変換に関する。
【背景技術】
【０００２】
一般的な背景として、有限状態オートマトン（ＦＳＡ：finite state automata）としても知られる有限状態機械（ＦＳＭｓ：finite state machines）は、状態、遷移および動作から成るシステムの振る舞いのモデルである。ＦＳＭまたはＦＳＡを、状態図、状態遷移図、状態表、ラベル付き有向グラフ、木、等を用いて、様々な概念的な方法で表すことができる。これらは機械、またはオートマトンを構成する状態、遷移および動作の関係を保存する。異なる種類のＦＳＭまたはＦＳＡ、それらの間で等価なもの、および良く知られたそれらの一部の間で変換した様々なものがある。
【０００３】
今日では、幾つかのグラフトランスデューサおよび木トランスデューサが存在し、それらはＦＳＴによりモデル化した一連のシステムを、例えば、幾つかの種類の有向グラフデータ構造に対して変換して、新たなＦＳＴまたはＦＳＴ集合、例えば新たな有向グラフデータ構造を形成するという幾つかの態様を実現するが、そのようなシステムには様々な理由で限界がある。例えば、ＸＳＬＴ（The Extensible Stylesheet Language Transformation）はＸＭＬ文書の変換に用いられるＸＭＬベースの言語である。他のＸＭＬ文書の変換に用いると、その文書は変化せず、新たな文書が既存のＸＭＬ文書のコンテンツに基づいて作成される。プロセッサにより、その新たな文書を、ＨＴＭＬまたはプレーンテキストのような、標準的なＸＭＬシンタックスまたは別のフォーマットでシリアライズ（出力）することができる。ＸＳＬＴは、異なるＸＭＬスキーマ間のデータ変換、またはＸＭＬデータのウェブページまたはＰＤＦ文書への変換にしばしば用いられる。
【０００４】
基本的に、ＸＳＬＴにより、他のＸＭＬ文書の変換を記述するＸＭＬ文書を作成することができ、この他のＸＭＬ文書をさらに異なるフォーマットに翻訳することができる。しかしながら、ＸＳＬＴでは、ＦＳＴで表現できる動作意味（action semantics）を考慮することができない。これに関して、動作は「予め定義された状態にあるとき、或る特定の情報、例えば名前を認識すると、何らかの動作を実施する」であるかもしれない。しかしながら、そのような任意の動作をＦＳＴに対して定義できる範囲（extent）では、ＸＳＬＴはそのような任意の動作に対する呼び出しをその変換機能の一部として扱うことができない。さらに、ＸＳＬＴは補集合（complement）、積（intersect）、および和（union）の演算の全てを機械で実施することができない。
【０００５】
さらに、ＸＳＬＴのような既存の変換では、（例えば木構造として表される）順序入れ子および非順序入れ子（ordered and unordered nests）のような順序階層情報および非順序階層構造の両方を有するＦＳＭにマッチし、構成することもできない。或る特定の状況では、木変換時に順序情報のみの保存を扱うことができる幾つかのシステムがあり、変換時に非順序情報のみの保存を扱うことができる幾つかのシステムがあるが、ＸＳＬＴも、他のいかなる公知のシステムも、順序入れ子および非順序入れ子の両方を有向グラフまたは木構造にわたって保存できる変換機能を含まない。有限状態トランスデューサの最新の変換におけるこれらおよび他の不備は、以下でより詳細に説明する本発明の様々な例示的で非限定的な実施形態の説明から明らかになるであろう。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Aho et al. "Compilers: Principles, Techniques and Tools," Addison- Wesley (1986)
【非特許文献２】Hopcroft et al. "Introduction to Automata Theory, Language and Computation," Addison- Wesley (2000)
【発明の概要】
【課題を解決するための手段】
【０００７】
上述した最新技術状態の不備を考慮して、本発明はＦＳＴに対して効率的な木変換、例えば積、和、補集合、等を実施するための一般的なフレームワークを与える。このフレームワークでは、ＦＳＴに対する変換動作にわたって動作意味が保存される。このＦＳＴは、その表現内の動作情報を多様な種類の表現にわたってサポートする。ＦＳＴに対する効率的な木変換を実施するためのフレームワークにより、木変換の実施中に順序入れ子情報および非順序入れ子情報を保存することもでき、非決定性データ構造から決定性データ構造への変換をサポートすることができる。
【０００８】
１つの実施形態では、コンピューティングシステムにおける（１つまたは複数の）木構造を特定する（１つまたは複数の）データ構造を（１つまたは複数の）モジュール式有限状態トランスデューサ（ＭＦＳＴ：modular finite state transducer）に変換する方法を説明する。本方法には、木構造を特定するデータ構造を受信することが含まれる。この木構造は、動作情報を定義するための動作意味を含む有限状態トランスデューサ（ＦＳＴｓ）を表す。そのデータ構造により表される任意の種類の有限状態機械（ＦＳＭ）モデルに対して、本方法にはＭＦＳＴ内のデータ構造の動作情報を保存しつつデータ構造をＭＦＳＴに変換する能力が含まれ、その変換には任意の積、和、および補集合の演算、またはデータ構造上の任意の積、和、および補集合の演算に還元可能な任意の動作を実施することが含まれる。本発明の別の態様では、結果のＦＳＭから、その結果のＦＳＭが空でない入力を受理するかどうかを決定することができる。
【０００９】
ここに簡潔な概要を与えて、より詳細な説明および付属図面に従う例示的で非限定的な実施形態の様々な態様の基本的または一般的な理解を可能とすることを支援する。しかしながら、本概要が広汎的または包括的な概要であるとは意図していない。本概要の唯一の目的は、本発明の様々な例示的で非限定的な実施形態に関する幾つかの高レベルな概念を以下の「発明を実施するための形態」の前置きとして簡潔な形で提示することである。
【００１０】
本発明の、モジュール式有限状態トランスデューサに対する木文法の変換技術、および関連プロセスを、付属図面を参照してさらに説明する。
【図面の簡単な説明】
【００１１】
【図１Ａ】本発明が与える一般的な変換フレームワークでＦＳＴを変換して動作意味を保存するための例示的なプロセスを示す、例示的で非限定的なフロー図である。
【図１Ｂ】本発明が与える一般的な変換フレームワークでＦＳＴを変換して動作意味を保存するための例示的なプロセスを示す、例示的で非限定的なブロック図である。
【図１Ｃ】本発明に従ってＦＳＴを変換するための例示的なフレームワークおよび変換エンジンを示す、例示的で非限定的なブロック図である。
【図２Ａ】本発明の変換エンジンに関連して与えられる例示的なインタフェースを示す図である。
【図２Ｂ】本発明の実施形態に従って与えられるＰｕｓｈＥｎｖｉｒｏｎｍｅｎｔメソッドの例示的な動作を示す図である。
【図２Ｃ】本発明の実施形態に従って与えられるＰｏｐＥｎｖｉｒｏｎｍｅｎｔメソッドの例示的な動作を示す図である。
【図２Ｄ】本発明の変換エンジンに関連して与えられる別の例示的なインタフェースを示す図である。
【図２Ｅ】本発明により与えられる変換フレームワークで実装される、例示的で非限定的な∈−閉包アルゴリズムを示す図である。
【図２Ｆ】本発明により与えられる変換フレームワークで実装される、動作に対応するための部分集合構築技術の修正版を示す図である。
【図３Ａ】本発明に従って定義した拡張翻訳ケース集合のうち、ＡＣＴＩＯＮ−ＲＥＧＥＸのケースまたはαＴのケースの例示的な翻訳を示す図である。
【図３Ｂ】本発明に従って定義した拡張翻訳ケース集合のうち、ＢＩＮＤ−ＮＥＳＴのケースまたはｘ：［Ｔ］のケースの例示的な翻訳を示す図である。
【図３Ｃ】本発明に従って定義した拡張翻訳ケース集合のうち、ＢＩＮＤ−ＮＥＳＴ−ＲＥＰＥＡＴのケースまたはｘ：［Ｔ］＊｜＋｜？のケースの例示的な翻訳を示す図である。
【図３Ｄ】本発明に従って定義した拡張翻訳ケース集合のうち、ｘ：（Ｔ）のケースの例示的な翻訳を示す図である。
【図３Ｅ】本発明に従って定義した拡張翻訳ケース集合のうち、呼び出しを用いた拡張であるｘ：Ｔ  Ｒｅｆのケースの例示的な翻訳を示す図である。
【図３Ｆ】本発明に従って定義した拡張翻訳ケース集合のうち、呼び出しを用いた拡張であるｘ：Ｔ  Ｒｅｆ＊｜＋｜？のケースの例示的な翻訳を示す図である。
【図４Ａ】順序入れ子情報および非順序入れ子情報の両方をＦＳＴに対する変換にわたって保存するよう動作する本発明のＱＦＸに関連した、順序パターンまたはリストパターンを概念的に示す図である。
【図４Ｂ】順序入れ子情報および非順序入れ子情報の両方をＦＳＴに対する変換にわたって保存するよう動作する本発明のＱＦＸに関連した、非順序パターンまたは集合パターンを概念的に示す図である。
【図５Ａ】本発明により与えられる一般的な変換フレームワークでＦＳＴを変換して順序情報および／または非順序情報を保存するための例示的なプロセスを示す、例示的で非限定的なフロー図である。
【図５Ｂ】本発明により与えられる一般的な変換フレームワークでＦＳＴを変換して順序情報および／または非順序情報を保存するための例示的なプロセスを示す、例示的で非限定的なブロック図である。
【図５Ｃ】本発明に従って順序情報、またはラベル付け情報が存在下における、状態機械上での変換の例示的で非限定的な態様を示す図である。
【図５Ｄ】本発明に従って順序情報、またはラベル付け情報が存在下における、状態機械上での変換の例示的で非限定的な態様を示す図である。
【図５Ｅ】本発明に従って順序情報、またはラベル付け情報が存在下における、状態機械上での変換の例示的で非限定的な態様を示す図である。
【図５Ｆ】本発明に従って順序情報、またはラベル付け情報が存在下における、状態機械上での変換の例示的で非限定的な態様を示す図である。
【図５Ｇ】本発明に従って順序情報、またはラベル付け情報が存在下における、状態機械上での変換の例示的で非限定的な態様を示す図である。
【図５Ｈ】本発明に従って順序情報、またはラベル付け情報が存在下における、状態機械上での変換の例示的で非限定的な態様を示す図である。
【図５Ｉ】本発明に従って順序情報、またはラベル付け情報が存在下における、状態機械上での変換の例示的で非限定的な態様を示す図である。
【図５Ｊ】本発明に従って順序情報、またはラベル付け情報が存在下における、状態機械上での変換の例示的で非限定的な態様を示す図である。
【図５Ｋ】本発明に従って順序情報、またはラベル付け情報が存在下における、状態機械上での変換の例示的で非限定的な態様を示す図である。
【図５Ｌ】本発明に従って順序情報、またはラベル付け情報が存在下における、状態機械上での変換の例示的で非限定的な態様を示す図である。
【図６Ａ】本発明のＱＦＸに従う例示的な有限状態トランスデューサを示す図である。
【図６Ｂ】それに関連して本発明のＱＦＸが順序入れ子情報および非順序入れ子情報の両方を保存するよう動作する、例示的な順序入れ子および非順序入れ子を表す木データ構造を示す図である。
【図６Ｃ】それに関連して本発明のＱＦＸが順序入れ子情報および非順序入れ子情報の両方を保存するよう動作する、例示的な順序入れ子および非順序入れ子を表す木データ構造を示す図である。
【図７Ａ】本発明に従う例示的な状態機械のデータ構造として、状態遷移表としてＦＳＭの例示的なモデル化を示す図である。
【図７Ｂ】本発明に従う例示的な状態機械のデータ構造として、状態表としてＦＳＭの例示的なモデル化を示す図である。
【図８Ａ】状態遷移図によりＦＳＭの例示的なモデル化を示す図である。
【図８Ｂ】本発明に従う例示的な種類の状態機械のデータ構造として、Ｍｏｏｒｅモデルの例を表すトランスデューサを示す図である。
【図８Ｃ】本発明に従う例示的な種類の状態機械のデータ構造として、Ｍｅａｌｙモデルの例を表すトランスデューサを示す図である。
【図９】本発明を実装可能な例示的で非限定的なネットワーク環境を表すブロック図である。
【図１０】本発明を実装可能な例示的で非限定的なコンピューティングシステムまたは動作環境を表すブロック図である。
【発明を実施するための形態】
【００１２】
背景技術で述べたように、ＦＳＴおよび木データ構造、例えばコンピューティングメモリ内で表される傾向にあるラベル付き有向グラフを変換するための現行のフレームワークは十分に万能ではなく、あらゆる種類のＦＳＴにわたって変換する際に一部の種類の情報を保存することができない。例えば、現行のフレームワークでは一部のＦＳＴの動作意味、またはＦＳＴにより表される順序入れ子情報および非順序入れ子情報の両方を、多種のＦＳＴにわたって保存することができない。
【００１３】
従って、本発明では、ＦＳＴに対して動作意味の保存を実現する効率的な木変換を実施するための一般的なフレームワークを与え、本明細書ではそれをＱフレームワーク（またはＱＦＸ）と称する。このＦＳＴは、動作情報をその表現においてサポートする。本発明の効率的な木変換を実施するためのＱフレームワークにより、その効率的な木変換を実施する間に順序入れ子情報および非順序入れ子情報を保存することもできる。以下の説明から理解されるように、ＱＦＸにより多数の他の新規態様も可能となる。それらの態様は、定義された木文法および対応する翻訳に対する変換機能、トランスデューサ図、変換エンジンおよび変換エンジンにより実施される動作、翻訳ケース、および変数リネーミングを含む決定に関し、これらを以下でより詳細に説明する。本発明の１つの実施形態では、本発明により木表現または木表現集合上での少なくとも積、和、補集合および空集合テストの変換が可能である。
【００１４】
概要説明を続ける。モジュール式有限状態トランスデューサ（ＭＦＳＴ）は変換を実装する状態機械である。特に、ＭＦＳＴは「動作」と呼ばれるプログラム断片で拡大したＭＦＡである。共通動作には、環境に記憶された他のオブジェクトからオブジェクトを構築すること、環境内部で変数を束縛すること、およびパターンマッチング中に述語を実行することが含まれる。
【００１５】
これに関して、高レベルでは、本発明のＱフレームワーク（ＱＦＸ）によりプログラマは、動作付きの正規木文法を定義することができ、これらの文法をＭＦＳＴに翻訳することができる。ＱＦＸは、動作を定義するための任意のドメイン固有言語（ＤＳＬ）の使用をサポートする。さらに、ＱＦＸは変数束縛動作の特別なサポートを提供し、属性付き木文法と呼ばれる一種の木文法を生成する。以下の本発明の例示的で非限定的な実装により、ＱＦＸがどのように属性付き木文法をコンパイルして実行できるかを説明する。
【００１６】
これに関して、本発明のコンパイルアプローチは多くの理由で有利である。このコンパイルアプローチは、最適化および他の高性能アプローチを介して高性能な変換のためのサポートを提供する。このコンパイル技術によりランタイムコンポーネントを簡略化することもでき、その結果、単純な変換機械の作成を容易に実現することができる。以下の例示的で非限定的な詳細で説明するように、本明細書で説明するコンパイル技術により一連の明確な意味も与えられる。これに関して、本発明のコンパイルアプローチは、プログラマが、合成および副作用を含めて、木文法の意味を推論することを容易にする。
【００１７】
一般に、図１Ａのフロー図により示されるように、本発明により、コンピューティングシステムにおける動作意味情報を有する多様な種類の有限状態トランスデューサ（ＦＳＴ）データ構造を１００で受信し、１０５でフレームワークの変換エンジンをＦＳＴに適用するための一般的なフレームワークが可能となる。次いで、以下でより詳細に説明するように、１１０でＦＳＴの分析および変換が任意の種類のＦＳＴ表現に対する予め定義された木文法に従って起こる。その結果、１１５でＦＳＴが変換されてＭＦＳＴを生成する。ＭＦＳＴはとりわけ、例えば積、補集合、および和の演算のうち任意のものを複数のＦＳＴ上で実施する間にＦＳＴの動作情報を保存し、順序入れ子情報および非順序入れ子情報を保存し、非決定性のＦＳＴの決定性のものへの変換を可能とする。
【００１８】
図１Ｂは上記プロセスに一般に対応するブロック図であり、本発明の木文法により可能となる１つの態様を示す。変換フレームワーク１２５は、動作意味を含む１つまたは複数のＭＦＳＴ１２０を受信し、積、和および補集合の変換演算（および／または合成を伴う、他のブール演算子）のうち任意のものに従ってＭＦＳＴを変換し、動作意味情報は出力１３０において保存される。
【００１９】
図１Ｃは、本発明に従ってＦＳＴを変換するための例示的なフレームワークおよび変換エンジンを示す例示的で非限定的なブロック図を示す。示すように、本発明に従って与えたＱフレームワーク１５０と相互作用するプロセッサＰを有するコンピューティング環境内であれば、多種の有限状態機械の表現を、コンピューティングシステムにおいて、様々な記憶要素１４０ａ〜１４０ｎで見つけることができる。一般に、Ｑフレームワーク１５０は、ＭＦＳＴ１９０に変換および生成するための変換エンジン１８０を介して、有限状態機械表現１４０ａ〜１４０ｎの部分集合を受信する。この変換では、属性付き木文法１７０を参照して分析１６０を有限状態機械表現１４０ａ〜１４０ｎの部分集合上で実施し、有限状態械表現１４０ａ〜１４０ｎの部分集合をＭＦＳＴ１９０に最も良く変換する方法を決定する。インタフェースＩ１もコンピューティング環境内で与えられ、予め定義された木文法１７０に基づいて、且つその文法で使用するために、有向グラフデータ構造を受信または定義する。
【００２０】
従って、様々な非限定的な実施形態において、本発明が、コンピューティングシステム内の木データ構造のモジュール式有限状態トランスデューサ（ＭＦＳＴ）への変換を可能にする。その木データ構造はＦＳＭ（例えば、ＦＳＴ）を表現し、ＦＳＭに関する動作情報を定義する動作意味を含み、その動作情報は変換プロセスを通して保存される。１つの実施形態では、木データ構造、例えば有向グラフデータ構造、ＸＭＬ文書、等により表現される任意の種類のＦＳＭモデルに対して、本発明では、動作情報を保存しつつその木データ構造をＭＦＳＴに変換する。拡張可能な予め定義された翻訳文法を変換エンジンにより実装する。この変換エンジンは、木データ構造により表現されるＦＳＭモデルの種類に関係なく動作情報を保存し、木データ構造の順序入れ子情報および非順序入れ子情報の両方を保存し、非決定性のデータ構造を決定性のＭＦＳＴに変換する。有利に、本発明は、或る種のＦＳＭの補集合、積および和を変換プロセスの一部として扱うことができる。
【００２１】
さらなる実施形態では、本発明は、有向グラフのモジュール式有限状態トランスデューサ（ＭＦＳＴ）への変換を実施するためのコンポーネントおよびソフトウェアを含むＱフレームワーク（ＱＦＸ）を含む。このコンポーネントおよびソフトウェアは、コンピューティングシステム内の任意の種類の有向グラフデータ構造を分析し、その分析に基づいて、有向グラフデータ構造の動作意味を保存しつつ有向グラフデータ構造をＭＦＳＴに変換する能力を有する。ＱＦＸは、有向グラフデータ構造により表現されるＦＳＭｓ（finite state machines）上で、その有向グラフデータ構造の動作意味情報を任意の種類の有向グラフ表現にわたって保存する方法で制御フロー分析アルゴリズムを実施する。
【００２２】
さらに、ＱＦＸは、有向グラフデータ構造の変換に関連して特殊化された束縛処理を実施する変換エンジンを含む。この特殊化された束縛処理には、パターンマッチング中に動作意味情報に対する束縛を実施することが含まれる。さらに、変換には、この複数の有向グラフデータ構造の内の１つの有向グラフデータ構造により定義される少なくとも１つのトランスデューサ定義を埋め込む能力が含まれる。また、変換には、その有向グラフデータ構造の変数束縛を既存の起動レコード内のスロットにコンパイルすることも含まれ、有向グラフデータ構造により表現されるＦＳＭのレジスタ分析も含まれる。本発明の上記効果および利点を実現する本発明により定義された文法を、動作意味情報を含む有向グラフデータ構造を記述するＣ＃のインタフェースのようなソフトウェアインタフェースを介して実装することができる。
【００２３】
さらに、様々な実施形態において、本発明は変数束縛を伴う字句解析を実装する。さらに、ＱＦＸは拡張可能であり、異なる変換プロバイダとの効率的な相互運用性を提供する。さらに、本発明は、コンパイル性能と実行性能との間のトレードオフに対する制御を実装する。即ち、実装が、コストの高いコンパイルをせずにパターンを解釈し、繰り返し使用する特定のパターンをコンパイルすることができる。最後に、可変粒度のコンテニュエーションポイントを提供することでランタイムコンポーネントはＱＦＸスケジューリング規則と関係付けられて、それにより同一メカニズムの使用が単一または複数の結果を与えることを可能にする。
【００２４】
以下の下表１の簡略化した木文法構文は、本発明に従ってコンパイルプロセスに関連して利用できる例示的で非限定的なモデルである。
【００２５】
【表１】
2010503932.tif 000003
【００２６】
上記文法では、適用できる例示的な演算子の優先順位はＲＥＰＥＡＴ＞ＢＩＮＤ＞ＳＥＱＵＥＮＣＥ＞ＡＮＤ＞ＯＲである。以下の説明では、ｘを用いて変数を表し、ｂを用いてベース記号（型またはベース型の値）を表し、Ｔを用いてＭＦＳＴを表し、αを用いて動作を表し、Ｔ  Ｒｅｆを用いてＴへの参照を表す。
【００２７】
正規表現のＮＦＡへの翻訳の従来技術に関して、およびＮＦＡの決定化に関して、そのような翻訳技術の概説を、例えば、「非特許文献１」または「非特許文献２」で一般的に見出すことができる。上記の従来技術に対する改善として、ＱＦＸに従い、本発明の技術を介して定義された正規木文法を、動作によりＭＦＳＴに拡張することができる。
【００２８】
また、非特許文献１で議論される翻訳では、上記文法から、以下のケース、すなわち、ＯＲ、ＡＮＤ、ＢＡＳＥ、ＳＥＱＵＥＮＣＥ、ＲＥＰＥＡＴおよびＲＥＦを網羅すると主張しているが、本発明に従って（１）動作、（２）入れ子、および（３）変数束縛を扱うには、以下の表２に示すように記録される、以下のさらなるケースに対して翻訳が望まれる。
【００２９】
【表２】
2010503932.tif 000004
【００３０】
ＡＣＴＩＯＮ−ＲＥＧＥＸおよびＲＥＧＥＸ−ＡＣＴＩＯＮのケースは、一般的な動作を伴う木文法のコンパイルを扱う。ＢＩＮＤ−ＲＥＦ、ＢＩＮＤ−ＧＲＯＵＰ、ＢＩＮＤ−ＮＥＳＴ、ＢＩＮＤ−ＲＥＦ−ＲＥＰＥＡＴ、ＢＩＮＤ−ＧＲＯＵＰ−ＲＥＰＥＡＴ、およびＢＩＮＤ−ＮＥＳＴ−ＲＥＰＥＡＴのケースは変数束縛のコンパイルを扱う。ＢＩＮＤ−ＮＥＳＴのケースはまた、正規表現を入れ子の正規表現に拡張する。
【００３１】
表１の簡略化された木文法構文には示されないが、非終端定義は本発明に従って正規パラメータおよび型パラメータの両方を有することができる。１つの実施形態では、コンパイラは正規パラメータを継承属性として扱い、ＢＩＮＤ−ＲＥＦおよびＢＩＮＤ−ＲＥＦ−ＲＥＰＥＡＴ翻訳を用いて型パラメータを扱う。
【００３２】
本発明に従うＭＦＳＴの変換を、そのＭＦＳＴを定義する状態機械図を用いて例示的な方法で説明することができる。図においては、遷移は次のようにラベル付けされる。すなわち、ｂを消費される入力記号としαを実施される動作としてｂ／αである。∈／αは入力を消費しないが何らかの動作を実施する遷移を表す。この遷移クラスを動作遷移と称する。トランスデューサを実行する際、本発明の１つの実施形態では、状態からの動作遷移に対して、その状態からの全ての入力消費遷移よりも低い優先度を割り当てる最大進行ポリシー（ｍａｘｉｍａｌ  ｐｒｏｇｒｅｓｓ  ｐｏｌｉｃｙ）を実装する。図において、特殊記号「［」と「］」は夫々、入力集合の開始と終了を表す。変数束縛をｘ＝ｅｘｐｒのように書き、トランスデューサの現在の環境に適用する。
【００３３】
反復演算子、即ち、「＋」、「＊」、および「？」に関して、リストを用いて結果の集合が蓄積されるが、例えば対応する結合演算子を用いることで、任意の集合型への結果の蓄積を網羅するようにこのメカニズムを一般化することができる。
【００３４】
本発明の様々な実施形態によると、ＢＩＮＤ−ＲＥＦおよびＢＩＮＤ−ＲＥＦ−ＲＥＰＥＡＴのケースを２つの方法、即ちインラインおよび呼び出しで拡張する。インライン拡張は空間と交換して時間を確保するので、本発明の非限定的な１つの実装では、ＭＦＳＴを決定化する際はインライン拡張が好ましい。一般に、呼び出し拡張は３つのケースで用いられる。第１のケースは、解釈するためにコンパイルする場合である。このケースでは、コンパイラはＭＦＳＴを決定化せず、全ての参照を呼び出しとして拡張する。第２のケースは再帰である。例えば、Ｔ  Ｒｅｆが開始記号を参照する場合、コンパイラはその参照を呼び出しとして拡張する。第３のケースは拡張である。Ｔ  Ｒｅｆが曖昧なＭＦＳＴを参照する場合、コンパイラはその参照を呼び出しとして拡張する。
【００３５】
本発明のコンパイラは、木文法を、変換エンジン（ＸＥ）と呼ばれる仮想マシン用の命令に翻訳する。ＸＥは、以下をサポートする。すなわち、（１）トランスデューサの定義および動作、（２）他の変換エンジンインスタンスへの制御の転送（Transfer）、ならびに（３）環境の管理（Management）および環境へのアクセスである。
【００３６】
第１のカテゴリに関して、状態機械の定義を存続し解釈するための技術が、知られている。従って、以下では、第２および第３の命令カテゴリ、即ちＴｒａｎｓｆｅｒおよびＭａｎａｇｅｍｅｎｔを実現するための例示的で非限定的なメソッドを説明する。本発明によると、これらの命令を、１組のインタフェースでメソッドとして定義する。コンパイラはこれらのインタフェースに対する呼び出しを直接生成せず、コンパイラはＸＥの実装により解釈されるＸＥ命令を生成する。
【００３７】
本発明に従って与えられるＸＥＣｏｎｔｒｏｌＩｎｓｔｒｕｃｔｉｏｎｓインタフェースを図２Ａの例示的な擬似コード２００に示す。ＸＥＣｏｎｔｒｏｌＩｎｓｔｒｕｃｔｉｏｎｓインタフェース２００は、現在のＸＥインスタンスを、暗黙的なオペランド、即ち、ＸＥＣｏｎｔｒｏｌＩｎｓｔｒｕｃｔｉｏｎｓインタフェース２００の「ｔｈｉｓポインタ」として有する。
【００３８】
ＱＦＸの例示的な実施形態で与えられるＭａｒｋメソッドは、現在の位置をマークスタック上の入力項に記録する。ＹｉｅｌｄメソッドはマークスタックからマークＭをポップして、Ｍと現在の位置との間の入力項部分を返す。１つの実施形態では、ＱＦＸはこれらのメソッドをトラバーサルプロバイダ（ｔｒａｖｅｒｓａｌ−ｐｒｏｖｉｄｅｒ）インタフェースを通したインダイレクションにより実装する。そのようなアプローチでは、有利に、項の表現とトラバーサルを項の変換から分離する。トラバーサルプロバイダは従って、ＱＦＸ変換フレームワークを任意の特定のデータ表現に適用することで、トラバーサルを実装することができる。
【００３９】
本発明に従って与えられるＣａｌｌメソッドは新たな環境Ｅを生成し、コンテニュエーションおよびｃａｌｌｉｎｇＥｎｖｉｒｏｎｍｅｎｔをＥに保存する（例えば、図２ＡのＸＥＣｏｎｔｒｏｌＩｎｓｔｒｕｃｔｉｏｎｓインタフェース２００を参照）。Ｃａｌｌメソッドは次いで、制御をターゲットに転送するコンテニュエーションを返す。ＣａｌｌメソッドはまたＭａｒｋメソッドを呼び出して、現在の入力位置を保存する。Ｒｅｔｕｒｎメソッドはこの動作を反転させ、マッチした項を現在の環境（Ｅ）にＹｉｅｌｄメソッドを用いて保存するよう動作する。即ち、Ｅ．ｔｅｒｍ＝Ｙｉｅｌｄ（）である。次いで、ＲｅｔｕｒｎメソッドはＥを変数ｃａｌｌｉｎｇＥｎｖｉｒｏｎｍｅｎｔ．ｒｅｓｕｌｔに記憶し、最後にＲｅｔｕｒｎメソッドは、コンテニュエーションを返す。呼び出し時、コンテニュエーションは、現在の環境をｃａｌｌｉｎｇＥｎｖｉｒｏｎｍｅｎｔに設定し、呼び出し状態から継続する。
【００４０】
ＮｅｗＥｎｖｉｒｏｎｍｅｎｔメソッドは、本発明に従って新たな環境を生成する。さらに、図２Ｂおよび２Ｃの例示的で非限定的な擬似コード２１０および擬似コード２２０は夫々、ＰｕｓｈＥｎｖｉｒｏｎｍｅｎｔメソッドおよびＰｏｐＥｎｖｉｒｏｎｍｅｎｔメソッドの動作の概要を示す。
【００４１】
ＰｕｓｈＥｎｖｉｒｏｎｍｅｎｔメソッドは現在の環境を内部環境スタック上に保存し、例えばｔｅｍｐＥｎｖ．ＰｕｓｈＥｎｖｉｒｏｎｍｅｎｔと名付けられた新たな環境を生成し、次いでｔｅｍｐＥｎｖをｖａｒｉａｂｌｅＮａｍｅに束縛し、現在の環境をｔｅｍｐＥｎｖに設定して、Ｍａｒｋを呼び出して、現在の入力位置を記録する。
【００４２】
ＰｏｐＥｎｖｉｒｏｎｍｅｎｔメソッドは、直前のＭａｒｋ呼び出し後にマッチした部分項を変数「ｔｅｒｍ」に記録する。ＰｏｐＥｎｖｉｒｏｎｍｅｎｔは次いで現在の環境を環境スタックから復元する。ＰｏｐＥｎｖｉｒｏｎｍｅｎｔはポップした環境を保存しない。なぜならば、ＰｕｓｈＥｎｖｉｒｏｎｍｅｎｔへの対応する呼び出しが既に、ポップした環境を束縛しているからである。
【００４３】
さらに、Ｅｘｅｃメソッドは、本発明に従って動作を実行する。ＱＦＸの例示的な実装では、ＡｃｔｉｏｎＲｅｆｅｒｅｎｃｅは、別々に存続しロードされるメソッドポインタのテーブルに対応するテーブル索引である。
【００４４】
本発明に従って与えられるＸＥＥｎｖｉｒｏｎｍｅｎｔＩｎｓｔｒｕｃｔｉｏｎｓインタフェースを、図２Ｄの例示的な擬似コード２３０に示す。ＸＥＥｎｖｉｒｏｎｍｅｎｔＩｎｓｔｒｕｃｔｉｏｎｓインタフェース２３０は、環境のインスタンスを、明示的なオペランド、即ち、ＸＥＥｎｖｉｒｏｎｍｅｎｔＩｎｓｔｒｕｃｔｉｏｎｓインタフェース２３０の「ｔｈｉｓポインタ」として有する。
【００４５】
ＣｈｉｌｄＥｎｖメソッドは、親がｔｈｉｓポインタの「ｔｈｉｓ」である新たな入れ子の環境を生成する。Ｂｉｎｄメソッドは変数を値に束縛し、束縛が成功した場合に真を返す。例示的で非限定的な例では、ｖａｒｉａｂｌｅＮａｍｅが現在の束縛を有する場合、Ｌｏｏｋｕｐメソッドは、値をその束縛に設定し、真を返す。そうでなければ、偽を返す。
【００４６】
本発明の変換エンジン（ＸＥ）の動作は、状態遷移への優先度の割り当てをサポートする。コンパイラは、夫々の状態で可能な遷移を順序付けすることで、パターン間の選択から生ずる曖昧さに対処する。１つの非限定的な実施形態では、通常入力での全ての遷移は、ワイルドカードの遷移より優先し、ワイルドカード遷移は動作遷移より優先する。また、これらの優先度グループ内で、プログラマは任意に優先度を特定の遷移に割り当てることができる。
【００４７】
ＸＥのインスタンスは、状態から継続するためにそれらが全ての適用可能な遷移を使用するモードをサポートすること、およびコンテニュエーションを優先順に待ち行列に入れることにより、複数の結果の生成に対処することができる。
【００４８】
図３Ａは、本発明に従って定義された拡張翻訳ケース集合のαＴケースの例示的な翻訳を示す。より具体的には、図３Ａは、ＡＣＴＩＯＮ−ＲＥＧＥＸケースの翻訳を示す。この翻訳は、ＮｅｓｔｅｄＲｅｇｅｘ  ＳＥＱＵＥＮＣＥケースに対する翻訳のアプリケーションである。ＲＥＧＥＸ−ＡＣＴＩＯＮケースはＳＥＱＵＥＮＣＥ翻訳の直接的なアプリケーションであるので示していない。図では、丸ＳＣｌ、ＳＣ２およびＳＣ３は開始状態を表し、丸ＩＣｌ、ＩＣ２およびＩＣ３は中間状態を表し、二重丸ＤＣｌ、ＤＣ２およびＤＣ３は受理状態を表す。
【００４９】
図３Ｂは、ＢＩＮＤ−ＮＥＳＴケース、ｘ：［Ｔ］の例示的な翻訳を示す。図３Ｂでは、メソッドＰｕｓｈＥｎｖｉｒｏｎｍｅｎｔおよびＰｏｐＥｎｖｉｒｏｎｍｅｎｔは夫々、ＰｕｓｈＥｎｖおよびＰｏｐＥｎｖと短縮される。開始状態ＳＣ４、中間状態ＩＳ３およびＩＳ４、ならびに受理状態ＤＣ４は、図３Ｂにより定義される機械の異なる状態を示す。［を読むと、機械は新たな環境Ｅを作成してそれをｘに束縛する。機械は次いで現在の環境Ｃをプッシュし、Ｅを現在の環境とする。機械はまた現在の入力位置をマークする。次いで、機械はＴを実行してＥ内の変数を束縛する。Ｔの実行中、変数束縛がＥ内で蓄積する。機械は次いで［Ｔ］によりマッチした項をＥ．ｔｅｒｍに記憶し、Ｃを現在の環境として復元する。
【００５０】
図３Ｃは、ＢＩＮＤ−ＮＥＳＴ−ＲＥＰＥＡＴケース、ｘ：［Ｔ］＊｜＋｜？の例示的な翻訳を示す。図３Ｃは、コンパイラが繰り返しを伴う入れ子の正規表現を翻訳する方法を示す。開始状態ＳＣ５、中間状態ＩＳ５、ＩＳ６、ＩＳ７およびＩＳ８、ならびに受理状態ＤＣ５は、図３Ｃにより定義される機械の異なる状態を示す。状態ＩＳ５、ＩＳ６、ＩＳ７およびＩＳ８により定義されるトランスデューサの内部部分は図３Ｂの機械と同じであることが分かる。この機械を、開始状態ＳＣ５および受理状態ＤＣ５を含むコンテナ状態機械により囲む。コンテナ機械の目的は、環境を変数ｘに束縛したリストとして蓄積することである。
【００５１】
これに関して、トランスデューサは先ず空リストを作成してそれをｘに束縛する。次に、トランスデューサは、［Ｔ］の実行結果をｘに付加する。実行ステップおよび付加ステップは、「この弧を「＊」および  「？」に対して使用せよ」とマークされた前方∈遷移により、任意とされる。実行ステップおよび付加ステップを、「この弧を「＊」および「＋」に対して使用せよ」とマークされた後方∈遷移のトラバーサルにより、任意に繰り返すことができる。
【００５２】
図３Ｄはｘ：（Ｔ）ケースの例示的な翻訳を示す。開始状態ＳＣ６、中間状態ＩＳ９およびＩＳ１０、ならびに受理状態ＤＣ６は、図３Ｄにより定義される機械の異なる状態を示す。図３Ｄはトランスデューサを示し、このトランスデューサは、図３Ｄ内のＴへの遷移およびＴからの遷移が入力記号を消費しないことを除いて、図３ＢのＢＩＮＤ−ＮＥＳＴケースに対するトランスデューサと同様である。
【００５３】
図３Ｅは、呼び出しを用いた拡張であるｘ：Ｔ  Ｒｅｆケースの例示的な翻訳を示す。図３Ｅは、開始状態ＳＣ７、中間状態ＩＳ１１および受理状態ＤＣ７を含む機械を定義し、ｘ：Ｔ  Ｒｅｆを拡張するための呼び出しストラテジーの使用を示す。第１の遷移では、以下の例示的で非限定的な擬似コードに対する短縮形である呼び出し命令Ｃａｌｌ（Ｔ）を実行する。
Ｃａｌｌ（Ｔ，ＣｕｒｒｅｎｔＣｏｎｔｉｎｕａｔｉｏｎ，ＣｕｒｒｅｎｔＥｎｖｉｒｏｎｍｅｎｔ）
【００５４】
呼び出しポイントでのＣｕｒｒｅｎｔＣｏｎｔｉｎｕａｔｉｏｎは、遷移矢印の終端での中間状態ＩＳ１１である。呼び出されたトランスデューサはその環境を変数の結果で返す。最後に、呼び出し側のトランスデューサはその結果をｘに束縛する。
【００５５】
図３Ｆは、呼び出しを用いた拡張であるｘ：Ｔ  Ｒｅｆ＊｜＋｜？の例示的な翻訳を示す。図３Ｆは、開始状態ＳＣ８、中間状態ＩＳ１２およびＩＳ１３、ならびに受理状態ＤＣ８を含む機械を定義し、呼び出しに適用される繰り返しコンテナを示す。このトランスデューサは、図３Ｃのトランスデューサと同様であり、Ｔのインライン拡張の代わりに内部トランスデューサとしてのＴへの呼び出しがある。
【００５６】
図３Ａから３Ｆのここまでで説明していない翻訳ケースは、ＢＩＮＤ−ＧＲＯＵＰ−ＲＥＰＥＡＴおよびＢＩＮＤ−ＲＥＦケースのインライン版である。ＢＩＮＤ−ＧＲＯＵＰ−ＲＥＰＥＡＴは図３Ｆの繰り返しコンテナを、図３Ｄに示すＢＩＮＤ−ＧＲＯＵＰに対するトランスデューサと結合する。さらに、ＢＩＮＤ−ＲＥＦのインライン版およびＢＩＮＤ−ＲＥＦＲＥＰＥＡＴケースは夫々、ＢＩＮＤ−ＧＲＯＵＰおよびＢＩＮＤ−ＧＲＯＵＰ−ＲＥＰＥＡＴケースと同じである。
【００５７】
決定化は、どのようにして部分集合の構築技術を定式化して、本発明に従って動作を有することができる遷移を説明するか描写する。本発明によると、動作の、遷移および状態両方との関連付けが、可能である。決定性のトランスデューサを遷移上のみの動作で構築することができるが、そのような選択は、アルゴリズムはより複雑にする一方で、効率性に対して直接的であり、動作を状態および遷移の両方に対して記憶する。
【００５８】
一部の詳細を簡略化し、図２Ｅは、ＱＦＸで実装される例示的で非限定的な∈−閉包アルゴリズム、即ち、Ｓｔａｔｅ〈Ｔ〉．ＥＣｌｏｓｕｒｅ＋を示す。本方法は、∈遷移上での動作を蓄積するように拡大される。図２Ｅの例示的な疑似コード２４０内の（Ａｌ）および（Ａ２）とマークされたラインは、∈−閉包の構築中にトラバースしたイプシロン遷移上の全ての動作をリスト「ａｃｔｉｏｎｓ」に保存する。全体の決定化アルゴリズムは、これらの保存された動作を、∈−閉包から構築されたＤＦＳＴ（deterministic finite state transducer）状態に転送する。
【００５９】
図２Ｆは、ＱＦＸにおいて例示的な方法で実装されるような、動作に対応するように修正された部分集合の構築、即ち、ＮＦＡ〈Ｔ〉．ＳｕｂｓｅｔＣｏｎｓｔｒｕｃｔｉｏｎを示す。ラベル（Ｂ１）から（Ｂ６）は、動作に対応するように修正または追加した、図２Ｆの例示的な疑似コード２５０のラインをマークする。ライン（Ｂ１）および（Ｂ２）は、ソース状態（ｓｒｃ）が記号で遷移を有する全ての状態を発見する。これらのラインはさらに夫々の遷移の動作をｓｙｍＡｃｔｉｏｎｓ内に蓄積する。ライン（Ｂ３）および（Ｂ４）は、∈遷移に対して同様の関数を実施する。最後に、ライン（Ｂ５）は、ｓｙｍＡｃｔｉｏｎｓをｓｒｃ状態とｄｓｔ状態の間のＤＦＳＴ遷移に加え、ライン（Ｂ６）はｅｐｓＡｃｔｉｏｎｓをｓｒｃ状態に加える。次いでこれらの動作を、ｓｒｃへの遷移完了時に実施する。１つの実施形態において、これらのアルゴリズムでは、動作は、現在の環境内の変数の束縛以外の副作用を有さないと仮定している。
【００６０】
全体として、有利に、本発明に従うこの決定化法が以下の保証を実現する。
１．動作α１およびα２の組が同じ作成規則の要素である場合、動作α１およびα２は辞書順に起動される。
２．動作α１が作成規則ｐ１の一部であり動作α２が作成規則ｐ２の一部であり、ｐ１≠ｐ２である場合、次いでトランスデューサはα１およびα２のいずれかを起動するだろう。ｐ１およびｐ２が接頭語ｐｒｅを共有し、ｐｒｅがｐ１内にα１を含み、ｐｒｅがｐ２内にα２を含む場合、トランスデューサは両方の動作を起動することのみできる。
３．文法に対する開始定義内で、夫々の作成規則の最終動作が副作用を有する可能性がある。１つの実施形態では、トランスデューサは全ての他の動作が完了するまでこの動作を実行しない。
【００６１】
これに関して、属性付き木文法は、プログラマが上の保証を利用することを可能にする。属性文法を用いると、プログラマは現在の環境内部で全ての動作を変数束縛として表現することができる。そのような動作は２つの形態のうち１つ、即ち、ｘ：Ｔまたはｘ＝ｅｘｐｒｅｓｓｉｏｎのいずれかを取ることができる。ここで、ｅｘｐｒｅｓｓｉｏｎは値を現在の環境から読み出すか、または値を計算するためのコードを起動することができる。式により実行されるコードが順序依存性を取り入れない限り、木文法の実行結果は決定的である。
【００６２】
プログラマは属性文法を使用して、副作用が生ずべきであることが明白になるまで、その副作用を遅らせることができる。例えば、木をトラバースしてテキストをプリントするため、プログラマは属性を用いてテキストを集めて文字列にし、次いで木文法の開始記号と関連付けられた最終動作からの文字列をプリントすることができた。プログラマはまた、プリント動作を曖昧でない非終端定義まで延ばすことで、部分木を「オンザフライ」でプリントすることを選択することもできた。
【００６３】
本発明の例示的で非限定的な実施形態に従う変数リネーミングに関して、変数束縛動作の独立性を保証するため、コンパイラは変数をリネームして、ＭＦＳＴ内で束縛される夫々の変数を一意にする。コンパイラが所与の動作に対するコードも生成する場合、コンパイラはα内の変数もリネームする。コードブロックＢがコンパイラに対して曖昧である場合、コンパイラは、元の変数名をそれらの更新された名前を通して間接的に調べる環境をＢに渡すよう手配する。
【００６４】
オプションとして、実行中の範囲分析を実施し、幾つかの元の変数に、同一の更新された名前を共有させることで、変数リネーミングを最適化することができる。また、コンパイラが決定するオフセットを用いて配列アクセスとして変数参照を実装することで、トランスデューサの性能を改善することができる。
【００６５】
従って、１つの態様では本発明は、ＦＳＴに対して動作意味の保存を実現する効率的な木変換を実施するための一般的なフレームワークを与える。このＦＳＴは、その表現における動作情報を多様なＦＳＴ表現集合にわたってサポートする。積、和および補集合の変換演算のうち任意のもの、ならびに合成を伴う他のブール演算子を、動作意味を保存する間、ＦＳＴ上で実施することができる。
【００６６】
さらに、背景技術で述べたように、制限された環境下では、順序入れ子情報を木変換にわたって保存できるいくつかのシステムもあれば、非順序入れ子情報を木変換にわたって保存できるシステムもあるが、順序木情報および非順序木情報の両方を木変換、例えば、積、和、補集合、等にわたって保存できるシステムはまだ存在しない。従って、様々な非限定的な実施形態において、効率的な木変換を実施するためのフレームワークは、ＦＳＴに対する木変換の実施中に順序入れ子情報および非順序入れ子情報も保存する。
【００６７】
順序情報と非順序情報との間の違いを概念的に図４Ａおよび４Ｂに示す。図４Ａはリストパターンとしても知られる順序パターンを示し、パターンマッチを行うために赤、次に緑、次に青、次に再び赤から成る列が必要である。従って、パターンマッチングの面ではパターン要素の出現順序を考慮する。図４Ｂは、集合パターンとしても知られる非順序パターンを示す。図４Ｂの集合パターンでは図４Ａのリストパターンと同じ要素を示してあるが、今回は順序がない。図４Ｂの集合パターンは従って、２つの赤、１つの緑、および１つの青から成る集合をいかなる順序でも表現する。パターンマッチングの際に考慮に入れるのは集合内の要素の出現、即ち、要素が両方の木で現れるかどうかであり、要素が現れる順序ではない。
【００６８】
コンピューティングシステムにおけるリストパターンマッチングのシナリオの例としてパスワード入力があり得る。ここで、パスワードは連続的な数字の集合である。パスワードに入力した夫々の文字は、ユーザに対してシステムに記憶された正しいパスワードとマッチさせるために特定の順序で入力されなければならないので、パスワードマッチングのシナリオでは順序情報を有する木構造に基づいてパターンをマッチさせるであろう。
【００６９】
コンピューティングシステムにおける集合パターンマッチングのシナリオの例では、特定のファイル集合、例えば、Ｐｉｃ＿Ａｍｙ、Ｐｉｃ＿Ｇｒｅｇ、Ｐｉｃ＿Ｎｅｙｄａをファイルシステム内で検索することができる。これらの画像が現れるフォルダを検索するとき、マッチされているものは、フォルダ内でのそれらの出現であって、フォルダ内でそれらが現れる順序ではない。換言すれば、検索シナリオではユーザはこれらのファイルの各々を有するフォルダを見つけることを気にするだけであり、画像がシステムに記憶された順序はユーザには重要でない。集合パターンマッチングシナリオの別の例には、或る特定のファーストネーム、ミドルネームおよびラストネームを纏めてデータベース内で見つけることがあり、この結果は、データが「ラストネーム、ファーストネーム、ミドルネーム」、「ファーストネーム、ミドルネーム、ラストネーム」または「ファーストネーム、ラストネーム、ミドルネーム」として記憶されたかどうかに依存しない。任意の順序でのこの３つ全ての任意の出現がデータベースクエリを満足させる。
【００７０】
本発明のフレームワークによると、積、和および補集合の変換のうち任意のものを含む変換を、木データ構造により表現した順序情報および非順序情報の両方を保存する間、ＭＦＳＴ上で実施することができる。従って、変換を、木の子に関する集合およびリストの前提を組み合わせたパターン上で実施することができる。このように、木構造のノード内で入れ子になった順序情報または非順序情報の何れかが変換にわたって保存される。
【００７１】
図５Ａのフロー図により示されるように、本発明により、コンピューティングシステムにおいて順序情報および／または非順序情報を含む多様な種類の有限状態トランスデューサ（ＦＳＴ）データ構造を５００で受信し、５０５で本発明のフレームワークの変換エンジンをＦＳＴに適用するための一般的なフレームワークが可能となる。５１０で、ＦＳＴの分析および変換が、任意の種類のＦＳＴ表現に対する上述した木文法に従って発生する。その結果、５１５でＦＳＴが変換されＭＦＳＴを生成する。このＭＦＳＴは、例えば積、補集合、および和の演算のうち任意のものを複数のＦＳＴ上で実施する間に、ＦＳＴの動作情報を保存し、順序入れ子情報および非順序入れ子情報を保存し、非決定性のＦＳＴを決定性の結果へ変換することを可能とする。
【００７２】
図５Ｂは、上記プロセスに一般的に対応するブロック図であり、本発明の木文法により可能となる本態様を示す。変換フレームワーク５３０は夫々順序情報、非順序情報、またはその両方を含む１つまたは複数のＭＦＳＴ５２０、５２２または５２４を受信し、積、和および補集合の変換演算（および／または合成を伴う他のブール演算子）のうち任意のものに従ってＭＦＳＴを変換し、順序情報および／または非順序情報を出力５４０に保存する。
【００７３】
図５Ｃから５Ｉは、順序情報、またはラベル付き情報の存在下における、状態機械上での変換の例示的で非限定的な態様を示す。図５Ｃのブロック図に示すように、問題は、夫々の機械Ｍ１およびＭ２に対して別々の受理状態５５０および５５５を有する、２つの状態機械Ｍ１およびＭ２の和に関する。即ち、この情報を機械の変換表現内でどのように表すか、である。以前は、これは２つの受理状態５５０および５５５を、両方を表す単一の受理状態に結合することにより実現されたが、これは元の機械から情報の喪失をもたらす可能性がある。
【００７４】
図５Ｄのブロック図によると、例示的で非限定的な態様において、本発明は、結果の変換機械５６０内で受理状態とラベル付けされたホーム状態機械（ｈｏｍｅ  ｓｔａｔｅ  ｍａｃｈｉｎｅ）を受理する。様々な非限定的な実施形態において、本発明は変換中にラベル付き和ＵLの処理を取り込む。ラベル付き和ＵLは和の変換であり、和機械の受理状態を、受理状態が生ずる機械の名前でラベル付する。
【００７５】
図５Ｅの例により示されるように、Ｍ1ＵLＭ2を実施するとき、受理状態ラベルに対する３つの可能性、即ち、「Ｍ1」５７５、「Ｍ1、Ｍ2」５８０および「Ｍ2」５８５がある。これらは、ラベル付き和機械内の受理状態が、夫々Ｍ１、Ｍ2およびＭ2の両方、ならびにＭ2により受理される入力を表すことを示す。図５Ｉでさらに詳細に示されるように、例示的で非限定的な実装では、これらのラベルを、元の機械当たり１ビットとしたビットと見なすことができる。例えば、Ｍ1に下位ビットを割り当て、Ｍ2に上位ビットを割り当てることができる。すると、可能なラベルを「０１」（即ち、Ｍ２でなくＭ1が入力を受理）、「１１」（即ち、Ｍ1およびＭ2の両方が入力を受理）および「１０」（即ち、Ｍ1でなくＭ2が入力を受理）として表すことができる。他の可能性は「００」である。全ての和機械の非受理状態は、（Ｍ1およびＭ2の何れも入力を受理しないので）このラベルを有するとみなすことができる。
【００７６】
これに関して、図５Ｅのブロック図に示されるように、組み合わせＭ1Ｍ2を表す結果の受理状態ノード５８０を生成することに加えて、本発明では受理状態Ｍ1および受理状態Ｍ2を表す受理状態ノード５７５および５８５も生成する。図５Ｆに示されるように、和演算子Ｍ1∪Ｍ2に出会うとこれらの受理状態５７５、５８０および／または５８５の何れも結果の受理状態の一部であることができ、一方で、図５Ｇに示されるように、積演算子Ｍ1∩Ｍ2は、Ｍ1Ｍ2ノード５８０にのみ関係する。例えば、Ｍ1に下位ビットを割り当て、Ｍ2に上位ビットを割り当てる場合、１つの非限定的な実施形態では、「１１」とラベル付けされた受理状態を見つけることで、和機械は積機械に変換される。その受理状態がなければ、積機械は空である。「１１」とラベル付けされた状態集合Ａが与えられる場合は、Ａ内のどの状態へも到達できない状態を和機械から除去することで積機械を生成する。
【００７７】
図５Ｈのブロック図に示されるように、本発明に従う変換中にサブタイピングを取得することもできる。タイピングに関してコンポーネント５７０で決定化する際、決定可能な３つの結果がある。Ｍ1⊂Ｍ2は、上側に示されるように、どの受理状態もＭ1とラベル付けされない場合の一つの結果である。Ｍ1＝Ｍ2は、中央において受理状態Ｍ1Ｍ2５８０のみが生成される場合の別の結果である。Ｍ2⊂Ｍ1は、下側に示されるように、どの受理状態もＭ2とラベル付けされない場合の別の結果である。上の変換プロセスが与えられると、サブタイピングを決定することができる。例えば、Ｍ1に下位ビットを割り当て、Ｍ2に上位ビットを割り当てる場合、全ての受理状態に１１がラベル付けされるならば、Ｍ1はＭ2に等しい。１０および１１がラベル付けされる受理状態がある場合、Ｍ2はＭ1を含む（即ち、Ｍ1はＭ2のサブタイプである）。
【００７８】
図５Ｉは、ラベル付き和演算子に従う機械５９０および機械５９２の変換の例示的で非限定的なプロセスに対するフロー図を示す。この場合、２つの機械５９０および５９２の各々は２ビットの機械である。ビットラベルを適用する上述の例示的で非限定的な実装によると、２ビットが機械５９０のラベルＬ1およびＬ2に割り当てられ、２ビットが機械５９２のラベルＬ3およびＬ4に割り当てられる。本発明のラベル付き和演算子に従って組み合わせると、これにより１６個の受理状態が結果の４ビット機械５９５内に作成される。例えば、Ｌ2はラベル００１０を取り、Ｌ2Ｌ4はラベル１０１０を取り、Ｌ1Ｌ2Ｌ3Ｌ4はラベル１１１１を取る、等、全ての組み合わせが表わされるまで続く。
【００７９】
図５Ｊは、対応する非順序機械を構築および組み合わせるためどのように順序機械を変換するかを示す。例えば、パターン集合Ｐは、少なくとも１つのｐ1、０個または１つ以上のｐ2、および１つまたは複数のｐ3を含む集合を示す以下の集合｛ｐ1，ｐ2*，ｐ3+｝により表されるような、任意の出現制約を含むことができる。本発明の例示的で非限定的な実装によると、集合パターンＰを２つの構成部分、即ち、（Ａ）今説明した集合の例Ｐにおけるｐ1∪ｐ2∪ｐ3のような和パターン５９６、および（Ｂ）ラベル付き実行の集合５９８に分解し、その各々は幾つかの入力を受理する。今説明した例では、これにより｛Ｌ1,Ｌ2*，Ｌ3+｝が結果生ずる可能性がある。ここで、Ｌ1、Ｌ2およびＬ3は夫々、ｐ1、ｐ2およびｐ3の受理状態をラベル付けする。
【００８０】
従って、図５Ｋに示されるように、非順序パターン、例えば所与の非順序パターンＰ1およびＰ2に対するラベル付き和ＵLを実施するため、本発明の例示的で非限定的な実装によると、以下の式が計算される。即ち式∪（Ｐ1）、∪（Ｐ2）、Γ（Ｐ1）およびΓ（Ｐ2）である。ここで、∪（ｘ）はｘに対する和パターンであり、Γ（ｘ）はｘに対する受理実行の集合である。次いで、これらの式に基づいて、以下の２つの結果が得られる。
【００８１】
【数１】
2010503932.tif 000005
【００８２】
ここで、図５Ｋおよび上の式（２）の「*」演算子ＬＵＣＰは、ラベル付き和外積演算を表す。
【００８３】
次に、∪（Ｐ1∪LＰ2）に再度ラベル付けして、実行ラベリングが一貫するようにする。例えば、再ラベル付けを、冗長なラベルグループＲ内の全てのｌを書き換えることで実現する。Ｒから、任意のメンバｚ（例えば、上述のラベル毎ビットの実装における、最小数のラベルまたは最小順位のビット）を選択し、Ｒ内の夫々のｌに対してｌをｚに書き換える。例えば、図５Ｌに示されるように、∪（Ｐ1∪LＰ2）が「Ｌ1、Ｌ2」、「Ｌ1、Ｌ3、Ｌ4、Ｌ2」および「Ｌ2、Ｌ4」を含む例示的な受理状態ラベルＡＳＬ１を有する場合、Ｌ3をＬ1で置き換え、Ｌ4をＬ2で置き換えて、短縮した受理状態ラベルＡＳＬ２、即ち、「Ｌ1」、「Ｌ1、Ｌ2」および「Ｌ2」を形成することができる。
【００８４】
述べたように、上の図５Ｋおよび式（２）の「*」演算子ＬＵＣＰは、ラベル付き和外積演算を表す。前段落で説明されたようにＰ1およびＰ2の受理実行を再ラベル付けしたので、ラベル付き和外積演算を以下の非限定的なプロセスに従って定義することができる。先ず、演算子ＵLを実行Ｒ1およびＲ2の組に対して定義する。そうするために、Ｌａｂｅｌ（Ｒ）を実行Ｒのラベルとして定義する。次いでＲを、組の集合（ｌ，［ｘ，ｙ］）として定義する。ここで、ｌは再ラベル付けしたＰ1∪LＰ2から得た何らかのラベルであり、ｘはｌの最小出現番号、ｙはｌの最大出現番号、および［ｘ，ｙ］⊆［０，∞］である。以下のようにＲ1＊Ｒ2（即ち、Ｒ1およびＲ2の外積）内の夫々の要素の組を考えることでＲ1∪LＲ2を計算する。夫々の組、（ｌ1，［ｘ1，ｙ1］）、（ｌ2，［ｘ2，ｙ2］）に対して、ｌ1＝ｌ2ならば、（ｌ1，［ｘ1，ｙ1］）、（ｌ2，［ｘ2，ｙ2］）は区間和演算を用いて（ｌ1，［ｘ1，ｙ1］）Ｕ（ｌ2，［ｘ2，ｙ2］）となる。そうでなければ、（ｌ1，［ｘ1，ｙ1］）、（ｌ2，［ｘ2，ｙ2］）は空集合である。
【００８５】
従って、Ｒ1*Ｒ2（即ち、Ｒ1およびＲ2の外積）内のメンバｚに対して、ＵLは（ｌ1，［ｘ1，ｙ1］）Ｕ（ｌ2，［ｘ2，ｙ2］）または空集合の何れかとして計算される。次いで、これらの結果に対して和を取ることでＲ1ＵLＲ2を計算し、結果の集合Ｓを形成する。ＳがＲ1およびＲ2と同じ濃度を有する場合、Ｒ1ＵLＲ2はラベル、例えば、Ｌａｂｅｌ（Ｒ1）およびＬａｂｅｌ（Ｒ2）を伴うＳである。そうでなければ、Ｒ1ＵLＲ2は｛Ｒ1，Ｒ2｝であり、この場合、Ｒ1およびＲ2は互いに素であり、別々のラベルで保持される。
【００８６】
例えば、
Ｒ1＝｛（Ｌ1，［０，１］），Ｌ2，［１，∞］），Ｌ3，［１，１］）｝
Ｒ2＝｛（Ｌ1，［１，２］），Ｌ2，［２，２］），Ｌ3，［１，１］）｝
である場合、ラベルＬａｂｅｌ（Ｒ1）およびＬａｂｅｌ（Ｒ2）でＲ1ＵLＲ2＝｛（Ｌ1，［０，２］），Ｌ2，［１，∞］），Ｌ3，［１，１］）｝である。
【００８７】
別の例として、
Ｒ1＝｛（Ｌ1，［１，１］）｝，Ｌ2，［２，∞］），Ｌ3，［１，１］）｝
Ｒ2＝｛（Ｌ1，［０，∞］）｝，Ｌ2，［１，１］），Ｌ3，［４，４］）｝
である場合、Ｒ1およびＲ2は互いに素であるのでＲ1ＵLＲ2＝｛Ｒ1，Ｒ2｝である。
【００８８】
別の例として、
Ｌ1を（Ｌ1，［１，１］）、等として、Ｒ1＝｛Ｌ1，Ｌ2｝
Ｒ2＝｛Ｌ1，Ｌ2，Ｌ3*｝
である場合、ラベルＬａｂｅｌ（Ｒ1）およびＬａｂｅｌ（Ｒ2）でＲ1ＵLＲ2＝｛Ｌ1，Ｌ2｝、且つラベルＬａｂｅｌ（Ｒ2）でＲ1ＵLＲ2＝｛Ｌ1，Ｌ2，Ｌ3+｝である。
【００８９】
要約すると、本発明によるとＲ1ＵLＲ2、実行Ｒ1およびＲ2に対するＵLの定義が上述の手続きに従って最初に計算される。次いで、Ｒ1と（Ｒ1ＵLＲ2）との積を取り、Ｒ2と（Ｒ1ＵLＲ2）との積を取って、即ち、Ｒ1∩（Ｒ1ＵLＲ2）およびＲ2∩（Ｒ1ＵLＲ2）として、結果を調整する。Ｒ1∩（Ｒ1ＵLＲ2）およびＲ2∩（Ｒ1ＵLＲ2）を、和演算子ＵLに対してと同様だが、区間和演算の代わりに区間積演算を用いた方法により実施する。
【００９０】
これを実現するため、本発明の例示的で非限定的な実施形態では、和実行を、部分Ｒ１、Ｒ２、およびＲ１∩Ｒ２に分解する。次いで、これらの部分Ｒ１、Ｒ２、およびＲ１∩Ｒ２に夫々Ｌａｂｅｌ（Ｒ１）、Ｌａｂｅｌ（Ｒ２）、およびＬａｂｅｌ（Ｒ１），Ｌａｂｅｌ（Ｒ２）でラベル付けする。
【００９１】
従って、Ｐ1およびＰ2が非順序パターンである場合、Ｐ1ＵLＰ2の決定化を実施することができる。これに関して、本発明により、和パターン部および和パターンの受理実行集合でＰ1ＵLＰ2を非順序パターンとして計算することができ、夫々の実行にはＰ1、Ｐ2またはその両方から得たラベルでラベル付けする。Ｐ1ＵLＰ2は次いで何らかの他の非順序パターンＰ3を伴う和であることができ、Ｐ3はまた、和パターン、ラベル付き実行の集合、等を別の非順序パターンＰ4に対して有する。
【００９２】
例示的で非限定的な利用シナリオ
理解を補うため、本発明の様々な利用シナリオにより、コンピューティングシステム内で本発明のＱフレームワークを用いたパターンマッチングを適用可能な幅広い応用例を示す。変換されている木に埋め込んだ動作意味または順序情報および非順序情報を保存しつつマッチさせる能力により、広範囲な一連のパターンマッチングシステムがコンピューティングシステム内で可能となる。しかしながら、選択された実際のシナリオは例示的に過ぎず、従って本発明が適用されるパターンマッチングの分野に対する限定と捉えるべきではない。実際、定義によると、変換されている木表現に埋め込んだ動作制約、または順序情報および非順序情報に関する情報を失うことを気にする必要がないので、本発明に従ってＭＦＳＴを変換する機能の幅は非常に広い。
【００９３】
これに関して、上述したように、Ｑフレームワークは、少なくとも積、和および補集合の変換に従ってＭＦＳＴを変換する際に上記の動作または順序情報および非順序情報の保存を可能にさせる。これら３つの変換演算により、木データ構造上の特性を、当業者に公知なように構造的互換性、またはサブタイピングとして実施することができる。しばしば、コンピューティングアプリケーションが、所与の木が別の所与の木、または木集合（または和、補集合もしくは積により定義されるこれらの木の何らかの変換演算）の部分集合であるかどうかを知りたくなるだろう。
【００９４】
本発明を適用可能な別の重要なシナリオクラスは、静的な型チェックを実施するアプリケーションのホストであり、この場合、コンパイラはプログラムを見て、手続き互換性を求める。手続き互換性チェックには木集合に対するパターンマッチングが関与し、コンピュータプログラム内のバグを発見するのに役立つ。
【００９５】
一般に、ユーザまたはコンピューティングシステムが木データ集合、または木データの部分集合に対して実装したいテストのクラスは無限である。しかしながら、幾つかの再現テストが一般に行われる。例えば、しばしばテストは、第１の木または木集合が第２の木または木集合と交わるかどうかを知りたがるだろう。または、木集合に対する集計があるかどうか、および木トラバーサル経路の全てに対するカバレッジがあるかどうかを知りたがるだろう。または、ユーザはどの木がデフォルトケースになるかを知りたいかもしれない。また、空テストを行って、木がそもそもパターンマッチとして受理されるかどうかを質問したいかもしれない。述べたように、本発明の１つの実施形態では、本発明により以下の４つの変換テスト、即ち、積、和、補集合および空のテストが可能となる。
【００９６】
コンパイラを用いた本発明の有利な利用方法を上で説明した。本発明を、スキーマ検証のような多数の他のシナリオに対して同様に使用することもできる。例えば、メッセージが購入注文とともに来る場合、問題はその購入注文が何らかのスキーマに対して互換性があるかどうかである。本発明のパターンマッチングを使用して、動作意味または順序／非順序情報に関わらず、それらを出力結果内で保存しつつそのメッセージをスキーマに対して検証することができる。
【００９７】
契約のチュックは、本発明の別の例示的な使用方法である。例えば、企業は、その企業向けのヒューマンリソースコンピューティングシステムに関するポリシーを持ちたいかもしれない。そのポリシーは、そのコンピューティングシステムが、物理システムを表す一連のコンピュータ要件（例えば、Ｘ量の記憶、Ｙ量のセキュリティ、Ｚ量の処理能力、等）に従わなければならないことを記述する。これに関して、夫々の構成を木表現内の要件集合として表すことができ、本発明のフレームワークの木変換機能によると、システムアナリストは予め定義された変換に従ってコンピュータ構成を変換し、その新しいコンピュータ構成がＨＲコンピューティングシステムに要求された契約にマッチするかどうかを見ることができる。
【００９８】
本発明をさらに、コンピューティングシステムにより記録された一連のログデータ内でセキュリティホールパターンを見つけること、またはコンピューティングシステムに対する可能な構成の決定に適用することができる。本発明をファイアウォールに適用することができる。この場合、ファイアウォールを出入りするメッセージを木と見なすことができ、パターンマッチングを使用して、任意の所与のメッセージをファイアウォールから出力すべきかどうかを監視することができる。本明細書で説明し、Ｑフレームワークによりサポートされる変換ブール演算を利用して任意の論理文を形成できるので、コンピューティングシステム内の任意のルールのシステムを木に還元することができ、パターンマッチングを適用してそれらのルールへの順守を判定することができる。従って、本発明の応用例が無限であることは明らかであるはずである。
【００９９】
有限状態オートマトンおよびトランスデューサ
さらなるコンテキストとして、有限状態機械（ＦＳＭ）または有限状態オートマトン（ＦＳＡ）は状態、遷移および動作から成る振る舞いのモデルである。ＦＳＭの状態は過去に関する情報を記憶する。即ち、状態はシステムの開始から現時点までの入力の変化を反映する。遷移は状態の変化を示し、その遷移を可能とする実行を要求する条件により記述される。動作は、所与の時点で実施すべき行動の記述である。幾つかの動作の種類がある。すなわち、エントリ動作、終了動作、入力動作、および遷移動作である。エントリ動作では、状態に入る際に動作を実行する。終了動作では、状態を出る際に動作を実行する。入力動作では、現在の状態と入力条件に依存して動作を実行する。遷移動作では、或る特定の遷移を実施する際に動作を実行する。
【０１００】
有限状態トランスデューサ（ＦＳＴ）は、出力を所与の入力および／または状態に基づいて動作を用いて生成する一種のＦＳＭであり、制御アプリケーション、コンピュータプログラムの構築、等に使用することができる。図６Ａは、単純な有限状態トランスデューサ６２０を示す。トランスデューサ６２０は、所与の入力６１０に基づいて、ＦＳＭ６２０により翻訳、または変換して出力６３０を生成する。存在する２種類のトランスデューサＦＳＭはＭｏｏｒｅモデルおよびＭｅａｌｙモデルであり、それらを以下でより詳細に説明する。混合モデルも同様にしばしば使用される。
【０１０１】
このように、多くの異なる種類のコンピュータシステムおよびプロセスをＦＳＭおよびＦＳＴとしてモデル化できることが分かる。例えば、任意のＸＭＬ（ｅｘｔｅｎｓｉｂｌｅ  ｍａｒｋｕｐ  ｌａｎｇｕａｇｅ）文書を、有向グラフを用いてＦＳＭとして表すことができる。関係データベース内の関係データもこの方法で表すことができる。それにより、例えば、入力（例えば、クエリ）を、基盤となる関係記憶を表すＦＳＴにより出力（例えば、クエリ結果）に翻訳する。一般に、コンピュータプロセスのモデル化に使用する際、ＦＳＴは一般にエッジにラベル付けされた有向グラフとして表され、夫々の頂点はｎ個の状態のうちの１つを表し、夫々のエッジは、そのエッジをラベル付けするアルファベット記号の受信の際の一方の状態から他方の状態への遷移を表す。
【０１０２】
コンピュータシステム内の多数の複雑なサブシステムおよびプロセスをシステム全体の一部として通信可能に結合する際、システム全体に対するソフトウェアを設計するため、設計者は最初にサブシステムおよびプロセスの各々をＦＳＴ、例えば、有向グラフ、または他の等価な表現として表すことができる。次いで、異なるサブシステムを接続する単一のシステムに対して複雑なコンピュータプログラムを作成するため、ＦＳＴ、例えば、有向グラフを、様々な演算に従って組合せまたは変換して、システム全体の振る舞いを表す新たな有向グラフを形成することができる。
【０１０３】
例えば、あるユーザＪａｎｅがインターネットを介してクライアントコンピュータからインターネットサーバに、データベースに記憶されインターネット上のアプリケーションにより提供される友人Ｊｏｈｎの休暇の写真を要求することを考える。理解できるように、その要求に従って生ずるエンドツーエンドの通信は大量であり、Ｊａｎｅの認証で始まり、要求自体を実施することに加えてＪａｎｅがＪｏｈｎの写真を閲覧する権利を与えられていることを保証する。単純な例として、要求自体の作成および処理を第１のＦＳＴとしてモデル化することができる。サーバ側で、第２のＦＳＴにより、一連のアクセス制御リスト（ＡＣＬ）および対応する手段で見つけられるような様々なルールを参照してＪａｎｅがＪｏｈｎの友人であるかどうかをチェックする振る舞いをモデル化することができる。上記のルールは、ＸＭＬ断片、木、または有向グラフのチェーンとして表すことができる。さらに、第３のＦＳＴにより関係データベース自体をモデル化することができる。第１、第２および第３のＦＳＴ集合を、変換、組み合わせ、マッチング、翻訳、等することより、新たな有向グラフを形成することができる。その有向グラフはシステムを表し、特定の入力要求に対して肯定（「許可」）または（「不許可」）の回答を返し、写真の配信を処理する。
【０１０４】
一般に、ＦＳＭを、図８Ａの単純な状態遷移図にあるように、状態図（または状態遷移図）を用いて表すことができる。図８Ａでは、２つの状態Ｓ１およびＳ２を夫々エントリ動作ＥｎｔｒｙＡ１およびＥｎｔｒｙＡ２を有するとして表してある。これは、状態Ｓ１に入る際にエントリ動作ＥｎｔｒｙＡ１を実施し、状態Ｓ２に入る際にエントリ動作ＥｎｔｒｙＡ２を実施することを意味する。次いで、遷移条件ＴＣ１が生じると状態Ｓ１からＳ２への遷移Ｔ１が生じ、遷移条件ＴＣ２が生じると状態Ｓ２からＳ１への遷移Ｔ２が生ずる。状態Ｓ１は「ドアが開いている」であり、状態Ｓ２は「ドアが閉じている」であることができる。従って、状態Ｓ１から状態Ｓ２へ行くために、遷移Ｔ１が生じなければならず、これは遷移条件ＴＣ１が生ずるときにのみ生じ、この条件とは「何らかの力がドアを閉じる方向に移動させる」であろう。状態Ｓ２に入る際に実行するエントリ動作ＥｎｔｒｙＡ２は従って「ドアを閉じる」であろう。ドアを開く、即ち、状態Ｓ２から状態Ｓ１に行く際に同様な遷移チェーンを辿ることができる。
【０１０５】
図のほかにも、異なる種類の状態遷移表を使用してＦＳＡを表すこともできる。状態遷移表ＳＴＴ１のような一般的な表現を図７Ａに示す。図７Ａにおいて、現在状態Ｂのような表ＳＴＴ１の列、および条件Ｙのような表ＳＴＴ１の行の組合せは、状態Ｂにいる間に条件Ｙが生ずる際に生ずる次の状態、即ち状態Ｃを示す。しかしながら、状態遷移表ＳＴＴ１のような表を用いると、脚注を用いるだけで完全な動作情報を加えることができる。
【０１０６】
しかしながら、状態表を用いて完全な動作情報を含むＦＳＭ定義が存在する。例えば、仮想環境内で定義されたＦＳＭは仮想有限状態機械（ＶＦＳＭ）と呼ばれる。このＶＦＳＭは、入力制御特性の割り当て名および出力動作の割り当て名を用いて制御システムの振る舞いを記述するために用いるソフトウェア仕様の方法に関する。
【０１０７】
仮想環境はＶＦＳＭが動作する環境を特徴付け、３つの名前の集合、即ち、入力名、出力名および状態名により定義される。入力名は全ての可能な変数の制御特性により表される。出力名は変数上での全ての可能な動作により表され、状態名はＦＳＭの状態の各々に対して定義される。入力名を使用して、状態遷移または入力動作を実施するための仮想条件を構築する。仮想条件は、正論理代数を用いて構築する。出力名を使用して動作（エントリ動作、終了動作、入力動作または遷移動作）をトリガする。
【０１０８】
状態表は、図７Ｂの例示的な状態表ＳＴ１に示されるように、ＶＦＳＭの状態の振る舞いの詳細を定義する。状態遷移表ＳＴ１は３つの列を含む。第１の列では、状態名ＳＮを使用し、第２の列には、正論理代数を用いて入力名から構築した仮想条件ＣＯを配置し、第３の列には、動作ＡＣをトリガするために用いられる出力名が現れる。
【０１０９】
ここで提示された反応システムのモデル化での使用に加えて、ＦＳＡは言語学、コンピュータ科学、哲学、生物学、数学、および論理学を含む多くの異なる分野で重要である。有限状態機械は、オートマトン理論および計算理論で研究されている一種のオートマトンである。コンピュータ科学では、有限状態機械はアプリケーションの振る舞いのモデル化、ハードウェアデジタルシステムの設計、ソフトウェア工学、コンパイラ、ならびに計算および言語の研究において広く用いられている。ＦＳＡの完全な適用調査は事実上不可能であるが、至る所のシステムに対する事実上無限のＦＳＡの適用がある。
【０１１０】
一般に、トランスデューサは２つの形式言語間の関係を計算する。ＦＳＭおよびＦＳＡのコンテキストでは、トランスデューサは所与の入力および／または状態に基づき動作を用いて出力を生成し、このトランスデューサを制御アプリケーションに使用することができる。２種類のトランスデューサＦＳＭが一般に区別される。即ちＭｏｏｒｅモデルとＭｅａｌｙモデルである。実際には、その混合モデルがしばしば使用される。
【０１１１】
説明に役立つ目的のため、図８Ｂは、出力Ｏ３、Ｏ４、Ｏ５およびＯ６を夫々伴う４つの状態Ｓ３、Ｓ４、Ｓ５およびＳ６を有するＭｏｏｒｅモデルの例を示す、トランスデューサＦＳＭ８００を示す。Ｍｏｏｒｅ機械では、ＦＳＭはエントリ動作のみを使用する。即ち、出力は状態のみに依存する。Ｍｏｏｒｅモデルの利点は、振る舞いの簡略化である。図８Ｂにおける例では、エレベータのドアのＭｏｏｒｅ  ＦＳＭ８００を示す。状態機械は、状態の変化をトリガする２つの命令、即ち、「ｃｏｍｍａｎｄ＿ｏｐｅｎ」Ｃ１と「ｃｏｍｍａｎｄ＿ｃｌｏｓｅ」Ｃ２を認識する。例えば、「Ｏｐｅｎｉｎｇ」状態Ｓ６におけるエントリ動作ＥＡ１はモータを開始してドアを開き、「Ｃｌｏｓｉｎｇ」状態Ｓ４におけるエントリ動作ＥＡ２はモータを反対方向に開始してドアを閉じる。「Ｏｐｅｎｅｄ」状態Ｓ３および「Ｃｌｏｓｅｄ」状態Ｓ５は本例ではいかなる動作も実施せず、むしろ外部システムに（例えば、他の状態機械に）、夫々「ドアが開いている」または「ドアが閉じている」ことを知らせる。
【０１１２】
図８Ｃは、２つの状態Ｓ７およびＳ８、出力Ｏ７およびＯ８、ならびに入力動作Ｉ１およびＩ２を夫々有するＭｅａｌｙモデルの例を示す、トランスデューサＦＳＭ８１０を示す。Ｍｅａｌｙ機械では、ＦＳＭは入力動作のみを使用する。即ち、出力は入力および状態に依存する。ＭｅａｌｙＦＳＭの使用は、状態数の削減にしばしばつながる。図８Ｃにおける例は、図８ＢのＭｏｏｒｅの例８００におけるものと同じ振る舞いを実装するＭｅａｌｙ  ＦＳＭ８１０を示す。２つの入力動作、即ち「ｃｏｍｍａｎｄ＿ｃｌｏｓｅが到着したらモータを開始してドアを閉じる」Ｉ１および「ｃｏｍｍａｎｄ＿ｏｐｅｎが到着したらモータを反対方向に開始してドアを開く」Ｉ２がある。
【０１１３】
ただし、有限オートマトンに対する別の違いが、決定性有限オートマトン（ＤＦＡ）と非決定性有限オートマトン（ＮＤＦＡ）または一般化非決定性有限オートマトン（ＧＮＦＡ）との間にある。決定性オートマトンでは、夫々の状態に対して、夫々の可能な入力に関する厳密に１つの遷移が存在する。非決定性オートマトンでは、所与の可能な入力に対して所与の状態からの遷移が、存在しないか、または１より多く存在する可能性がある。この違いは理論面では関連性はないが、実用面では関連性がある。なぜならば、任意のＮＤＦＡを等価なＤＦＡに変換できるアルゴリズムが存在するが、この変換により一般にオートマトンの計算量が大幅に増加するからである。
【０１１４】
１つの状態のみを有するＦＳＭは組み合わせＦＳＭと呼ばれ、入力動作のみを使用する。この概念は、多数のＦＳＭが協調する必要がある場合、および設計ツールに適合させるために純粋な組み合わせ部分を一種のＦＳＭとして考えると都合が良い場合に役立つ。
【０１１５】
一般に、トランスデューサは２つの形式言語間の関係を計算する。有限状態トランスデューサ（ＦＳＴ）により計算される関係のクラスは、合理的関係のクラスとして知られる。ＦＳＴは一般に、自然言語処理の研究において役立つ。
【０１１６】
ＦＳＴは、２つのテープを有する有限状態機械であり、単一のテープを有する通常の有限状態オートマトンと対比される。命名の問題として、オートマトンは、そのテープの内容を入力としてみなす場合は文字列を認識すると言われる。換言すれば、オートマトンは文字列を集合｛０，１｝にマッピングする関数を計算する。あるいは、オートマトンは文字列を生成すると言われ、これはそのテープを出力テープとみなすことを意味する。この観点において、オートマトンは文字列の集合である形式言語を生成する。オートマトンのこの２つの見方は等価である。即ち、オートマトンが計算する関数はまさに、オートマトンが認識した文字列集合の指標関数である。有限オートマトンにより生成される言語のクラスは、正規言語のクラスとして知られている。
【０１１７】
トランスデューサの２つのテープは一般に、入力テープおよび出力テープとみなされる。これに関して、トランスデューサは、その入力テープ上で文字列を受け取り、その出力テープ上に別の文字列を生成することで、その入力テープの内容をその出力テープに変換（即ち、翻訳）すると言われる。トランスデューサはそれを非決定的に行うことができ、夫々の入力文字列に対して１より多い出力を生成することができる。トランスデューサはまた、所与の入力文字列に対して出力を生成しなくてもよく、この場合、入力は却下されると言われる。
【０１１８】
さらなるコンテキストとして、形式的には、有限状態トランスデューサＴは、
Ｑは有限集合であって、状態の集合である、
Σは有限集合であって、入力アルファベットと呼ばれる、
Γは有限集合であって、出力アルファベットと呼ばれる、
ＩはＱの部分集合であって、初期状態の集合である、
ＦはＱの部分集合であって、最終状態の集合である、および
δ⊆Ｑ×（Σ∪｛∈｝）×（Γ∪｛∈｝）×Ｑ（∈は空文字列）が遷移関係である、
というようなタプル（Ｑ，Σ，Γ，Ｉ，Ｆ，δ）である。
（Ｑ，δ）を、Ｔの遷移グラフとしても知られるラベル付き有向グラフと見なすことができる。即ち、頂点の集合がＱであり、（ｑ，ａ，ｂ，ｒ）∈δは頂点ｑから頂点ｒに行くラベル付きエッジが存在することを意味する。これに関して、ａは入力ラベルであり、ｂはそのエッジの出力ラベルである。
【０１１９】
拡張された遷移関係δ*を、
δ⊆δ*、
全てのｑ∈Ｑに対して（ｑ，ε，ε，ｑ）∈δ、および
常に（ｑ，ｘ，ｙ，ｒ）∈δ*且つ（ｒ，ａ，ｂ，ｓ）∈δならば（ｑ，ｘａ，ｙｂ，ｓ）∈δ*
であるような最小の集合として定義する。
【０１２０】
拡張された遷移関係は本質的に、エッジラベルを考慮するよう拡大した遷移グラフの反射推移閉包である。δ*の要素は経路として知られる。経路のエッジラベルは、それを構成する遷移のエッジラベルを順番に連結することで得られる。
【０１２１】
トランスデューサＴの振る舞いは、次にように定義される合理的関係［Ｔ］である。即ち、（ｉ，ｘ，ｙ，ｆ）∈δ*となるようなｉ∈Ｉおよびｆ∈Ｆが存在する場合およびその場合に限り、ｘ［Ｔ］ｙである。即ち、入力ラベルがｘで出力ラベルがｙであるような、初期状態から最終状態への経路が存在する場合に、Ｔが文字列ｘ∈Σ*を文字列ｙ∈Γ*に変換する。
【０１２２】
有限オートマトン上で定義される以下の演算、すなわち、和、連結、Ｋｌｅｅｎｅ閉包、合成、入力テープの射影および出力テープの射影といった演算も、有限トランスデューサに適用される。
【０１２３】
和演算に関して、トランスデューサＴおよびＳが与えられると、ｘ［Ｔ］ｙまたはｘ［Ｓ］ｙである場合およびその場合に限りｘ［Ｔ∪Ｓ］ｙであるようなトランスデューサＴ∪Ｓが存在する。
【０１２４】
連結演算に関して、トランスデューサＴおよびＳが与えられると、ｗ［Ｔ］ｙおよびｘ［Ｓ］ｚである場合およびその場合に限りｗｘ［Ｔ・Ｓ］ｙｚであるようなトランスデューサＴ・Ｓが存在する。
【０１２５】
Ｋｌｅｅｎｅ閉包演算に関して、トランスデューサＴが与えられると、次の特性を有するトランスデューサＴ*が存在する。即ち、（１）ε［Ｔ*］ε、（２）ｗ［Ｔ*］ｙおよびｘ［Ｔ］ｚである場合ｗｘ［Ｔ*］ｙｚであり、（１）および（２）に従わない場合ｘ［Ｔ*］ｙは成立しない。
【０１２６】
トランスデューサの積という概念は存在しないことに留意されたい。その代わり、合成演算がある。合成演算はトランスデューサに固有のものであり、その構築はオートマトンの積の構築と同様である。合成を以下のように定義する。
【０１２７】
アルファベットΣおよびΓ上のトランスデューサＴならびにアルファベットΓおよびΔ上のトランスデューサＳが与えられると、ｘ［Ｔ］ｙおよびｙ［Ｓ］ｚとなるような文字
列ｙ∈Γ*が存在する場合およびその場合に限り
【０１２８】
【数２】
2010503932.tif 000006
【０１２９】
であるようなトランスデューサ
【０１３０】
【数３】
2010503932.tif 000007
【０１３１】
がΣおよびΔ上に存在する。
【０１３２】
トランスデューサの何れかのテープを射影してオートマトンを得ることもできる。２つの射影関数が存在する。即ち、π1は入力テープを保存し、π2は出力テープを保存する。第一の射影π1を以下のように定義する。
【０１３３】
トランスデューサＴが与えられると、ｘ［Ｔ］ｙである文字列ｙが存在する場合およびその場合に限りπ1Ｔがｘを受理するような有限オートマトンπ1Ｔが存在する。第２の射影π2は同様に定義される。
【０１３４】
さらに、有限状態機械を使用して部分順序を表すことができる。部分順序は、集合の要素の順序付け、配列、または配置の直感的な概念を形式化する。部分順序は必ずしも全順序である必要はない。全順序は、集合内の全てのオブジェクトの相互比較可能性を保証する。これに関して、全順序は集合の全ての項目の組に対して定義される一種の部分順序である。
【０１３５】
このように、部分順序はいくつかの項目の組に対して定義されるが、必ずしも全ての項目の組に対しては定義されない。例えば、集合｛ａ，ｂ｝および｛ａ，ｃ，ｄ｝は｛ａ，ｂ，ｃ，ｄ｝の部分集合であるが、どちらも他方の部分集合ではない。従って、「〜の部分集合」は集合上の部分順序である。別の例として、≦（以下）は整数上の全順序である。なぜならば、任意の２つの整数に対して、整数のうちの一つは常に他方以下であるからである。
【０１３６】
図６Ｂに示されるように、順序階層によると、順序入れ子は「ａ」が「ｂ」「意味する」という情報を表すが、その反対の情報は表さない（即ち、「ｂ」は必ずしも「ａ」を「意味する」わけではない）。従って、図６Ｂの木は順序入れ子の表現の例である。図６Ｃの木は対照的に、非順序入れ子の例を表す。これに関して、図６Ｃの木により表される事実情報を左から右に読むか、または右から左に読むかに関わらず、同じ事実情報が集められる。即ち、「ブロックは赤に等しい（ブロックは赤である）」または「赤はブロックに等しい（赤はブロックである）」は両方とも、ブロックが赤である（ブロック＝赤）ことを論理的に示している。従って、このような情報は非順序であり、木をトラバースする順序は非順序情報を得る上で重要ではない。
【０１３７】
例示的なネットワーク環境および分散環境
当業者は、本発明を、任意のコンピュータまたは他のクライアントまたはサーバ装置に関連させて実装でき、それらをコンピュータネットワークの一部として、または分散コンピューティング環境内に配置して、任意の種類のデータストアに接続できることを理解できる。これに関して、本発明は、任意数のメモリまたは記憶ユニットを有する任意のコンピュータシステムまたは環境、および任意数の記憶ユニットまたは記憶ボリュームにわたって生ずる任意数のアプリケーションおよびプロセスに関連し、これらを本発明のＱＦＸの実施形態に関連して使用することができる。本発明を、ネットワーク環境または分散コンピューティング環境に展開された、リモートまたはローカル記憶を有するサーバコンピュータおよびクライアントコンピュータを有する環境に適用することができる。本発明を、プログラミング言語機能性、リモートまたはローカルサービスおよびプロセスに関連して情報を生成、受信および送信するための解釈および実行機能を有する、スタンドアローンのコンピューティング装置に適用することもできる。前に述べられたように、ＭＦＳＴは複数のマシンおよびコンピューティング装置にわたるソフトウェアプロセスに対する普遍的な適用性を有し、それ故、本発明に従って文法をＭＦＳＴに翻訳する技術を、様々なコンピューティング環境において大きな効率性と共に適用することができる。
【０１３８】
分散コンピューティングは、コンピューティング装置とシステムとの間での交換によりコンピュータリソースおよびサービスの共有を提供する。これらのリソースとサービスは、ファイルのようなオブジェクトに対する、情報、キャッシュ記憶およびディスク記憶の交換を含む。分散コンピューティングは、ネットワーク接続性を利用して、クライアントが、集合的な力を活用して企業全体に利益をもたらすことができるようにする。これに関して、様々な装置が、本発明のＱＦＸに関係しうるアプリケーション、オブジェクトまたはリソースを有することができる。
【０１３９】
図９は、例示的なネットワークコンピューティング環境または分散コンピューティング環境の概略図を提供する。分散コンピューティング環境はコンピューティングオブジェクト９１０ａ、９１０ｂ、等、およびコンピューティングオブジェクトまたは装置９２０ａ、９２０ｂ、９２０ｃ、９２０ｄ、９２０ｅ、等を含む。これらのオブジェクトはプログラム、メソッド、データストア、プログラム可能ロジック、等を含むことができる。オブジェクトはＰＤＡ、オーディオ／ビデオ装置、ＭＰ３プレイヤ、パーソナルコンピュータ、等のような同一または異なる装置の部分を含むことができる。夫々のオブジェクトは通信ネットワーク９４０の方法により別のオブジェクトと通信することができる。このネットワーク自体は、図９のシステムにサービスを提供する他のコンピューティングオブジェクトおよびコンピューティング装置を含むことができ、それ自体複数の相互接続ネットワークを表すことができる。本発明の態様によると、夫々のオブジェクト９１０ａ、９１０ｂ、等、または９２０ａ、９２０ｂ、９２０ｃ、９２０ｄ、９２０ｅ、等は、本発明に従うＱＦＸの様々な実施形態での使用に適した、ＡＰＩ、または他のオブジェクト、ソフトウェア、ファームウェアおよび／またはハードウェアを利用できるアプリケーションを含むことができる。
【０１４０】
また、９２０ｃのようなオブジェクトを、別のコンピューティング装置９１０ａ、９１０ｂ、等、または９２０ａ、９２０ｂ、９２０ｃ、９２０ｄ、９２０ｅ、等でホストすることも理解できる。従って、示された物理環境は、接続された装置をコンピュータとして示すことができるが、そのような説明は例に過ぎず、物理環境を、ＰＤＡ、テレビ、ＭＰ３プレイヤ、等のような様々なデジタル装置を含むとして代替的に表現または説明してもよく、それらのうち任意のものは様々な有線および無線サービス、インタフェース、ＣＯＭオブジェクトのようなソフトウェアオブジェクト、等を使用することができる。
【０１４１】
分散コンピューティング環境をサポートする様々なシステム、コンポーネント、およびネットワーク構成がある。例えば、コンピューティングシステムを有線または無線システム、ローカルネットワークまたは広域分散ネットワークにより、互いに接続することができる。現在、ネットワークの多くはインターネットに結合されている。インターネットは、広域分散コンピューティングに対するインフラストラクチャを提供し、多くの異なるネットワークを包含する。そのインフラストラクチャのうち任意のものを、本発明のＱＦＸの実施形態に伴う例示的な通信に使用することができる。
【０１４２】
家庭用ネットワーキング環境では少なくとも４つの異なるネットワークトランスポート媒体があり、それらは夫々、電線、データ媒体（無線および有線の両方）、音声媒体（例えば、電話）および娯楽媒体のような一意なプロトコルをサポートすることができる。光スイッチおよび機器のような大部分の家庭用制御装置は接続に電線を使用することができる。データサービスはブロードバンド（例えば、ＤＳＬ、ケーブルモデム、等）として家庭に入ることができ、無線接続（例えば、ＨｏｍｅＲＦまたは８０２．１１Ｂ）または有線接続（例えば、ＨｏｍｅＰＮＡ、Ｃａｔ５、イーサネット（登録商標）、電線さえも）接続の何れかを用いて家庭内でアクセス可能である。音声トラフィックは有線（例えば、Ｃａｔ３）または無線（例えば、携帯電話）の何れかとして家庭に入ることができ、Ｃａｔ３配線を用いて家庭内に分散させることができる。娯楽媒体、または他のグラフィカルデータは衛星またはケーブルの何れかを通して家庭に入ることができ、一般に同軸ケーブルを用いて家庭内で分散される。ＩＥＥＥ１３９４およびＤＶＩも、メディア装置のクラスタに対するデジタル相互接続である。プロトコル標準として登場する可能性がある、または既に登場しているこれらのネットワーク環境の全ておよびその他のものを相互接続して、インターネットのような広域ネットワーク経由で外部世界に接続可能な、イントラネットのようなネットワークを形成することができる。要するに、様々な異なる情報源がデータの記憶および送信に対して存在し、その結果、本発明の任意のコンピューティング装置は任意の既存の方法でデータを共有および通信することができ、本明細書の実施形態で説明されたどの方法も限定であることを意図されていない。
【０１４３】
インターネットは一般に、ＴＣＰ／ＩＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ／Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）プロトコルスイートを利用するネットワークおよびゲートウェイの集合を参照し、コンピューティングネットワーキングの技術分野では公知である。インターネットを、ネットワーキングプロトコルを実行するコンピュータによって相互接続した、地理的に分散したリモートコンピュータネットワークのシステムとして説明することができる。そのネットワーキングプロトコルにより、ユーザはネットワーク上で相互作用および情報を共有することができる。このように幅広く情報共有できるので、インターネットのようなリモートネットワークはこれまで一般にオープンなシステムに発展してきた。このシステムにより、開発者は特殊な動作またはサービスを実施するためのソフトウェアアプリケーションを、原則として制限なしに設計することができる。
【０１４４】
従って、ネットワークインフラストラクチャにより、クライアント／サーバ、ピアツーピア、またはハイブリッドアーキテクチャのような多数のネットワークトポロジが可能となる。「クライアント」は、自身が関連付けられない別のクラスまたはグループのサービスを使用するクラスまたはグループのメンバである。従って、コンピューティングにおいて、クライアントは、別のプログラムにより提供されるサービスを要求するプロセス、即ち、大雑把には一連の命令またはタスクである。クライアントプロセスは、他のプログラムまたはサービス自体についての動作の詳細を「知る」必要なしに要求されたサービスを利用する。クライアント／サーバアーキテクチャ、特にネットワークシステムでは、クライアントは通常、別のコンピュータ、例えば、サーバにより提供される共有されたネットワークリソースにアクセスするコンピュータである。図９の例では、例えば、コンピュータ９２０ａ、９２０ｂ、９２０ｃ、９２０ｄ、９２０ｅ、等をクライアントと考え、コンピュータ９１０ａ、９１０ｂ、等をサーバと考えることができる。この場合、サーバ９１０ａ、９１０ｂ、等は、クライアントコンピュータ９２０ａ、９２０ｂ、９２０ｃ、９２０ｄ、９２０ｅ、等にその後複製されるデータを保持するが、状況に応じて、任意のコンピュータをクライアント、サーバ、またはその両方と考えることができる。これらのコンピューティング装置のうち任意のものはデータを処理中であることができ、または本発明のＱＦＸの様々な実施形態の木文法および翻訳技術に関係しうるサービスまたはタスクを要求中であることができる。
【０１４５】
サーバは一般に、インターネットまたは無線ネットワークインフラストラクチャのようなリモートまたはローカルネットワーク上でアクセス可能なリモートコンピュータシステムである。クライアントプロセスは第１のコンピュータシステム内でアクティブであることができ、サーバプロセスは第２のコンピュータシステム内でアクティブであることができ、それらは互いと通信媒体上で通信し、従って分散機能性を提供することができ、そして複数のクライアントはサーバの情報収集機能を利用することができる。本発明のＱＦＸに従って利用される任意のソフトウェアオブジェクトを複数のコンピューティング装置またはオブジェクトにわたって分散させることができる。
【０１４６】
クライアントおよびサーバは、プロトコル層により提供される機能性を利用して互いと通信する。例えば、ＨＴＴＰ（ＨｙｐｅｒＴｅｘｔ  Ｔｒａｎｓｆｅｒ  Ｐｒｏｔｏｃｏｌ）は、ＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）、または「ウェブ」に関連して用いられる共通プロトコルである。一般に、ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）アドレスのようなコンピュータネットワークアドレスまたはＵＲＬ（Ｕｎｉｖｅｒｓａｌ  Ｒｅｓｏｕｒｃｅ  Ｌｏｃａｔｏｒ）のような他の参照を使用して、サーバまたはクライアントコンピュータを互いに識別することができる。ネットワークアドレスをＵＲＬアドレスと呼ぶことができる。通信を通信媒体上で与えることができる。例えば、クライアントおよびサーバを、大容量通信向けのＴＣＰ／ＩＰ接続を介して互いに結合することができる。
【０１４７】
このように、図９は例示的なネットワークまたは分散環境を示し、サーバはネットワーク／バスを介してクライアントコンピュータと通信し、この中で本発明を使用することができる。より詳細には、本発明に従って、多数のサーバ９１０ａ、９１０ｂ、等を通信ネットワーク／バス９４０を介して、ポータブルコンピュータ、ハンドヘルドコンピュータ、シンクライアント、ネットワーク機器、またはＶＣＲ、ＴＶ、オーブン、ライト、ヒータ等のような他の装置といった多数のクライアントコンピューティング装置またはリモートコンピューティング装置９２０ａ、９２０ｂ、９２０ｃ、９２０ｄ、９２０ｅ、等と相互接続する。通信ネットワーク／バス９４０はＬＡＮ、ＷＡＮ、イントラネット、ＧＳＭネットワーク、インターネット、等であることができる。このように、本発明を任意のコンピューティング装置に適用でき、そのコンピューティング装置に関連して、本発明により定義されるＱフレームワークに従って属性付き木文法をコンパイルおよび実行し、ＭＦＳＴに翻訳することが望ましいと考えられる。
【０１４８】
通信ネットワーク／バス９４０がインターネットであるネットワーク環境において、例えば、サーバ９１０ａ、９１０ｂ、等はウェブサーバであることができ、クライアント９２０ａ、９２０ｂ、９２０ｃ、９２０ｄ、９２０ｅ、等はＨＴＴＰのような任意の多数の公知なプロトコルを介してそのウェブサーバと通信する。サーバ９１０ａ、９１０ｂ、等はクライアント９２０ａ、９２０ｂ、９２０ｃ、９２０ｄ、９２０ｅ、等としての機能を果たすこともでき、これは分散コンピューティング環境の特徴である。
【０１４９】
述べたように、通信は、必要に応じて有線または無線、またはその組合せであることができる。クライアント装置９２０ａ、９２０ｂ、９２０ｃ、９２０ｄ、９２０ｅ、等は通信ネットワーク／バス１４を介して通信してもしなくてもよく、通信ネットワーク／バス１４に関連する独立した通信を有してもよい。例えば、ＴＶまたはＶＣＲの場合、それらの制御に対するネットワーク態様があってもなくてもよい。夫々のクライアントコンピュータ９２０ａ、９２０ｂ、９２０ｃ、９２０ｄ、９２０ｅ、等およびサーバコンピュータ９１０ａ、９１０ｂ、等に様々なアプリケーションプログラムモジュールまたはオブジェクト１３５ａ、１３５ｂ、１３５ｃ、等を具備させ、様々な種類の記憶要素またはオブジェクトへの接続またはアクセスを具備させることができ、それらにわたってファイルまたはデータストリームを記憶することができ、またはそれらに対してファイルまたはデータストリームの部分をダウンロード、送信、または移動することができる。９１０ａ、９１０ｂ、９２０ａ、９２０ｂ、９２０ｃ、９２０ｄ、９２０ｅ、等の任意の１つまたは複数のコンピュータは、本発明に従って処理または保存されたデータを記憶するためのデータベースまたはメモリ９３０のような、データベース９３０または他の記憶要素の保守および更新に関与することができる。このように、本発明を、コンピュータネットワーク／バス９４０にアクセスおよびコンピュータネットワーク／バス９４０と相互作用できるクライアントコンピュータ９２０ａ、９２０ｂ、９２０ｃ、９２０ｄ、９２０ｅ、等、およびクライアントコンピュータ９２０ａ、９２０ｂ、９２０ｃ、９２０ｄ、９２０ｅ、等と相互作用できるサーバコンピュータ９１０ａ、９１０ｂ、等、および他の同様な装置、およびデータベース９３０を有するコンピュータネットワーク環境内で利用することができる。
【０１５０】
例示的なコンピューティング装置
述べたように、本発明は任意の装置に適用され、この場合、本発明に従って定義されるＱＦＸの技術を適用することが望ましいかもしれない。従って、当然のことながら、ハンドヘルド、ポータブルおよび他のコンピューティング装置ならびにあらゆる種類のコンピューティングオブジェクトが本発明に関連して使用される、即ち、装置が、状態機械を表すソフトウェアプロセスを実装、またはデータを受信、処理もしくは記憶できる場合なら常に本発明に関連して使用されると意図されていることが理解されるべきである。従って、図１０で後述される以下の汎用目的のリモートコンピュータは１つの例に過ぎず、本発明を、ネットワーク／バスの相互運用性および相互作用を有する任意のクライアントで実装することができる。このように、本発明を、非常に少量または最小のクライアントリソースが関係されるネットワークホストサービスの環境、例えば、機器内に配置したオブジェクトのような、クライアント装置がネットワーク／バスに対するインタフェースとして機能を果たすのみであるネットワーク環境で実装することができる。
【０１５１】
必ずしも必要ではないが、本発明を、装置またはオブジェクトに対するサービスの開発者が使用するためにオペレーティングシステムを介して部分的に実装することができ、および／または本発明のコンポーネントに関連して動作するアプリケーションソフトウェアに含めることができる。ソフトウェアを、プログラムモジュールのような、クライアントワークステーション、サーバまたは他の装置といった１つまたは複数のコンピュータにより実行されているコンピュータ実行可能命令の一般的なコンテキストで説明することができる。当業者は、本発明を他のコンピュータシステム構成およびプロトコルで実践してもよいことを理解するであろう。
【０１５２】
図１０は、従って、本発明を実装できる適切なコンピューティングシステム環境１０００ａの例を示すが、上で明らかにされたように、コンピューティングシステム環境１０００ａは媒体装置に対する適切なコンピューティング環境の１つの例に過ぎず、本発明の使用または機能性の範囲に関するいかなる限定を提示することを意図されない。コンピューティング環境１０００ａが、例示的な動作環境１０００ａにおいて示されたコンポーネントの任意の１つまたは組合せに関する任意の依存性または要件を有すると解釈されるべきでもない。
【０１５３】
図１０を参照すると、本発明を実装する例示的なリモート装置は、汎用目的コンピューティング装置をコンピュータ１０１０ａの形で含む。コンピュータ１０１０ａのコンポーネントは、処理ユニット１０２０ａ、システムメモリ１０３０ａ、およびシステムメモリを含む様々なシステムコンポーネントを処理ユニット１０２０ａに結合するシステムバス１０２１ａを含むことができるがこれらに限らない。システムバス１０２１ａは、メモリバスまたはメモリコントローラ、周辺バス、および様々なバスアーキテクチャのうち任意のものを用いるローカルバスを含む数種のバス構造のうち任意のものであることができる。
【０１５４】
コンピュータ１０１０ａは一般に様々なコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータ１０１０ａによりアクセス可能な任意の利用可能媒体であることができる。限定ではなく例として、コンピュータ可読媒体はコンピュータ記憶媒体および通信媒体を含むことができる。コンピュータ記憶媒体には、コンピュータ可読命令、データ構造、プログラムモジュールまたは他のデータのような情報を記憶するための任意の方法または技術で実装された、揮発性および不揮発性媒体、取り外し可能および取り外し不能媒体の両方が含まれる。コンピュータ記憶媒体には、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリもしくは他のメモリ技術、ＣＤＲＯＭ、ＤＶＤ（ｄｉｇｉｔａｌ  ｖｅｒｓａｔｉｌｅ  ｄｉｓｋ）もしくは他の光ディスク記憶、磁気カセット、磁気テープ、磁気ディスク記憶もしくは他の磁気記憶装置、または所望の情報の記憶に使用できコンピュータ１０１０ａによりアクセスできる任意の他の媒体が含まれるがこれらに限られない。通信媒体は一般に、コンピュータ可読命令、データ構造、プログラムモジュールまたは他のデータを、搬送波または他のトランスポート機構のような変調されたデータ信号で具現化し、任意の情報配信媒体を含む。
【０１５５】
システムメモリ１０３０ａはコンピュータ記憶媒体を、ＲＯＭ（ｒｅａｄ  ｏｎｌｙ  ｍｅｍｏｒｙ）および／またはＲＡＭ（ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）のような揮発性および／または不揮発性メモリの形で含むことができる。ＢＩＯＳ（ｂａｓｉｃ  ｉｎｐｕｔ／ｏｕｔｐｕｔ  ｓｙｓｔｅｍ）は、例えば起動中にコンピュータ１０１０ａ内の要素間での情報を転送することを支援する基本ルーチンを含み、メモリ１０３０ａに記憶されることができる。メモリ１０３０ａは一般に、処理ユニット１０２０ａにより直接アクセス可能、および／または現在処理ユニット１０２０ａにより作業されている、データおよび／またはプログラムモジュールも含む。限定ではなく例として、メモリ１０３０ａはオペレーティングシステム、アプリケーションプログラム、他のプログラムモジュール、およびプログラムデータを含むこともできる。
【０１５６】
コンピュータ１０１０ａは他の取り外し可能／取り外し不能、揮発性／不揮発性のコンピュータ記憶媒体を含むこともできる。例えば、コンピュータ１０１０ａは、取り外し不能、不揮発性磁気媒体を読み書きするハードディスクドライブ、取り外し可能、不揮発性磁気ディスクを読み書きする磁気ディスクドライブ、および／またはＣＤ−ＲＯＭもしくは他の光媒体のような取り外し可能、不揮発性光ディスクを読み書きする光ディスクドライブを含むことができる。例示的な動作環境において使用することができる他の取り外し可能／取り外し不能、揮発性／不揮発性のコンピュータ記憶媒体には、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、ソリッドステートＲＡＭ、ソリッドステートＲＯＭ等が含まれるがこれらに限られない。ハードディスクドライブは一般にインタフェースのような取り外し不能メモリインタフェースを通してシステムバス１０２１ａに接続され、磁気ディスクドライブまたは光ディスクドライブは一般にインタフェースのような取り外し可能メモリインタフェースによりシステムバス１０２１ａに接続される。
【０１５７】
ユーザは、キーボードおよび一般にマウス、トラックボールまたはタッチパッドと呼ばれるポインティングデバイスのような入力装置を通してコンピュータ１０１０ａに命令および情報を入力することができる。他の入力装置として、マイクロフォン、ジョイスティック、ゲームパッド、衛星テレビ受信用アンテナ、スキャナ、等を含むことができる。これらおよび他の入力装置は、システムバス１０２１ａに結合されたユーザ入力１０４０ａおよび関連インタフェースを通して処理ユニット１０２０ａにしばしば接続されるが、パラレルポート、ゲームポートまたはＵＳＢ（ｕｎｉｖｅｒｓａｌ  ｓｅｒｉａｌ  ｂｕｓ）のような他のインタフェースおよびバス構造により接続されてもよい。グラフィックサブシステムをシステムバス１０２１ａに接続することもできる。モニタまたは他種の表示装置も、出力インタフェース１０５０ａのようなインタフェースを介してシステムバス１０２１ａに接続され、システムバス１０２１ａは同様にビデオメモリと通信することができる。モニタに加えて、コンピュータはスピーカおよびプリンタのような他の周辺出力装置も含むことができ、出力インタフェース１０５０ａを通してそれらを接続することができる。
【０１５８】
コンピュータ１０１０ａは、リモートコンピュータ１０７０ａのような１つまたは複数の他のリモートコンピュータに対する論理接続を用いてネットワーク環境または分散環境で動作することができ、それらのリモートコンピュータは同様に装置１０１０ａとは異なるメディア機能を有することができる。リモートコンピュータ１０７０ａはパーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピアデバイスもしくは他の共通ネットワークノード、または任意の他のリモートメディア消費装置もしくはリモートメディア送信装置であることができ、コンピュータ１０１０ａに関して上述された要素のうち任意のものまたは全てを含むことができる。図１０に示された論理接続は、ＬＡＮ（ｌｏｃａｌ  ａｒｅａ  ｎｅｔｗｏｒｋ）またはＷＡＮ（ｗｉｄｅ  ａｒｅａ  ｎｅｔｗｏｒｋ）のようなネットワーク１０７１ａを含むが、他のネットワーク／バスを含むこともできる。このようなネットワーク環境は家庭、職場、企業規模のコンピュータネットワーク、イントラネットおよびインターネットで一般的である。
【０１５９】
ＬＡＮネットワーク環境で用いるとき、コンピュータ１０１０ａはネットワークインタフェースまたはアダプタを通してＬＡＮ１０７１ａに接続される。ＷＡＮネットワーク環境で用いるとき、コンピュータ１０１０ａは一般にモデムのような通信コンポーネント、またはインターネットのようなＷＡＮ上での通信を確立するための他の手段を含む。モデムのような通信コンポーネントは、内部または外部にあることができ、入力１０４０ａのユーザ入力インタフェース、または他の適切な機構を介してシステムバス１０２１ａに接続されることができる。ネットワーク環境では、コンピュータ１０１０ａに関して示されたプログラムモジュール、またはその部分をリモートメモリ記憶装置に記憶することができる。図示および説明されたネットワーク接続は例示的であって、コンピュータ間の通信リンクを確立する他の手段を使用してもよいことが、理解されるだろう。
【０１６０】
例示的な分散コンピューティングアーキテクチャ
様々な分散コンピューティングフレームワークが、パーソナルコンピューティングおよびインターネットの集中を考慮して開発されており、今でも開発されている。個人およびビジネスユーザにはアプリケーションおよびコンピューティング装置に対してシームレスに相互運用可能でウェブ可能なインタフェースが一様に提供され、コンピューティング活動を益々ウェブブラウザ志向またはネットワーク志向にしている。
【０１６１】
例えば、ＭＩＣＲＯＳＯＦＴ「登録商標」のマネージドコードプラットフォーム、即ち、．ＮＥＴは、ウェブベースのデータ記憶およびダウンロード可能なデバイスソフトウェアのようなサーバ、ビルディングブロックサービスを含む。一般に、．ＮＥＴプラットフォームは（１）コンピューティング装置全体を協調させユーザ情報を自動的にそれらの全ての上で更新および同期させるための能力、（２）ＨＴＭＬではなくＸＭＬのより一層の使用により可能となった、ウェブページに対する強化されたインタラクティブ機能、（３）例えば電子メール、またはＯｆｆｉｃｅ．ＮＥＴのようなソフトウェアといった、様々なアプリケーションの管理に対する中央の起点から、ユーザに対する製品およびサービスのカスタマイズされたアクセスおよび配信を特徴とするオンラインサービス、（４）情報へのアクセス、ならびにユーザおよび装置間の情報の同期の効率性および容易性を高める集中型データ記憶、（５）電子メール、ファックス、および電話のような様々な通信媒体を統合するための能力、（６）開発者に対し、再利用可能モジュールを生成し、それにより生産性を高め、プログラミングエラーの数を減らすための能力、および（７）多数の他のプラットフォーム間統合機能および言語統合機能を与える。
【０１６２】
本明細書では幾つかの例示的な実施形態を、コンピューティング装置上に存在するＡＰＩ（ａｐｐｌｉｃａｔｉｏｎ  ｐｒｏｇｒａｍｍｉｎｇ  ｉｎｔｅｒｆａｃｅ）のようなソフトウェアに関連して説明するが、本発明の１つまたは複数の部分をオペレーティングシステム、または「ミドルマン」オブジェクト、制御オブジェクト、ハードウェア、ファームウェア、中間言語の命令もしくはオブジェクト、等を介して実装し、本発明に従うＱＦＸの実施形態は、．ＮＥＴコードのようなマネージドコードにより可能となる言語およびサービスの全て、および他の分散コンピューティングフレームワークにも含まれ、それらでサポートされ、それらを介してアクセスすることもできる。
【０１６３】
例えば、適切なＡＰＩ、ツールキット、ドライバコード、オペレーティングシステム、制御、スタンドアローンまたはダウンロード可能ソフトウェアオブジェクト、等といった、本発明のＱＦＸの使用を可能とする複数の本発明の実装方法がある。本発明は、ＡＰＩ（または他のソフトウェアオブジェクト）の観点からの、および本発明に従ってＱＦＸの少なくとも一部を実装できるデータ構造、ソフトウェアまたはハードウェアオブジェクトの視点からの、本発明の使用を意図する。従って、本明細書で説明された本発明の様々な実装は、全体としてハードウェアである態様、部分的にハードウェアで部分的にソフトウェアである態様、ならびにソフトウェアである態様を有することができる。
【０１６４】
「例示的」という言葉は本明細書では例、事例、または実例としての役割を果たすことを意味している。誤解を避けるため、本明細書で開示された主題はこのような例によって限定されない。さらに、本明細書で「例示的」として説明された任意の態様または設計は必ずしも他の態様または設計に対して好適または有利であると解釈されるべきではなく、当業者に公知である等価な例示的構造および技術を除外することも意味しない。さらに、用語「含まれる」、「有する」、「含む」、および他の同様な単語を「発明を実施するための形態」または請求項の何れかで使用する限りでは、誤解を避けるため、このような用語はどの追加の要素または他の要素も除外せず、非制限的な移行語としての用語「備える」と同様に包括的であることが意図される。
【０１６５】
上述されたように、本発明の例示的な実施形態を様々なコンピューティング装置およびネットワークアーキテクチャに関連して説明してきたが、根本の概念を、変換を実装するＭＦＳＴを含むことが望ましい任意のコンピューティング装置またはシステムに適用することができる。例えば、本発明のＱＦＸを、装置上の別々のオブジェクトとして、別のオブジェクトの一部として、再利用制御として、サーバからダウンロード可能なオブジェクトとして、装置またはオブジェクトとネットワークとの間の「ミドルマン」として、分散オブジェクトとして、ハードウェアとして、メモリ内で、前述の任意の組合せ、等で与えて、コンピューティング装置のオペレーティングシステムに適用することができる。例示的なプログラミング言語、名前および例を本明細書では様々な選択肢の代表として選択したが、これらの言語、名前および例は限定することを意図されない。当業者は、本発明の様々な実施形態により実現されるものと同一、同様または均等な機能性を実現するオブジェクトコードおよび命名法を与える多数の方法があることを理解するであろう。
【０１６６】
述べたように、本明細書で説明された様々な技術を、ハードウェアもしくはソフトウェアに関連して、または必要に応じてその両方の組合せに関連して実装することができる。本明細書で用いる際、用語「コンポーネント」、「システム」等は同様に、コンピュータに関連するエンティティを指し、ハードウェア、ハードウェアおよびソフトウェアの組合せ、ソフトウェア、または実行中のソフトウェアの何れかを指すことを意図している。例えば、コンポーネントは、プロセッサ上で実行されるプロセス、プロセッサ、オブジェクト、実行ファイル、実行スレッド、プログラム、および／またはコンピュータであることができるが、これらに限らない。例として、コンピュータ上で実行するアプリケーションおよびコンピュータの両方はコンポーネントであることができる。１つまたは複数のコンポーネントはプロセスおよび／または実行スレッド内部に存在することができ、コンポーネントを１つのコンピュータ上にローカライズすることができ、および／または複数のコンピュータ間で分散させることができる。
【０１６７】
このように、本発明の方法および機器、またはその或る特定の態様またはその部分は、フロッピー（登録商標）ディスク、ＣＤ−ＲＯＭ、ハードドライブ、または任意の他の機械可読記憶媒体のような有形媒体内に具現化されたプログラムコード（即ち、命令）の形を取ることができ、この場合、プログラムコードをコンピュータのような機械にロードしてその機械で実行するとき、その機械は本発明を実践する機器となる。プログラム可能なコンピュータ上でのプログラムコード実行の場合、コンピューティング装置は一般にプロセッサ、そのプロセッサにより読取可能な記憶媒体（揮発性および不揮発性メモリ、および／または記憶要素を含む）、少なくとも１つの入力装置、少なくとも１つの出力装置を含む。例えば、データ処理ＡＰＩ、ソフトウェアオブジェクト、等の使用を通して本発明のＱＦＸを実装または利用できる１つまたは複数のプログラムを、好ましくは高レベルな手続きプログラミング言語またはオブジェクト指向プログラミング言語で実装してコンピュータシステムと通信させる。しかしながら、必要に応じて、プログラムをアセンブリ言語または機械言語で実装することができる。何れの場合でも、言語はコンパイル言語またはインタプリタ言語であることができ、ハードウェア実装と組み合わされることができる。
【０１６８】
電線またはケーブル線上で、光ファイバを通して、または任意の他の伝送形態を介してのように何らかの伝送媒体上で送信されるプログラムコードの形で具現化された通信を介して、本発明の方法および機器を実践することもできる。この場合、プログラムコードを、ＥＰＲＯＭ、ゲートアレイ、ＰＬＤ（ｐｒｏｇｒａｍｍａｂｌｅ  ｌｏｇｉｃ  ｄｅｖｉｃｅ）、クライアントコンピュータ、等のような機械により受信し、その機械にロードして、その機械により実行すると、その機械は本発明を実践する機器となる。汎用目的プロセッサ上に実装されるとき、プログラムコードはプロセッサと組み合わされて、本発明の機能性を起動するよう動作する一意な機器を提供する。さらに、本発明に関連して使用される任意の記憶技術は常にハードウェアおよびソフトウェアの組合せであることができる。
【０１６９】
さらに、開示された主題をシステム、メソッド、機器、または標準プログラミング技術および／もしくはエンジニアリング技術を用いた製品として実装して、本明細書で詳述された態様を実装するコンピュータまたはプロセッサベースの装置を制御するためのソフトウェア、ファームウェア、ハードウェア、またはその任意の組合せを作成することができる。用語「製品」（または、代替的に「コンピュータプログラム製品」）は、本明細書で用いられる場合は任意のコンピュータ可読装置、キャリア、または媒体からアクセス可能なコンピュータプログラムを網羅することを意図している。例えば、コンピュータ可読媒体は磁気記憶装置（例えば、ハードディスク、フロッピー（登録商標）ディスク、磁気ストリップ・・・）、光ディスク（例えば、ＣＤ（ｃｏｍｐａｃｔ  ｄｉｓｋ）、ＤＶＤ（ｄｉｇｉｔａｌ  ｖｅｒｓａｔｉｌｅ  ｄｉｓｋ・・・）、スマートカード、およびフラッシュメモリ装置（例えば、カード、スティック）を含むことができるが、これらに限られない。さらに、搬送波を使用して、電子メールの送受信に使用されるもの、またはインターネットまたはＬＡＮ（ｌｏｃａｌ  ａｒｅａ  ｎｅｔｗｏｒｋ）といったネットワークへのアクセスに使用されるもののようなコンピュータ可読電子データを運ぶことができることが知られている。
【０１７０】
前述のシステムを、幾つかのコンポーネント間の相互作用に関して説明した。このようなシステムおよびコンポーネントは、それらのコンポーネントまたは特定のサブコンポーネント、特定コンポーネントもしくはサブコンポーネントの一部、および／または追加のコンポーネントを、それらの様々な順列および組合せによって含むことが可能なことを、理解することができる。サブコンポーネントを、親コンポーネント（階層的）内に含まれるのではなく他のコンポーネントに通信可能に結合したコンポーネントとして実装することもできる。さらに、１つまたは複数のコンポーネントを、集計機能性を与える単一のコンポーネントに統合すること、または幾つかの別々のサブコンポーネントに分割することができ、管理層のような任意の１つまたは複数の中間層を与えてこのようなサブコンポーネントに通信可能に結合して統合機能性を提供できることに留意すべきである。本明細書で説明された任意のコンポーネントは、本明細書で具体的に説明されていないが当業者によって一般に知られている１つまたは複数の他のコンポーネントと相互作用することもできる。
【０１７１】
上述された例示的なシステムを考慮すると、開示された主題に従って実装できる方法論を、図５のフローチャートを参照してより良く理解することができる。説明の単純化の目的のため、その方法論を一連のブロックとして図示および説明してあるが、当然のことながら、特許請求の範囲に記載された主題はブロックの順序により限定されないことが理解されて認識されるべきである。なぜなら、幾つかのブロックは異なる順序で、および／もしくは他のブロックと同時に起こることができ、または別の方法で、その幾つかのブロックは、本明細書で示されおよび説明されたものから、等価な機能性を提供できるからである。非逐次的なフロー、または分岐があるフローをフローチャートを介して示す場合、同一または同様な結果を実現する様々な他の分岐、フロー経路、およびブロックの順序を実装可能であることを、理解することができる。さらに、全ての示されたブロックが、以降説明される方法論を実装する必要はない。
【０１７２】
さらに、理解できるように、上で開示されたシステムおよび以下の方法の様々な部分は、人工知能もしくは知識またはルールベースのコンポーネント、サブコンポーネント、プロセス、手段、方法論、またはメカニズム（例えば、サポートベクトルマシン、ニューラルネットワーク、エキスパートシステム、ベイジアンビリーフネット、ファジーロジック、データフュージョンエンジン、分類器・・・）を含むか、またはそれらから成ることができる。このようなコンポーネントはとりわけ、或る特定のメカニズムまたはそれにより実施されるプロセスを自動化して、ＱＦＸの部分をより適応的、および効率的且つ知的にすることができる。
【０１７３】
本発明を様々な図面の好適な実施形態に関連して説明したが、当然のことながら、他の同様な実施形態を使用でき、または説明された実施形態に修正および追加を行って、本発明の同一機能をそこから逸脱せずに実施することができる。例えば、本発明の例示的なネットワーク環境を、ピアツーピアネットワーク環境のようなネットワーク環境のコンテキストで説明したが、当業者は、本発明がそれに限定されないこと、および本出願で説明されたように本方法を有線または無線に関わらず、ゲームコンソール、ハンドヘルドコンピュータ、ポータブルコンピュータ、等のような任意のコンピューティング装置またはコンピューティング環境に適用でき、通信ネットワークを介して接続されネットワークにわたって相互作用する任意数のこのようなコンピューティング装置に適用できることを理解するであろう。さらに、特に無線ネットワーク装置の数が急増し続けるので、ハンドヘルド装置のオペレーティングシステムおよび他のアプリケーション固有なオペレーティングシステムを含む様々なコンピュータプラットフォームが検討されていることは強調すべきである。
【０１７４】
本発明を特定のプログラミング言語の構成概念のコンテキストで利用することに関して例示的な実施形態を説明したが、本発明はそのように限定されず、任意の言語で実装でき、動作を含む任意の文法の翻訳に適用することができる。さらに、本発明を複数の処理チップまたは装置内、またはそれらにわたって実装することができ、同様に複数の装置にわたって記憶を生じさせることができる。従って、本発明は任意の一実施形態にも限定されるべきではなく、添付された特許請求の範囲に従う幅および範囲で解釈されるべきである。
【図１Ａ】
2010503932.tif 000008
【図１Ｂ】
2010503932.tif 000009
【図１Ｃ】
2010503932.tif 000010
【図２Ａ】
2010503932.tif 000011
【図２Ｂ】
2010503932.tif 000012
【図２Ｃ】
2010503932.tif 000013
【図２Ｄ】
2010503932.tif 000014
【図２Ｅ】
2010503932.tif 000015
【図２Ｆ】
2010503932.tif 000016
【図３Ａ】
2010503932.tif 000017
【図３Ｂ】
2010503932.tif 000018
【図３Ｃ】
2010503932.tif 000019
【図３Ｄ】
2010503932.tif 000020
【図３Ｅ】
2010503932.tif 000021
【図３Ｆ】
2010503932.tif 000022
【図４Ａ】
2010503932.tif 000023
【図４Ｂ】
2010503932.tif 000024
【図５Ａ】
2010503932.tif 000025
【図５Ｂ】
2010503932.tif 000026
【図５Ｃ】
2010503932.tif 000027
【図５Ｄ】
2010503932.tif 000028
【図５Ｅ】
2010503932.tif 000029
【図５Ｆ】
2010503932.tif 000030
【図５Ｇ】
2010503932.tif 000031
【図５Ｈ】
2010503932.tif 000032
【図５Ｉ】
2010503932.tif 000033
【図５Ｊ】
2010503932.tif 000034
【図５Ｋ】
2010503932.tif 000035
【図５Ｌ】
2010503932.tif 000036
【図６Ａ】
2010503932.tif 000037
【図６Ｂ】
2010503932.tif 000038
【図６Ｃ】
2010503932.tif 000039
【図７Ａ】
2010503932.tif 000040
【図７Ｂ】
2010503932.tif 000041
【図８Ａ】
2010503932.tif 000042
【図８Ｂ】
2010503932.tif 000043
【図８Ｃ】
2010503932.tif 000044
【図９】
2010503932.tif 000045
【図１０】
2010503932.tif 000046
【国際調査報告】
2010503932.tif 000047
2010503932.tif 000048