(57)【要約】  状態機械の実行に推論機能を付加するためのインフラストラクチャとして、推論エンジンを利用する、拡張された状態機械。結果は、一部のまたは無秩序な情報を操作しうる状態機械であって、形式上トラバースされていない中間状態を推論する状態機械である。さらに、特に予想外の状況において、状態タイムアウトや遷移優先順のような制御は、状態機械の実行のより細かい制御を可能にする。
2009501387.tif 000002
【特許請求の範囲】
【請求項１】
複数の状態と事象に依存するそれらの間の遷移とによって定義される状態機械から構成され、
順序が狂った事象の正常な完了の観測から、前記状態機械への１つまたはそれ以上の欠落した事象入力について起こりそうな完了の推論を可能にするように、かつ、前記欠落した事象入力のない前記状態の現状態から、前記順序が狂った事象の前記正常な完了に伴う前記状態の新たな状態に前記状態機械が進行することを可能にするように、構成される推論エンジンを含む、
処理システム。
【請求項２】
さらに前記推論エンジンは、前記１つまたはそれ以上の欠落した事象入力を受理しだいその推論の妥当性を確認するように構成される請求項１に記載の処理システム。
【請求項３】
前記状態機械は、その状態のうち少なくとも１つの状態に付随する少なくとも１つのタイムアウト手段によって構成され、前記タイムアウト手段は、指定された事象入力の受理に先立つ前記タイムアウト手段を定義する時間フレームの経過しだい、その複数の状態のうち他の状態に前記状態機械を遷移させるように構成される請求項１に記載の処理システム。
【請求項４】
１つの明示的な事象発生よりもむしろ１つまたはそれ以上の事象条件によって定義される、少なくとも１つの遷移関数によって前記状態機械は構成される請求項１に記載の処理システム。
【請求項５】
事象条件は事象発生を含む請求項４に記載の処理システム。
【請求項６】
１つまたはそれ以上の動作は優先順位のある遷移関数に付随し、かつ、状態遷移が起こりうるとき１つまたはそれ以上の事象条件のうちの１つ以上が真である場合に、最優先順位を有する変換関数に従って次状態に遷移するように前記状態機械は構成される、請求項４に記載の処理システム。
【請求項７】
順序が狂った事象の正常な完了の観測から、複数の状態と事象に依存するそれらの間の遷移とによって定義される状態機械への１つまたはそれ以上の欠落した事象入力について起こりそうな完了を推量することと、前記欠落した事象入力のない前記状態の現状態から、前記順序が狂った事象の前記正常な完了に伴う前記状態の新たな状態に前記状態機械が進むことを可能にすること、を備える方法。
【請求項８】
前記状態機械は、別の事象状態よりも高い優先順位を有するある事象条件に付随する、前記状態の新たな状態に進む請求項７に記載の方法。
【請求項９】
前記１つまたはそれ以上の欠落した事象入力を受理しだい推論の妥当性を確認すること、をさらに備える請求項７に記載の方法。
【請求項１０】
指定された事象入力の受理に先だってタイムアウト期間の経過しだい、その複数の状態のうちの選択されたある状態に前記状態機械を遷移させること、をさらに備える請求項７に記載の方法。
【請求項１１】
１つの事象発生よりもむしろある事象状態に基づく、その複数の状態のうちの選択されたある状態に、前記状態機械を遷移させること、をさらに備える請求項７に記載の方法。
【請求項１２】
具体化されたコンピュータ読取り可能な命令を有し、前記命令は、前記命令を読取り実行するように構成される１つまたはそれ以上の処理要素によって実行されるとき、順序が狂った事象の正常な完了の観測から、前記処理要素に、複数の状態と事象に依存するそれらの間の遷移とによって定義される状態機械への１つまたはそれ以上の欠落した事象入力について起こりそうな完了を推量させ、かつ、前記欠落した事象入力のない前記状態の現状態から、前記順序が狂った事象の前記正常な完了に伴う前記状態の新たな状態に前記状態機械が進むことを可能にさせる、
コンピュータ読取り可能媒体。
【請求項１３】
前記命令は、別の事象条件よりも高い優先順位を有するある事象条件に付随する、前記状態の新たな状態に前記状態機械が進むように、前記処理要素に前記命令をさらに実行させる請求項１２に記載のコンピュータ読取り可能媒体。
【請求項１４】
前記命令は、前記１つまたはそれ以上の欠落した事象入力を受理しだい推論の妥当性を確認するように、前記処理要素に前記命令をさらに実行させる請求項１２に記載のコンピュータ読取り可能媒体。
【請求項１５】
前記命令は、指定された事象入力の受理に先だってタイムアウト期間の経過しだい、その複数の状態のうちの選択されたある状態に前記状態機械を遷移させるように、前記処理要素にさらに実行させる請求項１２に記載のコンピュータ読取り可能媒体。
【請求項１６】
前記命令は、１つの事象発生よりもむしろある事象状態に基づく、その複数の状態のうちの選択されたある状態に前記状態機械を遷移させるように、前記処理要素にさらに実行させる請求項１２に記載のコンピュータ読取り可能媒体。
【請求項１７】
クライアントによる要求に応じて前記クライアントに対してダウンロード可能なコンピュータ読取り可能命令を提供するように構成されたサーバであって、
前記命令は、順序が狂った事象の正常な完了の観測から、複数の状態と事象に依存するそれらの間の遷移とによって定義される状態機械への１つまたはそれ以上の欠落した事象入力について起こりそうな完了を推量し、かつ、前記欠落した事象入力のない前記状態の現状態から、前記順序が狂った事象の前記正常な完了に伴う前記状態の新たな状態に前記状態機械が進むことを可能にする、
ためのコンピュータ実行可能処理を定義するサーバ。
【請求項１８】
前記命令は、前記状態機械に対して、別の事象状態よりも高い優先順位を有するある事象状態に付随する、前記状態の新たな状態に進むように、コンピュータ実行可能処理をさらに定義する請求項１７に記載のサーバ。
【請求項１９】
前記命令は、前記１つまたはそれ以上の欠落した事象入力を受理しだい推論の妥当性を確認するために、コンピュータ実行可能処理をさらに定義する請求項１７に記載のサーバ。
【請求項２０】
前記命令は、前記状態機械に対して、指定された事象入力の受理に先だってタイムアウト期間の経過しだい、その複数の状態のうちの選択されたある状態に遷移させるために、コンピュータ実行可能処理をさらに定義する請求項１７に記載のサーバ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一部のまたは無秩序な情報において動作しうる状態機械であって、形式的にまだトラバースされていない中間状態を推論する状態機械に関する。
【背景技術】
【０００２】
多くの一般的な項目や状況におけるふるまいは、有限状態機械（ＦＳＭ）と呼ばれる、単純であるが強力なツールを使用してモデル化されうる。状態機械に効率的に変換されてきた機能の実例は、信号処理アルゴリズムに対するベクトル制御、データの符号化および復号化、暗号化および符合解読、事象のモニタリング、単純な機械制御機能を含む。ＦＳＭは、通常、遷移によって相互に連接される状態を含む有向グラフの形式で示される。状態機械の状態を定義し、かつ、状態遷移を示す有向線にこれらの状態を連接することによってモデル化される、システムの表示を“描く”ことを設計者に可能にする、多くのコンピュータツールがある。一般的に、このようなモデルは、モデル化されるシステムから独立しており、物理的システムが開発される前または後に作成されうる。
【０００３】
一般的に、１つもしくはそれ以上の入力の消費または他の事象の発生を表す、ある状態から別の状態への遷移により、順序立った状態における順序づけを介してトラバースする、ディジタル（ときに機械的）装置がＦＳＭである。ある場合において、状態遷移は、さまざまな動作によって補われる。コンピュータプロセッサが読み込み理解しうる、一組のコンピュータ可読命令として、および／または、個々の操作を実行するための論理ゲートの集合として、ＦＳＭは具現化されうる。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
典型的に、状態機械は、２つの明確な機能ブロックである次状態デコーダおよび出力デコーダを含むであろう。次状態デコーダは、状態機械の次状態（すなわち、現状態や一組の入力に基づいて）を規定し、一方、出力デコーダは、実際の出力を生成する。入力によって指示されるとおりに、状態機械が状態の順序をトラバースすることを確実にする役割を果たすのが次状態デコーダであり、一方、出力デコーダは、状態遷移に基づく出力信号の順序を提供する。時に、これらの出力は、ＦＳＭへの入力として、例えば、１つまたはそれ以上の帰還信号によって、戻されうる。
【０００５】
次に、状態機械の顕著な特徴は、そのプロセス指向性である。究極的な目標もしくは最終状態まで、状態機械は、状態から状態に、別の言い方をすると、主要管理点から主要管理点に、時間が経つにつれて移動する。一般に、状態機械は、これらの処理において可逆的である。これは、状態機械が、それらの入力を順番に、損失なく、消費するということである。この前提は、多くの領域で理にかなっているが、全部というわけではない。特に、状態機械の入力が、分散型構成における複数のシステムによって提供される、一連のデータ項目であるとき、順序は壊されるかもしれないし、データは失われるかもしれない。このような状況において、従来の状態機械は、立ち往生するか、または、誤った状態遷移を生成する。すなわち、いずれの結果も受け入れがたい。したがって、入力データが順番が狂って届く状況をうまく処理することができるか、あるいはそのような誤りを全く経験することのない、状態機械が必要である。
【課題を解決するための手段】
【０００６】
ある実施形態において、複数の状態と事象に依存するそれらの間の遷移とによって定義される状態機械と、１つまたはそれ以上の順序が狂った他の事象の正常な完了の観測から、状態機械への１つまたはそれ以上の欠落した事象入力について起こりそうな完了の推論を可能にするように構成される推論エンジンと、からなる処理システムを、本発明は提供する。このように、欠落した事象入力がない状態であっても、状態機械がその現状態から、異順序事象の完了に伴う新たな状態に進むことを、推論エンジンは可能にする。これらの欠落した入力が後に受理される場合、推論エンジンは、これらに応じて、その推論（すなわち、その計算された状態遷移）の妥当性を確認するように構成されうる。
【０００７】
状態機械は、１つまたはそれ以上のその状態に応じたタイムアウト手段を含みうる。タイムアウト手段は、指定された事象入力の受理に先立って、タイムアウトを定義する時間フレームの経過しだい、状態機械を指定された状態に遷移させることができる。また、状態機械は、明示的な事象の発生というよりはむしろ１つまたはそれ以上の事象状態によって定義される、少なくとも１つの遷移関数によって構成されうる。このような事象状態は、優先順位の遷移関数を有してもよく、また状態機械は、現状態から、（例えば、状態遷移が起こりうるときに、２つ以上の事象条件は真である場合のような）最優先順位を有する変換関数に応じて１つまたはそれ以上の次状態へ遷移するように構成されてもよい。
【０００８】
本発明は、下記添付の図において、例として示されるが、これらに限定されない。なお、図中同一または相当部分には同一符号を付し、その説明は繰り返さない。
【発明を実施するための最良の形態】
【０００９】
ここに記載されるのは、状態機械の実行に推論機能を付加するためのインフラストラクチャとして推論エンジンを利用する拡張された状態機械である。結果は、一部のまたは無秩序な情報を操作しうる状態機械であって、形式的にまだトラバースされていない中間状態を推論する。さらに、特に予期せぬ状況において、状態タイムアウトや遷移優先のような制御は、状態機械の実行のよりよい制御を可能にする。
【００１０】
本発明は、それについての種々の実施例や実施形態について考察されるが、これらの実施例が、本明細書に付属する請求項に特定される発明の範囲を制限することを意図しないことは留意されるべきである。さらに、本発明の種々の実施形態は、（プログラムまたはルーチンとして知られる）コンピュータ実装処理または方法の補助によって実現されうる。コンピュータ実装処理または方法は、Ｃ＃、Ｃ／Ｃ＋＋、Ｆｏｒｔｒａｎ、ＣＯＢＯＬ、ＰＡＳＣＡＬ、アセンブリ言語、マークアップ言語（例えば、ｘｍｉ、ＨＴＭＬ、ＳＧＭＬ、ＸＭＬ、ＶｏＸＭＬ）等と同様に、共通オブジェクト・リクエスト・ブローカ・アーキテクチャ（ＣＯＲＢＡ）、Ｊａｖａ（登録商標）等のようなオブジェクト指向環境も、制限なく、いかなるコンピュータ言語にも翻訳されうる。しかしながら、一般に、ここで使用される上記の用語のすべては、任意の目的を達成するために順番に実行される一連の論理ステップを含むように、かつ、（例えば、状態表の整備等によって）モデル化されたシステムに関する状態情報を保持するように、意図される。
【００１１】
上述の観点において、下記詳細な説明の一部が、コンピュータメモリ内データ上の動作のアルゴリズムおよび記号表示について示されることは、理解されるべきである。これらのアルゴリズム的記載および表示は、コンピュータ科学技術における知識を有する者によって、その処理実体を当該技術の他の当業者に最も効果的に伝達するために使用される手段である。ここでは、一般的に、アルゴリズムは、所望の結果に導く自己矛盾のない一連のステップであると解される。ステップは、物理的量の物理的な操作を要求するものである。必ずしも必要ではないが、通常、格納され、転送され、結合され、比較され、およびさもなければ操作されることが可能な、電気信号または磁気信号の形を、これらの物理的量はとる。ビット、値、要素、記号、文字、用語、数字等のようなこれらの信号を参照することは、主に標準使用という理由で、時に便利であることが実証済みである。しかしながら、これらのすべておよび類似の用語が、しかるべき物理的量に付随し、かつ、これらの量に該当する単に便利な標識にすぎないことは、念頭に置かれるべきである。コンピュータシステムのレジスタおよびメモリ内の物理的（電子的）量として表されるデータを、コンピュータシステムのメモリ、レジスタ、または他のそのような情報記憶、伝達、もしくは表示装置内の物理的量として同じように表される他のデータに処理し変換する、コンピュータシステムまたは同様の電子計算装置の動作および処理について、特に言明しないかぎり、本発明の明細書全体にわたって、例えば、“処理”、“演算”、“計算”、“決定”、“表示”等の用語の使用が意味することは正しく理解されるであろう。
【００１２】
本発明は、ここに記述される操作を実行するための装置により実装されうる。この装置は、要求される目的のために特別に製造されてもよいし、コンピュータに格納されるコンピュータプログラムによって選択的に作動しもしくは再構成される、汎用コンピュータから構成されてもよい。このようなコンピュータプログラムは、コンピュータ読取り可能格納媒体、例えば、下記に限定されないが、フロッピーディスク、光ディスク、ＣＤ−ＲＯＭ、磁気光ディスク、読取り専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気もしくは光カードを含む各種ディスク、または電子命令を格納するために好適でかつそれぞれがコンピュータシステムバスに結合される各種媒体等の中に、格納されうる。さらに、コンピュータ読取り命令は、ある要求に反応してクライアントに命令を与えるように構成されるサーバに格納されうる。このような要求は、通常の通信路、例えば、ｆｔｐ、ｈｔｔｐまたはｈｔｔｐ要求（または他のファイル転送要求）を介して、または（例えば、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワークもしくはインターネットのような）１つもしくは複数のネットワークあるいはネットワークのネットワークを介して、届いてよい。
【００１３】
ここに示されるアルゴリズムおよび処理は、元来、特定のコンピュータまたは他の装置に応じたものではない。種々の汎用システムが、ここにいう教示に係るプログラムによって使用されてもよいし、または要求された方法を実現するためにより特化された装置を製造することが便利であると実証されるかもしれない。例えば、本発明に係る任意の方法は、配線された回路、汎用プロセッサのプログラミング、またはハードウェアとソフトウェアの任意の組合せによって、実装されうる。ハンドヘルド装置、マルチプロセッサシステム、マイクロプロセッサベースのもしくはプログラマブルの大衆消費電子製品、ＤＳＰ装置、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ等以外にも、それらを含むコンピュータシステム構成によって、本発明が実施されうることを、通常の知識を有する者は即座に理解するであろう。また、タスクが通信ネットワークを介してリンクされる遠隔処理装置によって実現される、分散型の演算環境において、本発明は実施されうる。これらのシステムの多様性に対する必要な構造は、下記説明から明らかになるであろう。
【００１４】
上述に指摘したとおり、有限状態機械は、しばしばデータ処理をモデル化する方法として使用される。これは、現実の（すなわち、物理的な）システム（しばしば複雑であり、多くのサブシステムを包含しうる）が、状態機械によって仮想の意味において抽出され表示されうるということである。このようなモデルは、例えば、所定の入力に対する物理的システムにおける潜在的出力を決定したい場合に、有効である。物理的システムそれ自身を使用してこのような決定をすることは、実際的ではない（実際、ときに不可能である）一方、このシステム（すなわち、状態機械）の仮想の表示は、しばしばこのような目的に使用されうる。その代わりに、あるいはこれに加えて、状態機械は、物理的システム内の処理を追従するように使用されてもよい。そのような“追従および追跡の”実施は、物理的システムが多くのサブシステムに広く分散する場合に、および／または、トランザクション監視機能の他の形態が、実行するには実際的でないかあるいは困難な場合に、特に有用である。また、状態機械は、複雑なソフトウェア駆動システムのようなコンピュータ利用システムの状態を追従するためのモデルとして使用されうる。
【００１５】
非決定性有限状態機械のより正式な定義は、５個組（Ｓ、Σ、Ｔ、ｓ、Ｆ）からなる。すなわち、
Ｓは、状態の有限集合であり、
Σは、有限の入力アルファベットであり、
Ｔは、状態集合に対して状態／アルファベットの対を割り当てる遷移関数、すなわち、
２Ｓに対するＳｘ（ΣE｛e｝）であり、ここで２Ｓは、Ｓのベキ集合を示すものであって、
ｓは、Ｓの１つの要素であり、開始状態を示し、
Ｆは、Ｓの部分集合であり、最終状態を示す。
（ΣE｛e｝）の要素を構成する入力文字列ｘ１、ｘ２、ｘ３、．．．、ｘｎが与えられるとすると、
ｓ０＝ｓ、
ｓｉ＋１は、ｉ＝０、１、．．．、ｎ−１で、Ｔ（ｓｉ、ｘｉ）の集合要素であり、
ｓｎは、Ｆの要素
である一連の状態ｓ０、ｓ１、ｓ２、．．．、ｓｎを通って状態機械が実行できるならば、非決定性有限状態機械は、文字列を受理する。このように、状態機械はその開始状態において開始され、遷移は入力文字列の各要素ごとに生成される。入力文字列のすべての要素が処理された後の最終状態に状態機械がおかれるときかつそのときに限って、文字列は受理されたとみなされる。
【００１６】
例えば、図１に示される状態機械１０を考察する。ここで、
Ｓ＝｛Ａ、Ｂ、Ｃ、Ｄ、Ｅ｝、
Σ＝｛０、１｝、
Ｔは、
Ｔ（Ａ、０）＝｛Ｂ、Ｄ｝、
Ｔ（Ａ、１）＝｛Ｄ｝、
Ｔ（Ｂ、１）＝｛Ｃ｝、
Ｔ（Ｃ、０）＝｛Ｅ｝、
Ｔ（Ｄ、０）＝｛Ｅ｝のように示され、
ｓ＝Ａ、
Ｆ＝｛Ｅ｝である。
示されるように、許容状態（Ａ、Ｂ、Ｃ、ＤおよびＥ）を示すグラフノードと、それらの状態の間の遷移を示すグラフのラベル付き円弧を用いて、この状態機械１０は有向グラフとして図示されうる。この場合、円弧上のラベルは、遷移に割り当てられるアルファベット要素を示す。このように、状態“Ａ”は開始状態、状態“Ｅ”は最終状態、確定された入力文字列は、“０１０”、“００”、および“１０”である。中間状態での入力の消費を表す、状態Ａから状態Ｅへの遷移、を形成することに加えて、いくつかまたはすべての遷移は、実行される動作に随伴されてもよい。このように、入力の消費は、入力受理決定を導くだけでなく、動作または出力も同様に実行させうる。
【００１７】
従来の状態機械は、これらの処理において典型的に情報が失われないものに限定される。すなわち、従来の状態機械は、その入力を順番にかつ損失なく消費する。このようなモデルは、多くの領域で妥当ではあるが、すべてではない。特に、状態機械の入力が、分散応用アーキテクチャにおける複数のシステムまたはサブシステムによって供給される一連のデータ項目であるとき、順序は崩されるかもしれず、またデータが失われるかもしれない。このような状況において、従来の状態機械は、たびたび立ち往生するか、さもなければ誤作動する。
【００１８】
対照的に、本発明は従来の有限状態機械に機能拡張を与え、状態機械に誤順序のまたは失われたデータに対処することを可能にする。ある実施形態において、１つまたはそれ以上の入力が壊れていなかったとしたならば状態機械がとったであろうパスを予測するのに、推論エンジンは使用される。従来の状態機械が立ち往生するかまたは誤った遷移を形成するような状況において、この推論機構は、状態機械が演算処理を持続することを可能にする。
【００１９】
残された課題は非決定性状態機械に集中するが、それは決定性状態機械と同様に適用される。（空の入力文字、εを受理しない状態機械であって、一組の状態にというよりもむしろ単一の状態に対して状態／入力の対を遷移関数が割り当てる）決定性状態機械は、それらの非決定性相当物の部分集合である。さらに、各非決定性状態機械は決定性状態機械に変換されうる。
【００２０】
本発明をよりよく理解するために、状態機械が、複数の分配システムおよび／またはサブシステムを含むビジネスプロセスフロー（例えば、保険金請求処理、携帯電話トランザクション処理の要求と達成、コンテンツの公開と発行等）を監視するように使用される、追従および追跡の実施を考察されたい。状態機械のジョブは、ビジネスシステムの包括的な進行を追従および追跡するためのものである。包括的なビジネスシステムを組み立てる各個別のシステム／サブシステムは、中間のタスクの完了を知らせる１つまたはそれ以上の出力を、生成しうるし、状態機械によるこれらの出力処理は、包括的なシステムの進行を追従することを可能にする。図２は、２つのサブシステム３０ａと３０ｂを状態機械２０が追従および追跡するために使用される本概念の基本的な実施例を示す。
【００２１】
サブシステム３０ａと３０ｂのいずれもが事象の完了を知らせていないことを、開始状態２２は示す。状態２４は、サブシステム３０ａが事象１をすでに送ったことを示す。状態２６は、サブシステム３０ａが事象１をすでに送ったことと、サブシステム３０ｂが事象２をすでに送ったことを示す。状態２８（最終状態）は、サブシステム３０ａが事象１をすでに送っていることと、サブシステム３０ｂが事象２をすでに送ったことと、サブシステム３０ｂが事象３をすでに送ったことを示す。
【００２２】
入力事象に基づいて状態遷移を追従することに加えて、任意の個別遷移における動作を実行するように状態機械２０は補われうる。例えば、事象２の発生における状態遷移をマップするのに加えて、状態２４と２６の間の遷移関数は（出力を生成するような）動作を起動しうる。動作は、データベース内にデータを格納することや、別の状態機械にある事象を知らせること等を含みうる。
【００２３】
状態機械２０がその入力を順番に消費するかぎりにおいて、追加の入力要素（本実施例において事象２および３）が処理に対して有効になるまで、中間状態２４および２６で待ちながら、サブシステム３０ａと３０ｂによる動作の観測は次に進みうる。しかしながら、状態機械への入力が多くの別個のサブシステムによって動的に生成されうる場合に、このような分散形システムにおいては、状態機械へのいくつかの入力は遅延するか完全に失われうる可能性がある。例えば、サブシステム３０ｂの事象２の出力の欠落が発生した場合、図３に示される状況が考えられるであろう。
【００２４】
事象２のような入力の欠落は、従来の状態機械を状態２４において立ち往生し、先に進むこともできず、分散形システムのさらなる進捗を正常に追従することもできない原因に大いになりうる。もしこのような欠落が、監視される実際のサブシステムの故障というよりはむしろ通信障害（例えば、ネットワークの停止あるいは他の事象）によるものであったとすれば、実際には存在しない障害を調査するための無用な金額を、システムのオペレータは結局費やすかもしれない。さらに、物理的システムによって処理される追加の業務処理は記録されないかもしれず、収益機会または他のビジネスを失う結果をもたらす。
【００２５】
図３に示されるような状況において、従来の状態機械が立ち往生する理由は、一般に、このような状態機械が、これらの公式定義の静的状態で動作するようにコンピュータ読取り命令（すなわち、ソフトウェア）の中に実装されるからである。対照的に、本発明の実施形態に従って構成される状態機械は、推論エンジンのコンテキストの中に実装される。推論エンジンは、“推論ステップ”、すなわち１つまたはそれ以上の前提からの推論の表現、を照合しまたは生成することができるコンピュータ実装処理である。これによって我々は、１つまたはそれ以上の前提から１つの結論への論理的推論を一般に表現しようとする特定の種類のデータを意味する。推論エンジンのコンテキスト内に状態機械を置くことによって、本発明は、状態間の推論される遷移を可能にする。本発明によって与えられる、従来の状態機械への他の操作上の機能拡張は、機械タイムアウトと優先的な遷移を含む。これらはそれぞれ、正規の状態機械に対する機能拡張−それは分配形システムに現れる例外的な環境等をこのような装置がうまく処理することを可能にする−を定義する。
【００２６】
推量される遷移：推論エンジン内の状態機械の実装が、入力の無秩序さまたは欠落が存在する場合において、状態遷移を形成し続ける機会を与える。特に、中間遷移を実施する必要なくあり得べき（または任意の）将来の状態について推論が形成されうる。例えば、図３に示される状態機械を再度考察されたい。もし事象２および事象３が連続している（すなわち、事象３は、事象２の発生があるまで起こり得ない）と仮定するならば、事象３の存在から、事象２が失われたことや、状態機械２０が状態２８に進み得たことを、推量することができる。
【００２７】
データが無秩序かまたは欠落したかもしれない状態において、推論を形成するための手段により、本発明の状態機械はこれを行う。特に、順序が狂って到達したかまたは他の入力が欠落した後に到達したかもしれない入力を反映する、起こりうる中間状態の集合を常に把握するように、推論エンジンベースの状態機械は構成される。追加の入力に基づいて、現在の集合から、起こりうる中間状態の新たな集合を反復的に形成するように、推論エンジンは構成される。他の場合において、１つまたは複数のパスを定義するユーザ定義基準によって、推論は到達されうる。さらに、本発明のある実施形態において、将来状態の発生は現状態の発生から推論されうるし、そのまた逆も同様である。
【００２８】
無秩序のまたは欠落した入力がある状態における進捗を推論することに加えて、順番が狂ってデータが到達する場合には、本発明の状態機械はその推論の妥当性を確認することができる。例えば、図３に示される状態機械において、｛１、３、２｝として到達する入力は、（状態２４から）状態２８への遷移を推論し、次に、順番の狂った事象２に到達しだい、状態２４から状態２６への遷移を引き続き確証することによって対処されうる。
【００２９】
状態タイムアウト：無秩序のまたは欠落した入力のような例外的な状況に対処するための第２の機構は、タイムアウト機構である。この場合、状態機械は、個々の状態に付随するタイムアウトを含みうるので、その時間フレーム内の入力の欠落は特定の遷移（例えば、誤り状態）の原因となるであろう。例えば、図４に示される状態機械４０が考えられよう。
【００３０】
本図において、サブシステム３０ａおよび３０ｂは示されないが、前述のとおり、状態遷移１、２、３は、それぞれ、状態２２と２４、２４と２６、２６と２６の間に示される。状態機械４０は、追加された状態３２、３４と、入力依存というよりもタイムアウト依存の状態２２、２４、２６からの遷移とによって補われている。この状態機械を実行するため、状態２２において３０秒以上立ち往生させる入力は、状態３２への遷移の発生をもたらすであろう。同様に、状態２４において２０秒以上立ち往生させる入力は、状態３２への遷移の発生をもたらすであろう。同様に、状態２６において３０秒以上立ち往生させる入力は、状態３４への遷移の発生をもたらすであろうし、それに続く“３”の入力は、最終状態２８への遷移をもたらすであろう。こうして、後者の場合において、誤り遷移が最終である必要はないが、遅れた入力に対する例外処理機構として利用されうることが示される。一般に、入力を読取ることのない遷移、明示状態への遷移、または“すべての状態”への遷移を含む、多くの異なるタイムアウト動作を有する状態機械の使用方法を、本発明は意図し提供する。
【００３１】
優先順の遷移：本発明のさらなる実施形態は、状態機械の遷移関数に、状態変化を起こさせる入力のような明示的な特性というよりも、条件を受理することを可能にする。例えば、図５に示される状態機械５０が考えられよう。この場合において、感知する温度の条件（すなわち、Ｔが３２°未満もしくは等しい、またはＴが３２°よりも高い）は、状態機械５０が開始状態５２から適切な係属状態５４または５６への遷移をもたらすであろう。
【００３２】
また、図６に示されるように、特定の遷移があいまいな非決定性状態機械を、本発明は提供しうる。例えば、状態機械６０において、２つの条件は同時に真である。これは、開始状態６２から状態６４（Ｔは１００°よりも高い）への遷移状態が真であると同時に、開始状態６２から状態６６（湿度（Ｈ）は８５％よりも高い）への遷移状態もまた真である、ということである。このような状況を処理するために、２つまたはそれ以上の条件が同時に真である任意の状況が決定的に解決されうるような、個別の優先順位によって遷移関数をさらに補うことを、本発明は可能にする。本実施例において、状態６２から６４への遷移はより高い優先順位を与えられうる一方、状態６２から６６への遷移はより低い優先順位を与えられうる。仮に、両方の条件が真であって状態機械６０が状態６２に到達する場合は、状態機械はより高い優先順位に基づいて状態６２に遷移するということである。
【００３３】
このように、本発明は、複数の状態と事象に依存するそれらの間の遷移とによって定義づけられる状態機械と、１つまたはそれ以上の他の異常順序事象の正常な完了の観測から、状態機械に１つまたはそれ以上の欠落した事象入力について起こりそうな完了の推論を可能にするように構成される推論エンジンと、を含む処理システムを提供する。こうして、欠落した事象入力がない場合でも、状態機械がその現状態から順序が狂った事象の完了に付随する新たな状態に進むことを、推論エンジンは可能にする。これらの欠落した入力が後に受理された場合に、推論エンジンはこれらに係るその推論（すなわち、その演算される状態遷移）の妥当性を確認するように構成されうる。
【００３４】
本発明にしたがって構成される処理システムのための部分的なソフトウェアアーキテクチャを示す図７を参照する。種々の状態、遷移事象、推論ルール等を指定するように設計されたシステムを可能にするユーザインターフェース７４（例えば、グラフィカルユーザインターフェース）を介して、推論エンジン７０と状態機械７２とは定義づけられうる。状態機械７２は、１つまたはそれ以上の状態に付随するタイムアウト手段を含み、タイムアウト手段は、指定された事象入力の受理に先立つタイムアウトを定義づける時間フレームの経過次第、状態機械が指示される状態に遷移するようにする。また状態機械７２は、ある明示的な事象発生というよりむしろ、１つまたはそれ以上の事象条件によって定義される少なくとも１つの遷移関数によって構成されうる。このような事象条件は遷移関数を優先づけしうるし、状態機械は、最優先順位を有する変換関数に基づいて、現状態から１つまたはそれ以上の次状態（例えば、状態遷移が起こりうるときに、２つ以上の事象条件が真である場合）に遷移するように構成しうる。
【００３５】
このように、状態機械の実行に推論機能を付加するためのインフラストラクチャとして、推論エンジンを利用する、拡張された状態機械が記述された。任意の図示された実施例を参照して論じられてきたが、本発明の範囲は、請求項の表記によってのみ判定されるべきである。
【図面の簡単な説明】
【００３６】
【図１】従来の有限状態機械の一例を示す図である。
【図２】複数のサブシステムの活動を追従し追跡することに使用される状態機械の一例を示す図である。
【図３】図２に示された状態機械により監視された、サブシステムの１つから欠落した入力の一例を示す図である。
【図４】本発明の実施形態に係る、タイムアウト処理をするように構成される状態機械の一例を示す図である。
【図５】本発明の実施形態に係る、状態変化に刺激を与える入力として、明示的な特性よりもむしろ条件を受理するための遷移関数によって構成される状態機械の一例を示す図である。
【図６】本発明の実施形態に係る、優先的な状態遷移の使用を可能にする非決定性状態遷移関数を有する状態機械の一例を示す図である。
【図７】本発明の実施形態に係る推論エンジンの実装に基礎をおく状態機械がその中に実現される、処理システムに対するソフトウェア・アーキテクチャの一例を示す図である。
【図１】
2009501387.tif 000003
【図２】
2009501387.tif 000004
【図３】
2009501387.tif 000005
【図４】
2009501387.tif 000006
【図５】
2009501387.tif 000007
【図６】
2009501387.tif 000008
【図７】
2009501387.tif 000009