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