(57)【特許請求の範囲】
【請求項１】
イベント間の発生順序と間隔条件とを伴ったイベントパターンに含まれる分岐パターンについて、前記分岐パターンの分岐の起点となるイベントの受理時刻を当該イベントの遷移先を示す起点ノードに対応付けて保持させる処理、前記起点ノードから前記分岐パターンの分岐先となるイベントおよび間隔条件を対応付けた分岐ノードに接続する処理、複数の分岐ノードから前記複数の分岐ノードを結合する結合点を示す結合点ノードに接続する処理を行うことで、オートマトンを生成するオートマトン生成部と、
複数のイベントの発生順序を含むイベントストリームと、前記オートマトンとを順次比較し、前記分岐パターンの分岐の起点となるイベントが前記起点ノードで受理されると、受理されたイベントの受理時刻を前記起点ノードに対応付けて保持し、前記分岐の起点となるイベントに後続するイベントが前記分岐ノードで受理されると、受理されたイベントの受理が前記分岐ノードに対応付けられた間隔条件を満たせば、該保持した受理時刻を前記分岐ノードの受理状態と共に遷移させ、前記結合点ノードにて複数の分岐ノードから遷移された受理時刻に同一の受理時刻があると、当該受理時刻を含む結合状態を更に遷移させることで、前記イベントストリームに前記イベントパターンが含まれているか否かを照合する照合部と
を有することを特徴とする照合装置。
【請求項２】
前記オートマトン生成部は、前記イベントパターンに含まれる結合パターンについて、前記結合パターンの結合の終点となるイベントの受理時刻を当該イベントの遷移先を示す分岐ノードに対応付けて保持させる処理、複数の分岐ノードから前記複数の分岐ノードを結合する結合点を示す前記結合点ノードに接続する処理を行うことで、更に前記オートマトンを生成し、
前記照合部は、前記結合パターンの結合の終点となるイベントが前記分岐ノードで受理されると、遷移元の受理状態を複製すると共に、受理されたイベントの受理時刻を前記分岐ノードに対応付けて保持し、該保持した受理時刻を該複製した受理状態と共に前記結合点ノードに遷移させ、前記結合点ノードにて複数の分岐ノードから遷移された受理時刻に前記終点となるイベントの同一の受理時刻があると、当該受理時刻を含む結合状態を更に遷移させることを特徴とする請求項１に記載の照合装置。
【請求項３】
コンピュータに、
イベント間の発生順序と間隔条件とを伴ったイベントパターンに含まれる分岐パターンについて、前記分岐パターンの分岐の起点となるイベントの受理時刻を当該イベントの遷移先を示す起点ノードに対応付けて保持させる処理、前記起点ノードから前記分岐パターンの分岐先となるイベントおよび間隔条件を対応付けた分岐ノードに接続する処理、複数の分岐ノードから前記複数の分岐ノードを結合する結合点を示す結合点ノードに接続する処理を行うことで、オートマトンを生成し、
複数のイベントの発生順序を含むイベントストリームと、前記オートマトンとを順次比較し、前記分岐パターンの分岐の起点となるイベントが前記起点ノードで受理されると、受理されたイベントの受理時刻を前記起点ノードに対応付けて保持し、前記分岐の起点となるイベントに後続するイベントが前記分岐ノードで受理されると、受理されたイベントの受理が前記分岐ノードに対応付けられた間隔条件を満たせば、保持された受理時刻を前記分岐ノードの受理状態と共に遷移させ、前記結合点ノードにて複数の分岐ノードから遷移された受理時刻に同一の受理時刻があると、当該受理時刻を含む結合状態を更に遷移させることで、前記イベントストリームに前記イベントパターンが含まれているか否かを照合する
各処理を実行させることを特徴とする照合プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、照合装置等に関する。
【背景技術】
【０００２】
ネットワーク技術やセンサー技術の発達と普及にともない、時々刻々と大量に発生するイベントの系列を、リアルタイムに処理することを目的としたイベントストリーム処理が注目されている。以下において、イベントの系列をイベントストリームと表記する。イベントストリームを処理する分野において、イベント到着順序のパターンを検出するイベントパターン照合技術が重要視されており、様々な手法が提案されている。
【０００３】
イベントパターン照合には、例えば、以下に示す３つの性質が求められる。１つ目の性質について説明する。イベントパターン照合では、イベントストリームの途中に混じったノイズイベントを無視して照合を行うことが求められる。ここで、ノイズイベントは、照合対象となるイベント以外のイベントに対応するものである。
【０００４】
２つ目の性質について説明する。イベントパターン照合では、並列パターンや選択パターン等の各種のパターン表現に対する効率のよい照合を行うことが求められる。例えば、イベントＡとイベントＢとの並列パターンは「Ａ＆Ｂ」と表される。イベントストリームに順不同で、イベントＡ、Ｂの双方が含まれていれば「Ａ＆Ｂ」は照合完了となる。これに対して、イベントＡとイベントＢとの選択パターンは、「Ａ∨Ｂ」と表される。イベントストリームに、イベントＡまたはイベントＢのどちらか一方が含まれていれば「Ａ∨Ｂ」は照合完了となる。
【０００５】
３つ目の性質について説明する。イベントパターン照合では、あるイベントの所定時間以内に特定のイベントが到着するようなイベントパターンの照合を行うことが求められる。時間差が大きい無関係な２つのイベントの照合を避けることができる。
【０００６】
次に、イベントパターンを照合する従来技術の一例について説明する。図２１は、従来技術を説明するための図である。図２１に示すように、イベントストリーム１０は、自動車の動作において５秒ごとの速度の差分を示すイベントａ、ｎ、ｚ、ａ、ｂ、ｘ、ｙ、ｃ、ｎ、ｚ・・・を含む。図２２は、イベントとイベントの説明とを対応づけた図である。図２２に示すように、イベントｃは−３０ｋｍ／ｈ以下の急減速を示し、イベントｂは−３０〜−１５ｋｍ／ｈを示し、イベントａは−１５〜−５ｋｍ／ｈを示す。また、イベントｎは−５〜５ｋｍ／ｈを示し、イベントｘは５〜１５ｋｍ／ｈを示し、イベントｙは１５〜３０ｋｍ／ｈを示し、イベントｚは３０ｋｍ／ｈ以上の急加速を示す。
【０００７】
ここでは、急加速（ｚ）後１０秒以内に急減速（ｃ）するイベントパターンＰを考える。従来技術では、イベントパターンＰと図２１に示したイベントストリーム１０とを比較する。そうすると、イベントストリーム１０の位置１０ａでイベントｚが照合され、位置１０ｂでイベントｃが照合される。ところが、位置１０ａでイベントｚを受信してから位置１０ｂでイベントｃを受信するまで２５秒であるので、イベントパターンＰを検出しない。また、位置１０ｃでイベントｚが照合され、位置１０ｄでイベントｃが照合される。この場合、位置１０ｃでイベントｚを受信してから位置１０ｄでイベントｃを受信するまで１０秒であるので、イベントパターンＰを検出する。
【０００８】
ところで、従来技術では、イベントパターンとイベントストリームを比較する場合に、イベントパターンに対応する非決定性有限オートマトン（NFA:Nondeterministic  Finite  Automaton）を生成して利用する。以下において、非決定性有限オートマトンを、オートマトンと略記する。図２３は、イベントパターンから生成される従来のオートマトンを示す図である。図２３に示すオートマトン２０は、イベントパターンＱが示す間隔条件付きイベントの並列パターンに対応するオートマトンである。すなわち、イベントパターンＱは、イベントａを受理した後、各辺に記載された間隔以内にイベントｂ、ｃ、ｄを受理し、イベントｂ、ｃ、ｄをそれぞれ受信した後、各辺に記載された間隔以内にイベントｅを受理する間隔条件付きのイベントのパターンである。
【０００９】
オートマトン２０は、ノード２１、２２、２３ａ〜２３ｆ、２４ａ〜２４ｆ、２５ａ〜２５ｆ、２６ａ〜２６ｆ、２７、２８をそれぞれ接続する。従来技術では、イベントパターンＱの間隔条件付きイベントの並列パターン「｛ｂ：（２：ａ）｝＆｛ｃ：（４：ａ）｝＆｛ｄ：（２：ａ）｝」に対応するべく、「｛ｂ：（２：ａ）｝、｛ｃ：（４：ａ）｝、｛ｄ：（２：ａ）｝」の発生順序の全ての組み合わせをノード２３ａ〜２３ｆ、２４ａ〜２４ｆ、２５ａ〜２５ｆ、２６ａ〜２６ｆで表現する。ここで、｛ｂ：（２：ａ）｝とは、イベントａとの差が２以内でイベントｂを受理することを意味する。｛ｃ：（４：ａ）｝とは、イベントａとの差が４以内でイベントｃを受理することを意味する。｛ｄ：（２：ａ）｝とは、イベントａとの差が２以内でイベントｄを受理することを意味する。そして、イベントｂとの受理時刻の差が６以内且つイベントｃとの受理時刻の差が４以内且つイベントｄとの受理時刻の差が４以内でイベントｅが受理される。なお、オートマトン２０のノードの遷移は、矢印上の間隔条件付きイベントが発生した場合に発動する。例えば、イベントストリームのイベントａの位置に到達した場合に、ノード２１からノード２２への遷移が発動する。
【００１０】
なお、オートマトン２０の「ε」はε遷移を表す。例えば、ノード２１からノード２２への遷移が発動した場合には、ノード２２からノード２３ａ〜２３ｆへのε遷移が発動する。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】A.Demers,et  al."Cayuga:A  General  Purpose  Event  Monitoring  System,"Proc.CIDR'07
【非特許文献２】J.Agrawal,et  al."Efficient  Pattern  Matching  over  Event  Streams"Proc.SIGMOD'08
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、上述した従来技術では、オートマトンを利用して間隔条件付きイベントの並列パターンを効率的に照合することができないという問題があった。
【００１３】
イベントパターンに間隔条件付きイベントの並列パターンが存在すると、図２３に示したように並列パターンに含まれる間隔条件付きイベントの発生順序の全ての組み合わせをオートマトンに含めることとなり、非効率である。例えば、並列パターンに間隔条件付きイベントがｍ個存在する場合には、ノード数がＯ（ｍ！）個となる。
【００１４】
開示の技術は、上記に鑑みてなされたものであって、オートマトンを利用して間隔条件付きイベントの並列パターンを効率的に照合することができる照合装置および照合プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
開示の照合装置は、オートマトン生成部および照合部を有する。オートマトン生成部は、イベント間の発生順序と間隔条件とを伴ったイベントパターンに含まれる分岐パターンについて、前記分岐パターンの分岐の起点となるイベントの受理時刻を当該イベントの遷移先を示す起点ノードに対応付けて保持させる処理、前記起点ノードから前記分岐パターンの分岐先となるイベントおよび間隔条件を対応付けた分岐ノードに接続する処理、複数の分岐ノードから前記複数の分岐ノードを結合する結合点を示す結合点ノードに接続する処理を行うことで、オートマトンを生成する。照合部は、イベントストリームとオートマトンとを順次比較し、イベントストリームにイベントパターンが含まれているか否かを照合する。照合部は、複数のイベントの発生順序を含むイベントストリームと、前記オートマトンとを順次比較し、前記分岐パターンの分岐の起点となるイベントが前記起点ノードで受理されると、受理されたイベントの受理時刻を前記起点ノードに対応付けて保持し、前記分岐の起点となるイベントに後続するイベントが前記分岐ノードで受理されると、受理されたイベントの受理が前記分岐ノードに対応付けられた間隔条件を満たせば、該保持した受理時刻を前記分岐ノードの受理状態と共に遷移させ、前記結合点ノードにて複数の分岐ノードから遷移された受理時刻に同一の受理時刻があると、当該受理時刻を含む結合状態を更に遷移させることで、前記イベントストリームに前記イベントパターンが含まれているか否かを照合する。
【発明の効果】
【００１６】
本願の開示する照合装置の一つの態様によれば、オートマトンを利用して間隔条件付きイベントの並列パターンを効率的に照合することができるという効果を奏する。
【図面の簡単な説明】
【００１７】
【図１】図１は、実施例に係る照合システムの構成を示す図である。
【図２】図２は、実施例に係る照合装置の構成を示す機能ブロック図である。
【図３】図３は、イベントストリームのデータ構造の一例を示す図である。
【図４】図４は、ＮＦＡ生成部のＮＦＡ構築法を説明するための図（１）である。
【図５】図５は、ＮＦＡ生成部のＮＦＡ構築法を説明するための図（２）である。
【図６】図６は、ＮＦＡ生成部のＮＦＡ構築法を説明するための図（３）である。
【図７】図７は、ＮＦＡ生成部のＮＦＡ構築法を説明するための図（４）である。
【図８】図８は、照合部の照合を説明するための図（１）である。
【図９】図９は、照合部の照合を説明するための図（２）である。
【図１０】図１０は、ＮＦＡ生成部におけるＮＦＡ構築の主処理の手順を示すフローチャートである。
【図１１】図１１は、サブルーチン処理の手順を示すフローチャート（１）である。
【図１２】図１２は、サブルーチン処理の手順を示すフローチャート（２）である。
【図１３】図１３は、サブルーチン処理の手順を示すフローチャート（３）である。
【図１４Ａ】図１４Ａは、ＮＦＡを生成する処理を説明する図（１）である。
【図１４Ｂ】図１４Ｂは、ＮＦＡを生成する処理を説明する図（２）である。
【図１４Ｃ】図１４Ｃは、ＮＦＡを生成する処理を説明する図（３）である。
【図１５Ａ】図１５Ａは、ＮＦＡを生成する処理を説明する図（１）である。
【図１５Ｂ】図１５Ｂは、ＮＦＡを生成する処理を説明する図（２）である。
【図１５Ｃ】図１５Ｃは、ＮＦＡを生成する処理を説明する図（３）である。
【図１５Ｄ】図１５Ｄは、ＮＦＡを生成する処理を説明する図（４）である。
【図１５Ｅ】図１５Ｅは、ＮＦＡを生成する処理を説明する図（５）である。
【図１６】図１６は、照合部におけるパターン照合の主処理の手順を示すフローチャートである。
【図１７】図１７は、通常遷移を発動する処理の処理手順を示すフローチャートである。
【図１８】図１８は、全てのε遷移とε＝遷移を発動する処理の手順を示すフローチャートである。
【図１９Ａ】図１９Ａは、照合部の処理を説明する図（１）である。
【図１９Ｂ】図１９Ｂは、照合部の処理を説明する図（２）である。
【図１９Ｃ】図１９Ｃは、照合部の処理を説明する図（３）である。
【図１９Ｄ】図１９Ｄは、照合部の処理を説明する図（４）である。
【図１９Ｅ】図１９Ｅは、照合部の処理を説明する図（５）である。
【図１９Ｆ】図１９Ｆは、照合部の処理を説明する図（６）である。
【図１９Ｇ】図１９Ｇは、照合部の処理を説明する図（７）である。
【図１９Ｈ】図１９Ｈは、照合部の処理を説明する図（８）である。
【図１９Ｉ】図１９Ｉは、照合部の処理を説明する図（９）である。
【図１９Ｊ】図１９Ｊは、照合部の処理を説明する図（１０）である。
【図１９Ｋ】図１９Ｋは、照合部の処理を説明する図（１１）である。
【図２０】図２０は、照合プログラムを実行するコンピュータの一例を示す図である。
【図２１】図２１は、従来技術を説明するための図である。
【図２２】図２２は、イベントとイベントの説明とを対応づけた図である。
【図２３】図２３は、イベントパターンから生成される従来のオートマトンを示す図である。
【発明を実施するための形態】
【００１８】
以下に、本願の開示する照合装置および照合プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例】
【００１９】
［実施例に係る照合システムの構成］
実施例に係る照合システムの構成の一例について説明する。図１は、本実施例にかかる照合システムの構成を示す図である。図１に示すように、この照合システムは、イベントストリーム発生装置４０、ユーザ端末５０、照合装置１００を有する。照合装置１００は、ネットワーク３０を介して、イベントストリーム発生装置４０、ユーザ端末５０に接続される。
【００２０】
イベントストリーム発生装置４０は、複数のイベントの系列を含むイベントストリームを発生する装置である。イベントストリーム発生装置４０は、イベントストリームの情報を、照合装置１００に送信する。
【００２１】
ユーザ端末５０は、照合装置１００にイベントパターンを送信し、照合装置１００から照合結果を受信する装置である。
【００２２】
照合装置１００は、イベントパターンがイベントストリームに含まれるか否かを照合する装置である。照合装置１００は、照合結果をユーザ端末５０に送信する。
【００２３】
［実施例に係る照合装置の構成］
図１に示した照合装置１００の構成について説明する。図２は、実施例に係る照合装置の構成を示す機能ブロック図である。図２に示すように、この照合装置１００は、通信部１１０、入力部１２０、表示部１３０、記憶部１４０、制御部１５０を有する。
【００２４】
通信部１１０は、ネットワーク３０を介して、イベントストリーム発生装置４０、ユーザ端末５０とデータ通信を行う処理部である。後述する制御部１５０は、通信部１１０を介して、イベントストリームやイベントパターンの情報を受信する。通信部１１０は、所定の通信プロトコルを用いてデータ通信を行う通信装置、通信カード等に対応する。
【００２５】
入力部１２０は、ユーザが各種の情報を照合装置１００に入力するための入力装置である。例えば、入力部１２０は、キーボード、マウス、タッチパネルに対応する。表示部１３０は、各種の情報を表示する表示装置である。例えば、表示部１３０は、ディスプレイ、タッチパネルに対応する。
【００２６】
記憶部１４０は、イベントパターン１４０ａ、ＮＦＡ（Nondeterministic  Finite  Automaton）１４０ｂおよびイベントストリーム１４０ｃを記憶する。記憶部１４０は、例えば、ＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read  Only  Memory）、フラッシュメモリ（Flash  Memory）等の半導体メモリ素子、またはハードディスク、光ディスク等の記憶装置に対応する。
【００２７】
イベントパターン１４０ａは、イベントストリーム１４０ｃの照合に用いられるイベントパターンである。本実施例では、イベントパターンを間隔条件付きイベントの並列パターンとする。例えば、イベントパターン１４０ａを「Ｐ＝｛ｂ：（２：ａ）｝＆｛ｃ：（５：ａ）｝」の分岐パターンとする。または、イベントパターン１４０ａを「｛ｅ：（６：ｂ）｝＆｛ｅ：（４：ｃ）｝」の結合パターンとする。このイベントパターンのａ、ｂ、ｃ、ｄ、ｅは、それぞれイベントａ、ｂ、ｃ、ｄ、ｅに対応する。なお、｛ｂ：（２：ａ）｝とは、イベントａとの差が２以内でイベントｂを受理することを意味する。｛ｃ：（５：ａ）｝、｛ｅ：（６：ｂ）｝および｛ｅ：（４：ｃ）｝も同様の意味合いであるので、具体的な説明を省略する。
【００２８】
イベントパターンの「＆」は、順不同で該当するイベントを全て照合することを示す記号である。例えば、「Ａ＆Ｂ」は、順不同でイベントＡ、Ｂの双方を照合する並列パターンである。
【００２９】
ＮＦＡ１４０ｂは、イベントパターン１４０ａを基にして生成される非決定性有限オートマトンである。イベントストリーム１４０ｃは、複数のイベントの系列を含むデータである。図３は、イベントストリームのデータ構造の一例を示す図である。図３に示すように、イベントストリーム１４０ｃは、イベントの系列を示すイベントストリームと、各イベントが発生した時刻とを対応づけて記憶する。
【００３０】
制御部１５０は、データ取得部１５０ａ、ＮＦＡ生成部１５０ｂおよび照合部１５０ｃを有する。例えば、制御部１５０は、ＡＳＩＣ（Application  Specific  Integrated  Circuit）や、ＦＰＧＡ（Field  Programmable  Gate  Array）などの集積装置に対応する。また、制御部１５０は、例えば、ＣＰＵやＭＰＵ（Micro  Processing  Unit）等の電子回路に対応する。
【００３１】
データ取得部１５０ａは、イベントストリーム発生装置４０から、イベントストリームを取得し、ユーザ端末５０からイベントパターンを取得する処理部である。データ取得部１５０ａは、イベントパターンおよびイベントストリームを、イベントパターン１４０ａ、イベントストリーム１４０ｃとして記憶部１４０に格納する。
【００３２】
ＮＦＡ生成部１５０ｂは、イベントパターン１４０ａを基にして、ＮＦＡ１４０ｂを生成する処理部である。ＮＦＡ生成部１５０ｂは、生成したＮＦＡ１４０ｂを記憶部１４０に格納する。なお、ＮＦＡ生成部１５０ｂは、ＴｈｏｍｐｓｏｎＮＦＡ手法を利用して、ＮＦＡを生成するが、これに限定されるものではなく、如何なる従来技術を利用してＮＦＡを生成しても良い。
【００３３】
ここで、ＮＦＡ生成部１５０ｂのＮＦＡ構築法について説明する。図４〜図７は、ＮＦＡ生成部のＮＦＡ構築法を説明するための図である。
【００３４】
単一のイベントに対するＮＦＡは、図４に示すものとなる。図４は、単一イベントに対応するＮＦＡを示す。ＮＦＡ生成部１５０ｂは、ノード１ａとノード１ｂとを接続し、イベントａの受理によりノード１ａからノード１ｂに無条件に遷移するＮＦＡを生成する。このように、ノードからノードに無条件に遷移する通常遷移を「間隔条件なしの通常遷移」とする。
【００３５】
非連続直列パターンに対するＮＦＡは、図５に示すものとなる。図５は、非連続直列パターンに対応するＮＦＡを示す。なお、図５では、ｂはイベントを指し、ｘはイベント間の間隔条件を指すものとする。Ｐ１、Ｐ２は、それぞれイベントの集合を指すものとする。
【００３６】
ＮＦＡ生成部１５０ｂは、ノード２ａとノード２ｂとを接続し、ノード２ｂとノード２ｃとを接続し、ノード２ｃとノード２ｄとを接続する。また、ＮＦＡ生成部１５０ｂは、ノード２ｄとノード２ｅとを接続し、ノード２ｅとノード２ｆとを接続する。図５において、ノード２ｂからノード２ｃへの遷移およびノード２ｄからノード２ｅへの遷移を「ε遷移」とする。例えば、イベントＰ１によりノード２ａからノード２ｂに遷移した場合に、ノード２ｂからノード２ｃへの遷移が発動される。
【００３７】
図５において、ノード２ｃからノード２ｄへの遷移を、イベント間隔の条件を持つ遷移「ｂ：ｘ」とする。すなわち、ノード２ｃがイベントｂを受理すると、既にノード２ｃが受理したイベントとの間隔条件ｘを満たすとき、ノード２ｃからノード２ｄへの遷移が発動される。このように、間隔条件をチェックしたうえでノードからノードに遷移する通常遷移を「間隔条件ありの通常遷移」とする。
【００３８】
分岐パターンに対するＮＦＡは、図６に示すものとなる。図６は、分岐パターンに対応するＮＦＡを示す。なお、図６では、ａ、ｂ、ｃはそれぞれイベントを指し、ｘ、ｙはイベント間の間隔条件を指すものとする。Ｐ１、Ｐ２、Ｐ３は、それぞれイベントの集合を指すものとする。
【００３９】
ＮＦＡ生成部１５０ｂは、分岐パターンの分岐の起点となるイベントａの受理時刻を当該イベントａの遷移先を示すノード３ａに対応付けて保持させる。ここで、イベントの受理時刻を保持させるノードを「受理時刻保持ノード」（起点ノードに相当）というものとする。図６の例では、受理時刻保持ノードを「＠」で示している。そして、ＮＦＡ生成部１５０ｂは、分岐の起点となるイベントａに対応させて、受理時刻保持ノードに一意の識別子となる＠番号を割り当てる。
【００４０】
また、ＮＦＡ生成部１５０ｂは、ノード３ａから分岐先のノード３ｂおよびノード３ｃにε遷移で接続する。また、ＮＦＡ生成部１５０ｂは、ノード３ｂからノード３ｄに間隔条件ありの通常遷移「ｂ：ｘ」で接続する。この結果、ノード３ｂがイベントｂを受理すると、既にノード３ｂまで遷移したイベントとの間隔条件ｘを満たすとき、ノード３ｂからノード３ｄへの遷移が発動される。また、ＮＦＡ生成部１５０ｂは、ノード３ｃからノード３ｅに間隔条件ありの通常遷移「ｃ：ｙ」で接続する。この結果、ノード３ｃがイベントｃを受理すると、既にノード３ｃまで遷移したイベントとの間隔条件ｙを満たすとき、ノード３ｃからノード３ｅへの遷移が発動される。
【００４１】
また、ＮＦＡ生成部１５０ｂは、ノード３ｄからノード３ｆにε遷移で接続し、ノード３ｅからノード３ｇにε遷移で接続する。また、ＮＦＡ生成部１５０ｂは、ノード３ｈおよびノード３ｉからノード３ｊへそれぞれε＝遷移で接続する。ここで、複数のノードからε＝遷移で接続されたノード、言い換えると複数のノードを結合する結合点を示すノードを「合流ノード」（結合点ノードに相当）というものとする。図６の例では、合流ノード３ｊを「＝＠」で示している。すなわち、ＮＦＡ生成部１５０ｂは、合流ノード３ｊにて複数のノード３ｈ、３ｉから遷移されるイベントａの受理時刻が同じものがあるか否かを判定させるようにする。
【００４２】
結合パターンに対するＮＦＡは、図７に示すものとなる。図７は、結合パターンに対応するＮＦＡを示す。なお、図７では、ｃはイベントを指し、ｘ、ｙはイベント間の間隔条件を指すものとする。Ｐ１、Ｐ２、Ｐ３は、それぞれイベントの集合を指すものとする。
【００４３】
ＮＦＡ生成部１５０ｂは、結合パターンの結合の終点となるイベントｃの受理時刻を当該イベントｃの遷移先を示すノード４ｅ、４ｆに対応付けて保持させる。ここで、ノード４ｅ、４ｆは、それぞれイベントｃの受理時刻を保持させるノードであるので、それぞれ受理時刻保持ノードとなる。図７の例では、受理時刻保持ノード４ｅ、４ｆを「＠」で示している。そして、ＮＦＡ生成部１５０ｂは、結合の終点となるイベントｃに対応させて、受理時刻保持ノード４ｅ、４ｆに一意の識別子となる同一の＠番号を割り当てる。
【００４４】
また、ＮＦＡ生成部１５０ｂは、ノード４ｅおよびノード４ｆからノード４ｇへそれぞれε＝遷移で接続する。ここで、ノード４ｇは、複数のノード４ｅ、４ｆからε＝遷移で接続されたノードであるので、合流ノードとなる。図７の例では、合流ノード４ｇを「＝＠」で示している。すなわち、ＮＦＡ生成部１５０ｂは、合流ノード４ｇにて複数のノード４ｅ、４ｆから遷移されるイベントｃの受理時刻が同じものがあるか否かを判定させるようにする。
【００４５】
図２に戻って、照合部１５０ｃは、ＮＦＡ１４０ｂを利用して、イベントストリーム１４０ａを照合する処理部である。例えば、照合部１５０ｃは、ＮＦＡ１４０ｂを用いて、分岐の起点となるイベントの受理時刻を間隔条件に合った受理状態と共に遷移させ、結合点となる合流ノードで受理時刻が同じものがあれば更に遷移させる。そして、照合部１５０ｃは、照合結果をユーザ端末５０に通知する。
【００４６】
一例として、照合部１５０ｃは、イベントストリーム１４０ｃの各イベントを順に辿り、ＮＦＡ１４０ｂの各ノードと比較し、ＮＦＡ１４０ｂに含まれる分岐パターンについて、以下のように照合する。照合部１５０ｃは、分岐パターンの分岐の起点となるイベントが受理時刻保持ノードで受理されると、受理されたイベントの受理時刻を受理時刻保持ノードに対応付けて保持する。
【００４７】
そして、照合部１５０ｃは、イベントストリーム１４０ｃ上の分岐の起点となるイベントに後続するイベントが分岐先のノードで受理されると、受理されたイベントの受理が分岐先のノードに対応付けられた間隔条件を満たすか否かを判定する。そして、照合部１５０ｃは、受理されたイベントの受理が分岐先のノードに対応付けられた間隔条件を満たすと判定した場合、受理時刻保持ノードに対応付けて保持された受理時刻を分岐先のノードの受理状態と共に遷移させる。ここで、受理状態とは、分岐先のノードが現段階で最終的に受理したイベントの状態を意味し、例えば、受理したイベントの受理時刻を示す。なお、受理時刻保持ノードが受理したイベントが複数ある場合には、そのイベントを受理した受理時刻毎に複数存在することもある。
【００４８】
さらに、照合部１５０ｃは、合流ノードにて複数の分岐先のノードから遷移された受理時刻に同一の受理時刻があるか否かを判定する。そして、照合部１５０ｃは、同一の受理時刻があると判定した場合、同一の受理時刻を含む結合状態を生成し、生成した結合状態を更に遷移させる。ここで、結合状態とは、例えば同一の受理時刻に対応する複数の受理状態を結合した状態を意味する。
【００４９】
照合部１５０ｃは、最終状態であるノードへの遷移を発動した時点で、照合完了とし、照合結果として例えば終了時刻を出力する。
【００５０】
また、照合部１５０ｃは、イベントストリーム１４０ｃの各イベントを順に辿り、ＮＦＡ１４０ｂの各ノードと比較し、ＮＦＡ１４０ｂに含まれる結合パターンについて、以下のように照合する。照合部１５０ｃは、結合パターンの結合の終点となるイベントが受理時刻保持ノードで受理されると、遷移元の受理状態を複製する。また、照合部１５０ｃは、受理されたイベントの受理時刻を受理時刻保持ノードに対応付けて保持する。そして、照合部１５０ｃは、該保持した受理時刻を該複製した受理状態と共に合流ノードに遷移させる。
【００５１】
さらに、照合部１５０ｃは、合流ノードにて複数の分岐先のノードから遷移された受理時刻に終点となるイベントの同一の受理時刻があるか否かを判定する。そして、照合部１５０ｃは、同一の受理時刻があると判定した場合、同一の受理時刻を含む結合状態を生成し、生成した結合状態を更に遷移させる。
【００５２】
ここで、照合部１５０ｃの照合について説明する。図８および図９は、照合部の照合を説明するための図である。
【００５３】
図８において、イベントパターン１４０ａに含まれる分岐パターン２００ｐは、イベントａを分岐の起点とし、イベントａからイベントｂまでの間隔が２以内であって、イベントａからイベントｃまでの間隔が２以内である分岐パターンとする。分岐パターン２００ｐに対するＮＦＡ１４０ｂは、図８に示す２００ｎに示すものとなる。なお、図８の示す２００ｎ内の＠０は、＠番号を０とする受理時刻保持ノードであることを示す。また、＝＠０は、＠番号を０とする受理時刻保持ノードで受理されたイベントの受理時刻を照合する合流ノードであることを示す。
【００５４】
照合部１５０ｃは、イベントストリーム１４０ｃ上の分岐パターンの分岐の起点となるイベントａを間隔条件なしの通常遷移を経て受理時刻保持ノード５ａで受理すると、受理したイベントａの受理時刻を受理時刻保持ノード５ａに対応付けて保持する。そして、照合部１５０ｃは、受理時刻保持ノード５ａでイベントａを受理したので、受理時刻保持ノード５ａからノード５ｂに接続されたε遷移を発動する。このとき、照合部１５０ｃは、受理時刻保持ノード５ａに対応付けて保持したイベントａの受理時刻と共に、受理時刻保持ノード５ａの受理状態をノード５ｂに遷移させる。
【００５５】
そして、照合部１５０ｃは、イベントストリーム１４０ｃ上の分岐の起点となるイベントａに後続するイベントｂを分岐先のノード５ｂで受理すると、受理したイベントｂに関する間隔条件ありの通常遷移を発動する。そして、照合部１５０ｃは、イベントｂの受理が分岐先のノード５ｂに対応付けられた間隔条件２を満たすか否かを判定する。ここでは、照合部１５０ｃは、イベントａの受理時刻からイベントｂまでの間隔条件が２以下であるか否かを判定する。そして、照合部１５０ｃは、間隔条件２を満たせば、受理ノード５ｂに遷移したイベントａの受理時刻をノード５ｂの受理状態と共にノード５ｄに遷移させる。そして、照合部１５０ｃは、ノード５ｄでイベントｂを受理したので、ノード５ｄからノード５ｆに接続されたε＝遷移を発動する。
【００５６】
すると、照合部１５０ｃは、合流ノード５ｆにて複数の分岐先のノード５ｄ、５ｅから遷移された受理時刻に＠０に対応する同一の受理時刻があるか否かを判定する。そして、照合部１５０ｃは、＠０に対応する同一の受理時刻があると判定した場合、ノード５ｄ、５ｅのそれぞれの受理状態から同一の受理時刻に対する受理状態を結合した結合状態を生成し、生成した結合状態を更に遷移させる。
【００５７】
図９において、イベントパターン１４０ａに含まれる結合パターン２０１ｐは、イベントｅを結合の終点とし、結合元のイベントｂからイベントｅまでの間隔が６以内であって、結合元のイベントｃからイベントｅまでの間隔が４以内である結合パターンとする。結合パターン２０１ｐに対するＮＦＡ１４０ｂは、図９に示す２０１ｎに示すものとなる。なお、図９の示す２０１ｎ内の＠０は、＠番号を０とする受理時刻保持ノードであることを示す。また、＝＠０は、＠番号を０とする受理時刻保持ノードで受理されたイベントの受理時刻を照合する合流ノードであることを示す。
【００５８】
照合部１５０ｃは、イベントストリーム１４０ｃ上のイベントｂをノード６ａで受理すると、受理したイベントｂに関する間隔条件なしの通常遷移を発動し、ノード６ａの受理状態をノード６ｃに遷移させる。さらに、照合部１５０ｃは、ノード６ｃからノード６ｅに接続されたε遷移を発動し、ノード６ｃの受理状態をノード６ｅに遷移させる。
【００５９】
そして、照合部１５０ｃは、結合パターンの結合の終点となるイベントｅをノード６ｅで受理すると、受理したイベントｅに関する間隔条件ありの通常遷移を発動する。そして、照合部１５０ｃは、イベントｅの受理がノード６ｅに対応付けられた間隔条件６を満たすか否かを判定する。ここでは、照合部１５０ｃは、イベントｂの受理時刻からイベントｅまでの間隔条件が６以下であるか否かを判定する。そして、照合部１５０ｃは、間隔条件６を満たせば、ノード６ｅの受理状態をノード６ｇに遷移させる。そして、照合部１５０ｃは、受理時刻保持ノードであるノード６ｇでイベントｅを受理すると、遷移元のノード６ｅの受理状態を複製する。そして、照合部１５０ｃは、受理したイベントｅの受理時刻を受理時刻保持ノード６ｇに対応付けて保持する。そして、照合部１５０ｃは、ノード６ｇからノード６ｉに接続されたε＝遷移を発動する。このとき、照合部１５０ｃは、保持した受理時刻を複製した受理状態と共に合流ノード６ｉに遷移させる。
【００６０】
すると、照合部１５０ｃは、合流ノード６ｉにて複数のノード６ｇ、６ｈから遷移された受理時刻に＠０に対応する同一の受理時刻があるか否かを判定する。そして、照合部１５０ｃは、＠０に対応する同一の受理時刻があると判定した場合、同一の受理時刻を含む結合状態を生成し、生成した結合状態を更に遷移させる。
【００６１】
［実施例に係るＮＦＡ生成部におけるＮＦＡ構築の処理手順］
次に、実施例に係るＮＦＡ生成部１５０ｂにおけるＮＦＡ構築の処理手順を、図１０〜図１３を参照して説明する。図１０はＮＦＡ生成部におけるＮＦＡ構築の主処理の手順を示し、図１１〜図１３はＮＦＡ生成部におけるＮＦＡ構築のサブルーチン処理の手順を示す。
【００６２】
［ＮＦＡ構築の主処理の手順］
まず、ＮＦＡ構築の主処理の手順について、図１０を参照して説明する。図１０は、実施例に係るＮＦＡ生成部におけるＮＦＡ構築の主処理の手順を示すフローチャートである。図１０に示す処理は、例えば、イベントのパターンＰを入力とし、ＮＦＡを指すＮ（Ｐ）を出力とする。そして、ノード番号を変数ｉとし、＠番号を変数ｊとする。ここで、ノード番号とは、各ノードに割り振られるユニークな番号であり、状態番号と同じ意味を示す。状態の種類には、ノードに応じて、例えば、初期状態、最終状態がある。＠番号とは、受理時刻保持ノード（＠ノード）に対応する番号を示す。
【００６３】
まず、ＮＦＡ生成部１５０ｂは、ノード番号を０とする初期状態のノードを生成し、生成したノードに空の「＠リスト」を登録する。そして、ＮＦＡ生成部１５０ｂは、現ノード番号ｉの値を０に設定し、現＠番号ｊの値を０に設定する（ステップＳ１１）。なお、「＠リスト」とは、＠番号とタイムアウトの期間とを対応付けたリストである。
【００６４】
そして、ＮＦＡ生成部１５０ｂは、入力されたパターンＰに示されたイベント（以降、「イベント受理制約」と同義）の内、イベントの前に間隔制約がないものを集め、仮のイベント集合（仮イベント集合）とする（ステップＳ１２）。なお、間隔制約とは、間隔条件と同じ意味であるものとする。
【００６５】
そして、ＮＦＡ生成部１５０ｂは、初期状態のノードを起点ノードとして、仮イベント集合に集めたイベント受理制約について、サブルーチン処理を行なう（ステップＳ１３）。
【００６６】
その後、サブルーチン処理が終了すると、ＮＦＡ生成部１５０ｂは、最終状態のノードを生成し、生成したノードに、現ノード番号ｉに１を加算した値を割り当てる。そして、ＮＦＡ生成部１５０ｂは、「終端ノードリスト」に含まれるそれぞれのノードから、生成した最終状態のノードへε＝遷移で接続する（ステップＳ１４）。なお、「終端ノードリスト」は、終端となるノードを集めたリストであり、サブルーチン処理で作成される。
【００６７】
そして、ＮＦＡ生成部１５０ｂは、終端ノードリストに含まれる異なるノードについて、各ノードの＠リストを取り出す。そして、ＮＦＡ生成部１５０ｂは、取り出した＠リストに存在する共通の＠番号を指定＠番号として、タイムアウトの中で一番大きいものをタイムアウト長として最終状態のノードに登録する（ステップＳ１５）。
【００６８】
［サブルーチン処理の手順］
次に、図１０のステップＳ１３に示したサブルーチン処理について、図１１〜図１３を参照して説明する。図１１〜図１３は、サブルーチン処理の手順を示すフローチャートである。
【００６９】
ＮＦＡ生成部１５０ｂは、起点ノードが初期状態のノードでない、且つ仮イベント集合に集めたイベント受理制約が２つ以上であるか否かを判定する（ステップＳ１３１）。起点ノードが初期状態のノードである場合、又は、起点ノードが初期状態のノードでない、且つ仮イベント集合に集めたイベント受理制約が２つ以上でない場合（ステップＳ１３１；Ｎｏ）、ＮＦＡ生成部１５０ｂは、ステップＳ１３２に移行する。
【００７０】
ステップＳ１３２では、ＮＦＡ生成部１５０ｂが、集めた各イベント受理制約に対応するイベントを入力するノード（以降、「イベント入力ノード」という。）を生成する。そして、ＮＦＡ生成部１５０ｂは、現ノード番号ｉに１を加算しながら、現ノード番号ｉを生成したノードに割り当てる。そして、ＮＦＡ生成部１５０ｂは、起点ノードから、生成したイベント入力ノードへε遷移で接続する。すなわち、ＮＦＡ生成部１５０ｂは、起点ノードからイベント入力ノードへの遷移をε遷移とする。さらに、ＮＦＡ生成部１５０ｂは、起点ノードの＠リストを、生成したノードの＠リストにコピーする（ステップＳ１３２）。
【００７１】
一方、起点ノードが初期状態のノードでない、且つ仮イベント集合に集めたイベント受理制約が２つ以上である場合（ステップＳ１３１；Ｙｅｓ）、ＮＦＡ生成部１５０ｂは、ステップＳ１３３に移行する。すなわち、仮イベント集合に集めたイベント受理制約が分岐パターンとなるイベント受理制約である場合である。
【００７２】
ステップＳ１３３では、ＮＦＡ生成部１５０ｂが、起点ノードに現＠番号ｊを割り当て、＠番号ｊに１を加算する（ステップＳ１３３）。すなわち、この起点ノードは、分岐の起点となるイベントの受理時刻を保持する「受理時刻保持ノード」となる。そして、ＮＦＡ生成部１５０ｂは、起点ノードの＠リストに、割り当てた＠番号およびタイムアウト０を設定し（ステップＳ１３４）、ステップＳ１３２に移行する。
【００７３】
ステップＳ１３２の処理後、ＮＦＡ生成部１５０ｂは、仮イベント集合に集めたイベント受理制約の中で未処理のものがあるか否かを判定する（ステップＳ１３５）。集めたイベント受理制約の中で未処理のものがない場合（ステップＳ１３５；Ｎｏ）、ＮＦＡ生成部１５０ｂは、サブルーチン処理を終了する。
【００７４】
一方、集めたイベント受理制約の中で未処理のものがある場合（ステップＳ１３５；Ｙｅｓ）、ＮＦＡ生成部１５０ｂは、集めたイベント受理制約から未処理のイベント受理制約を１つ取り出す（ステップＳ１３６）。
【００７５】
そして、ＮＦＡ生成部１５０ｂは、現在のイベント受理制約に前方間隔制約があるか否かを判定する（ステップＳ１３７）。現在のイベント受理制約に前方の間隔制約がない場合（ステップＳ１３７；Ｎｏ）、ＮＦＡ生成部１５０ｂは、現ノード番号ｉに１を加算し、イベント受理完了ノードを生成し、生成したノードに、加算した現ノード番号を割り当てる。そして、ＮＦＡ生成部１５０ｂは、指定したイベントの受理によりイベント入力ノードからイベント受理完了ノードに遷移するエッジで接続する。すなわち、ＮＦＡ生成部１５０ｂは、イベント入力ノードからイベント受理完了ノードへの遷移を「間隔条件なしの通常遷移」とする。さらに、ＮＦＡ生成部１５０ｂは、イベント入力ノードの＠リストをイベント受理完了ノードの＠リストにコピーする（ステップＳ１３８）。その後、ＮＦＡ生成部１５０ｂは、ステップＳ１４１に移行する。
【００７６】
一方、現在のイベント受理制約に前方間隔制約がある場合（ステップＳ１３７；Ｙｅｓ）、ＮＦＡ生成部１５０ｂは、現ノード番号ｉに１を加算し、イベント受理完了ノードを生成し、生成したノードに、加算した現ノード番号を割り当てる。そして、ＮＦＡ生成部１５０ｂは、前方間隔制約を満たすイベントの受理で、イベント入力ノードからイベント受理完了ノードに遷移するエッジで接続する。すなわち、ＮＦＡ生成部１５０ｂは、イベント入力ノードからイベント受理完了ノードへの遷移を「間隔条件付きの通常遷移」とする。さらに、ＮＦＡ生成部１５０ｂは、イベント入力ノードの＠リストの各タイムアウトに前方間隔制約を加えてから、生成したイベント受理完了ノードの＠リストにコピーする（ステップＳ１３９）。その後、ＮＦＡ生成部１５０ｂは、ステップＳ１４１に移行する。
【００７７】
続いて、ＮＦＡ生成部１５０ｂは、現在のイベント受理制約の前方間隔制約の数をＦに設定する（ステップＳ１４１）。そして、ＮＦＡ生成部１５０ｂは、Ｆの値が２以上であるか否かを判定する（ステップＳ１４２）。Ｆの値が２以上でない場合（ステップＳ１４２；Ｎｏ）、ＮＦＡ生成部１５０ｂは、生成したイベント受理完了ノードを完了ノードとする（ステップＳ１４３）。その後、ＮＦＡ生成部１５０ｂは、現在のイベント受理制約の後方間隔制約における処理を行うべく、ステップＳ１５１に移行する。
【００７８】
一方、Ｆの値が２以上である場合（ステップＳ１４２；Ｙｅｓ）、ＮＦＡ生成部１５０ｂは、現在のイベント受理制約に対応する生成済みのイベント受理完了ノードの数がＦの値と一致するか否かを判定する（ステップＳ１４４）。現在のイベント受理制約に対応する生成済みのイベント受理完了ノードの数がＦの値と一致しない場合（ステップＳ１４４；Ｎｏ）、ＮＦＡ生成部１５０ｂは、集めたイベント受理制約の中で未処理のイベント受理制約の処理をすべく、ステップＳ１３５に移行する。
【００７９】
一方、現在のイベント受理制約に対応する生成済みのイベント受理完了の数がＦの値と一致する場合（ステップＳ１４４；Ｙｅｓ）、ＮＦＡ生成部１５０ｂは、現ノード番号ｉに１を加算し、現在のイベント受理制約に対応する合流ノードを生成する。そして、ＮＦＡ生成部１５０ｂは、現在のイベント受理制約に対応する生成済みの全てのイベント受理完了ノードから、生成した合流ノードへε＝遷移で接続する（ステップＳ１４５）。すなわち、ＮＦＡ生成部１５０ｂは、イベント受理完了ノードから合流ノードへの遷移を「ε＝遷移」とする。
【００８０】
続いて、ＮＦＡ生成部１５０ｂは、現在の＠番号ｊおよびタイムアウト０を現在のイベント受理制約に対応する生成済みの全てのイベント受理完了ノードに割り当て、それぞれの＠リストに追加する。すなわち、これら生成済みの全てのイベント受理完了ノードは、イベントの受理時刻を保持する「受理時刻保持ノード」となる。さらに、ＮＦＡ生成部１５０ｂは、＠番号ｊに１を加算する（ステップＳ１４６）。
【００８１】
続いて、ＮＦＡ生成部１５０ｂは、現在のイベント受理制約に対応する生成済みのイベント受理完了ノードの＠リストにおいて、複数の生成済みのイベント受理完了ノードが持っている同一の＠番号を合流ノードの指定＠番号とする。そして、ＮＦＡ生成部１５０ｂは、タイムアウトの中で一番大きい値をタイムアウト長として、＠番号とともに合流ノードに対応付けて登録する（ステップＳ１４７）。
【００８２】
続いて、ＮＦＡ生成部１５０ｂは、現在のイベント受理制約に対応する生成済みのイベント受理完了ノードの＠リストに含まれる＠番号および各＠番号で最大のタイムアウトを重複なく合流ノードの＠リストに設定する（ステップＳ１４８）。そして、ＮＦＡ生成部１５０ｂは、合流ノードを完了ノードとし（ステップＳ１４９）、現在のイベント受理制約の後方間隔制約における処理を行うべく、ステップＳ１５１に移行する。
【００８３】
ステップＳ１５１では、ＮＦＡ生成部１５０ｂが、ステップＳ１３６で取り出したイベント受理制約の後方への間隔制約を持つイベント受理制約を集め、仮イベント集合とする（ステップＳ１５１）。そして、ＮＦＡ生成部１５０ｂは、仮イベント集合に集めたイベント受理制約が１つ以上であるか否かを判定する（ステップＳ１５２）。集めたイベント受理制約が１つ以上でない場合、すなわち０である場合（ステップＳ１５２；Ｎｏ）、ＮＦＡ生成部１５０ｂは、終端ノードリストに完了ノードを追加する（ステップＳ１５３）。その後、ＮＦＡ生成部１５０ｂは、集めたイベント受理制約の中で未処理のイベント受理制約の処理をすべく、ステップＳ１３５に移行する。
【００８４】
一方、集めたイベント受理制約が１つ以上である場合（ステップＳ１５２；Ｙｅｓ）、ＮＦＡ生成部１５０ｂは、完了ノードを起点ノードとして、仮イベント集合に集めたイベント受理制約について、サブルーチン処理を再帰的に行う（ステップＳ１５４）。その後、ＮＦＡ生成部１５０ｂは、集めたイベント受理制約の中で未処理のイベント受理制約の処理をすべく、ステップＳ１３５に移行する。
【００８５】
［ＮＦＡを生成する処理の一例］
次に、分岐パターンをイベントパターン１４０ａとした場合に、図１０〜図１３に示したＮＦＡの構築法を用いて、ＮＦＡ生成部１５０ｂが、イベントパターン１４０ａからＮＦＡ１４０ｂを生成する処理の一例について説明する。図１４Ａ〜図１４Ｃは、ＮＦＡを生成する処理を説明する図である。
【００８６】
図１４Ａに示すように、イベントパターン１４０ａのデータ構造を、符号２０２ｐに示すものとする。イベントパターン１４０ａは、イベントＡを分岐の起点とし、イベントＡからイベントＢまでの間隔を２以内とし、イベントＡからイベントＣまでの間隔を５以内とする分岐パターンであるものとする。
【００８７】
図１４Ｂの１段目に示すように、ＮＦＡ生成部１５０ｂは、ノード番号を０とする初期状態のノード７ａを生成し、生成したノード７ａに空の＠リストを登録する。そして、ＮＦＡ生成部１５０ｂは、現ノード番号ｉの値を０に設定し、現＠番号ｊの値を０に設定する。そして、ＮＦＡ生成部１５０ｂは、入力されたイベントパターン１４０ａに示されたイベント受理制約の内、前に間隔制約がないものを集め、仮イベント集合とする。ここでは、ＮＦＡ生成部１５０ｂは、イベントＡのイベント受理制約を仮イベント集合とする。そして、ＮＦＡ生成部１５０ｂは、初期状態のノード７ａを起点ノードとする。
【００８８】
図１４Ｂの２段目に示すように、ＮＦＡ生成部１５０ｂは、起点ノードが初期状態のノード７ａであるので、仮イベント集合に集められたイベント受理制約（Ａ）に対応するイベント入力ノード７ｂを生成する。そして、ＮＦＡ生成部１５０ｂは、生成したノード７ｂに現ノード番号ｉに１を加算した値１を割り当てる。そして、ＮＦＡ生成部１５０ｂは、起点ノード７ａからイベント入力ノード７ｂへε遷移で接続する。
【００８９】
図１４Ｂの３段目に示すように、ＮＦＡ生成部１５０ｂは、仮イベント集合に集められたイベント受理制約（Ａ）から未処理のイベント受理制約を１つ取り出す。ここでは、ＮＦＡ生成部１５０ｂはイベントＡを取り出す。そして、ＮＦＡ生成部１５０ｂは、イベント受理完了ノード７ｃを生成し、生成したノード７ｃに、現ノード番号ｉに１を加算した値２を割り当てる。そして、ＮＦＡ生成部１５０ｂは、イベントＡの受理によりイベント入力ノード７ｂからイベント受理完了ノード７ｃに遷移するエッジで接続する。すなわち、イベント入力ノード７ｂからイベント受理完了ノード７ｃへの遷移が「間隔条件なしの通常遷移」となる。さらに、ＮＦＡ生成部１５０ｂは、イベント入力ノード７ｂの＠リストをイベント受理完了ノード７ｃの＠リストにコピーする。
【００９０】
続いて、ＮＦＡ生成部１５０ｂは、現在のイベント受理制約（Ａ）の前方の間隔制約の数をＦとする。ここでは、ＮＦＡ生成部１５０ｂは、イベントＡの前方の間隔に制約がないので、Ｆを０に設定する。そして、ＮＦＡ生成部１５０ｂは、Ｆが２以上でないので、イベント受理完了ノード７ｃを完了ノードとする。さらに、ＮＦＡ生成部１５０ｂは、取り出したイベント受理制約（Ａ）の後方への間隔制約を持つイベント受理制約を集め、仮イベント集合とする。ここでは、ＮＦＡ生成部１５０ｂは、イベントＡの後方イベントＢまでの間隔制約が２、イベントＡの後方イベントＣまでの間隔制約が５であるので、イベント受理制約Ｂ、Ｃを仮イベント集合とする。そして、ＮＦＡ生成部１５０ｂは、完了ノード７ｃを起点ノードとする。
【００９１】
図１４Ｂの４段目に示すように、ＮＦＡ生成部１５０ｂは、起点ノード７ｃが初期状態のノードでなく、且つ仮イベント集合に集められたイベント受理制約（Ｂ、Ｃ）が２つ以上であるので、起点ノード７ｃに現＠番号ｊの値０を割り当てる。すなわち、この起点ノード７ｃは、＠番号０（＠０）を有する受理時刻保持ノードとなる。そして、ＮＦＡ生成部１５０ｂは、現＠番号ｊの値を、１加算した値１に設定する。
【００９２】
図１４Ｂの５段目に示すように、ＮＦＡ生成部１５０ｂは、起点ノード７ｃの＠リスト１ｍに、割り当てた＠番号０およびタイムアウト０を設定する。
【００９３】
図１４Ｃの１段目に示すように、ＮＦＡ生成部１５０ｂは、仮イベント集合に集められたイベント受理制約（Ｂ、Ｃ）に対応するイベント入力ノード７ｄ、７ｅを生成する。そして、ＮＦＡ生成部１５０ｂは、生成したノード７ｄに現ノード番号ｉ（２）に１を加算した値３を割り当て、生成したノード７ｅにさらに現ノード番号ｉ（３）に１を加算した値４を割り当てる。そして、ＮＦＡ生成部１５０ｂは、起点ノード７ｃからイベント入力ノード７ｄへε遷移で接続し、起点ノード７ｃからイベント入力ノード７ｅへε遷移で接続する。そして、ＮＦＡ生成部１５０ｂは、起点ノード７ｃの＠リストをイベント入力ノード７ｄ、７ｅのそれぞれの＠リストにコピーする。
【００９４】
図１４Ｃの２段目に示すように、ＮＦＡ生成部１５０ｂは、仮イベント集合に集められたイベント受理制約（Ｂ、Ｃ）から未処理のイベント受理制約を１つ取り出す。ここでは、ＮＦＡ生成部１５０ｂはイベントＢを取り出す。そして、ＮＦＡ生成部１５０ｂは、イベント受理完了ノード７ｆを生成し、生成したノード７ｆに、現ノード番号ｉに１を加算した値５を割り当てる。そして、ＮＦＡ生成部１５０ｂは、前方間隔制約２を満たすイベントＢの受理によりイベント入力ノード７ｄからイベント受理完了ノード７ｆに遷移するエッジで接続する。すなわち、イベント入力ノード７ｄからイベント受理完了ノード７ｆへの遷移が「間隔条件ありの通常遷移」となる。さらに、ＮＦＡ生成部１５０ｂは、イベント入力ノード７ｄの＠リストのタイムアウトに前方間隔制約２を加えてからイベント受理完了ノード７ｆの＠リストにコピーする。
【００９５】
続いて、ＮＦＡ生成部１５０ｂは、現在のイベント受理制約（Ｂ）の前方の間隔制約の数をＦとする。ここでは、イベントＢの前方間隔制約は２のものだけであるので、ＮＦＡ生成部１５０ｂは、前方の間隔制約の数Ｆを１に設定する。そして、ＮＦＡ生成部１５０ｂは、Ｆが２以上でないので、イベント受理完了ノード７ｆを完了ノードとする。さらに、ＮＦＡ生成部１５０ｂは、取り出したイベント受理制約（Ｂ）の後方への間隔制約を持つイベント受理制約を集め、仮イベント集合とする。ここでは、ＮＦＡ生成部１５０ｂは、イベントＢの後方への間隔制約を持つイベント受理制約がないので、空の仮イベント集合とする。そして、ＮＦＡ生成部１５０ｂは、仮イベント集合が空なので、終端ノードリストに完了ノード７ｆを追加する。ここで、イベント受理制約Ｂの処理が終了する。
【００９６】
図１４Ｃの３段目に示すように、ＮＦＡ生成部１５０ｂは、仮イベント集合に集められたイベント受理制約（Ｂ、Ｃ）から未処理のイベント受理制約を１つ取り出す。ここでは、ＮＦＡ生成部１５０ｂは、イベントＢの処理が終了しているので、未処理のイベントＣを取り出す。そして、ＮＦＡ生成部１５０ｂは、イベント受理完了ノード７ｇを生成し、生成したノード７ｇに、現ノード番号ｉに１を加算した値６を割り当てる。そして、ＮＦＡ生成部１５０ｂは、前方間隔制約５を満たすイベントＣの受理によりイベント入力ノード７ｅからイベント受理完了ノード７ｇに遷移するエッジで接続する。すなわち、イベント入力ノード７ｅからイベント受理完了ノード７ｇへの遷移が「間隔条件ありの通常遷移」となる。さらに、ＮＦＡ生成部１５０ｂは、イベント入力ノード７ｅの＠リストのタイムアウトに前方間隔制約５を加えてからイベント受理完了ノード７ｇの＠リストにコピーする。
【００９７】
続いて、ＮＦＡ生成部１５０ｂは、現在のイベント受理制約（Ｃ）もイベントＢと同様に、前方の間隔制約の数が１つで、後方の間隔制約がないので、終端ノードリストに完了ノード７ｇを追加する。すなわち、終端ノードリストには、完了ノード７ｆ、７ｇがある。ここで、イベント受理制約Ｃの処理が終了する。この結果、イベント受理制約Ａの処理が終了する。
【００９８】
続いて、ＮＦＡ生成部１５０ｂは、仮イベント集合に集められたイベント受理制約（Ｂ、Ｃ）の処理が終了したので、元の仮イベント集合および元の起点ノードに戻す。すなわち、起点ノードは初期状態のノード７ａとなり、仮イベント集合はイベント受理制約Ａを含んだものになる。
【００９９】
図１４Ｃの４段目に示すように、ＮＦＡ生成部１５０ｂは、戻した仮イベント集合に含まれるイベント受理制約Ａの処理を終了しているので、最終状態のノード７ｈを生成し、生成したノード７ｈに、現ノード番号ｉに１を加算した値７を割り当てる。そして、ＮＦＡ生成部１５０ｂは、終端ノードリストに含まれるそれぞれの完了ノード７ｆ、７ｇから、生成した最終状態のノード７ｈへε＝遷移で接続する。
【０１００】
図１４Ｃの５段目に示すように、ＮＦＡ生成部１５０ｂは、終端ノードリストに含まれる異なるノードについて、各ノードの＠リストを取り出す。ここでは、ＮＦＡ生成部１５０ｂは、終端ノードリストに含まれる完了ノード７ｆ、７ｇの＠リストを取り出す。そして、ＮＦＡ生成部１５０ｂは、取り出した＠リストに存在する共通の＠番号を指定＠番号として、タイムアウトの中で一番大きいものをタイムアウト長として最終状態のノード７ｈに登録する。ここでは、完了ノード７ｆの＠リストには、＠番号０とタイムアウト長２とが対応付けられ、完了ノード７ｇの＠リストには、＠番号０とタイムアウト長５とが対応付けられている。このため、ＮＦＡ生成部１５０ｂは、指定＠番号を０として、タイムアウト長を５として最終状態のノード７ｈに登録する。
【０１０１】
上述したように、ＮＦＡ生成部１５０ｂは、図１４Ａ〜図１４Ｃに示す処理を実行することで、図１４Ａに示すイベントパターン１４０ａからＮＦＡ１４０ｂを生成する。
【０１０２】
［ＮＦＡを生成する処理の別の例］
次に、分岐パターンと結合パターンを含むパターンをイベントパターン１４０ａとした場合に、図１０〜図１３に示したＮＦＡの構築法を用いて、ＮＦＡ生成部１５０ｂが、イベントパターン１４０ａからＮＦＡ１４０ｂを生成する処理の別の例について説明する。図１５Ａ〜図１５Ｅは、ＮＦＡを生成する処理を説明する図である。
【０１０３】
図１５Ａに示すように、イベントパターン１４０ａのデータ構造を、符号２０３ｐに示すものとする。イベントパターン１４０ａは、イベントＡからイベントＢまでの間隔を２以内とする非連続直列パターンを有する。そして、イベントパターン１４０ａは、イベントＢを分岐の起点とし、イベントＢからイベントＤまでの間隔を６以内とし、イベントＢからイベントＥまでの間隔を５以内とする分岐パターンを有する。さらに、イベントパターン１４０ａは、イベントＢからイベントＥまでの間隔を５以内とし、イベントＣからイベントＥまでの間隔を４以内とし、イベントＥを結合の終点とする結合パターンを有する。
【０１０４】
図１５Ｂの１段目に示すように、ＮＦＡ生成部１５０ｂは、ノード番号を０とする初期状態のノード８ａを生成し、生成したノード８ａに空の＠リストを登録する。そして、ＮＦＡ生成部１５０ｂは、現ノード番号ｉの値を０に設定し、現＠番号ｊの値を０に設定する。そして、ＮＦＡ生成部１５０ｂは、入力されたイベントパターン１４０ａに示されたイベント受理制約の内、前に間隔制約がないものを集め、仮イベント集合とする。ここでは、ＮＦＡ生成部１５０ｂは、前に間隔制約がないものがＡとＣであるので、イベント受理制約Ａ、Ｃを仮イベント集合とする。そして、ＮＦＡ生成部１５０ｂは、初期状態のノード８ａを起点ノードとする。
【０１０５】
図１５Ｂの２段目に示すように、ＮＦＡ生成部１５０ｂは、起点ノードが初期状態のノード８ａであるので、仮イベント集合に集められたイベント受理制約（Ａ、Ｃ）に対応するイベント入力ノード８ｂ、８ｃを生成する。そして、ＮＦＡ生成部１５０ｂは、生成したノード８ｂに現ノード番号ｉを１加算して、加算した値１を割り当て、生成したノード８ｃに現ノード番号ｉを１加算して、加算した値２を割り当てる。そして、ＮＦＡ生成部１５０ｂは、起点ノード８ａからイベント入力ノード８ｂへε遷移で接続し、起点ノード８ａからイベント入力ノード８ｃへε遷移で接続する。
【０１０６】
図１５Ｂの３段目に示すように、ＮＦＡ生成部１５０ｂは、仮イベント集合に集められたイベント受理制約（Ａ、Ｃ）から未処理のイベント受理制約を１つ取り出す。ここでは、ＮＦＡ生成部１５０ｂはイベントＡを取り出す。そして、ＮＦＡ生成部１５０ｂは、イベント受理完了ノード８ｄを生成し、生成したノード８ｄに、現ノード番号ｉに１を加算した値３を割り当てる。そして、ＮＦＡ生成部１５０ｂは、イベントＡの受理によりイベント入力ノード８ｂからイベント受理完了ノード８ｄに遷移するエッジで接続し、＠リストをコピーする。
【０１０７】
続いて、ＮＦＡ生成部１５０ｂは、現在のイベント受理制約（Ａ）の前方の間隔制約がないので、イベント受理完了ノード８ｄを完了ノードとする。さらに、ＮＦＡ生成部１５０ｂは、取り出したイベント受理制約（Ａ）の後方への間隔制約を持つイベント受理制約を集め、仮イベント集合とする。ここでは、ＮＦＡ生成部１５０ｂは、イベントＡの後方イベントＢまでの間隔制約が２であるので、イベント受理制約Ｂを仮イベント集合とする。そして、ＮＦＡ生成部１５０ｂは、完了ノード８ｄを起点ノードとする。
【０１０８】
図１５Ｂの４段目に示すように、ＮＦＡ生成部１５０ｂは、起点ノード８ｄが初期状態のノードでなく、且つ仮イベント集合に集められたイベント受理制約（Ｂ）が２つ以上でないので、次の処理を行う。すなわち、ＮＦＡ生成部１５０ｂは、仮イベント集合に集められたイベント受理制約（Ｂ）に対応するイベント入力ノード８ｅを生成する。そして、ＮＦＡ生成部１５０ｂは、生成したノード８ｅに現ノード番号ｉに１を加算した値４を割り当てる。そして、ＮＦＡ生成部１５０ｂは、起点ノード８ｄからイベント入力ノード８ｅへε遷移で接続する。
【０１０９】
図１５Ｂの５段目に示すように、ＮＦＡ生成部１５０ｂは、仮イベント集合に集められたイベント受理制約（Ｂ）から未処理のイベント受理制約を１つ取り出す。ここでは、ＮＦＡ生成部１５０ｂはイベントＢを取り出す。そして、ＮＦＡ生成部１５０ｂは、イベント受理完了ノード８ｆを生成し、生成したノード８ｆに、現ノード番号ｉに１を加算した値５を割り当てる。そして、ＮＦＡ生成部１５０ｂは、前方間隔制約２を満たすイベントＢの受理によりイベント入力ノード８ｅからイベント受理完了ノード８ｆに遷移するエッジで接続する。すなわち、イベント入力ノード８ｅからイベント受理完了ノード８ｆへの遷移が「間隔条件ありの通常遷移」となる。さらに、ＮＦＡ生成部１５０ｂは、イベント入力ノード８ｅの＠リストのタイムアウトに前方間隔制約２を加えてからイベント受理完了ノード８ｆの＠リストにコピーする。
【０１１０】
続いて、ＮＦＡ生成部１５０ｂは、現在のイベント受理制約（Ｂ）の前方の間隔制約の数が２以上でないので、イベント受理完了ノード８ｆを完了ノードとする。さらに、ＮＦＡ生成部１５０ｂは、取り出したイベント受理制約（Ｂ）の後方への間隔制約を持つイベント受理制約を集め、仮イベント集合とする。ここでは、ＮＦＡ生成部１５０ｂは、イベントＢの後方イベントＤまでの間隔制約が６、イベントＥまでの間隔制約が５であるので、イベント受理制約Ｄ、Ｅを仮イベント集合とする。そして、ＮＦＡ生成部１５０ｂは、完了ノード８ｆを起点ノードとする。
【０１１１】
図１５Ｃの１段目に示すように、ＮＦＡ生成部１５０ｂは、起点ノード８ｆが初期状態のノードでなく、且つ仮イベント集合に集められたイベント受理制約（Ｄ、Ｅ）が２つ以上であるので、起点ノード８ｆに現＠番号ｊの値０を割り当てる。すなわち、この起点ノード８ｆは、＠番号０（＠０）を有する受理時刻保持ノードとなる。そして、ＮＦＡ生成部１５０ｂは、現＠番号ｊの値を、１加算した値１に設定する。
【０１１２】
図１５Ｃの２段目に示すように、ＮＦＡ生成部１５０ｂは、起点ノード８ｆの＠リスト２ｍに、割り当てた＠番号０およびタイムアウト０を設定する。
【０１１３】
図１５Ｃの３段目に示すように、ＮＦＡ生成部１５０ｂは、仮イベント集合に集められたイベント受理制約（Ｄ、Ｅ）に対応するイベント入力ノード８ｇ、８ｈを生成する。そして、ＮＦＡ生成部１５０ｂは、生成したノード８ｇに現ノード番号ｉ（５）に１を加算した値６を割り当て、生成したノード８ｈにさらに現ノード番号ｉ（６）に１を加算した値７を割り当てる。そして、ＮＦＡ生成部１５０ｂは、起点ノード８ｆからイベント入力ノード８ｇへε遷移で接続し、起点ノード８ｆからイベント入力ノード８ｈへε遷移で接続する。そして、ＮＦＡ生成部１５０ｂは、起点ノード８ｆの＠リストをイベント入力ノード８ｇ、８ｈのそれぞれの＠リストにコピーする。
【０１１４】
図１５Ｃの４段目に示すように、ＮＦＡ生成部１５０ｂは、仮イベント集合に集められたイベント受理制約（Ｄ、Ｅ）から未処理のイベント受理制約Ｄを取り出す。そして、ＮＦＡ生成部１５０ｂは、イベント受理完了ノード８ｉを生成し、生成したノード８ｉに、現ノード番号ｉに１を加算した値８を割り当てる。そして、ＮＦＡ生成部１５０ｂは、前方間隔制約６を満たすイベントＤの受理によりイベント入力ノード８ｇからイベント受理完了ノード８ｉに遷移するエッジで接続する。すなわち、イベント入力ノード８ｇからイベント受理完了ノード８ｉへの遷移が「間隔条件ありの通常遷移」となる。さらに、ＮＦＡ生成部１５０ｂは、イベント入力ノード８ｇの＠リストのタイムアウトに前方間隔制約６を加えてからイベント受理完了ノード８ｉの＠リストにコピーする。
【０１１５】
続いて、ＮＦＡ生成部１５０ｂは、現在のイベント受理制約（Ｄ）の前方の間隔制約の数が２以上でないので、イベント受理完了ノード８ｉを完了ノードとする。さらに、ＮＦＡ生成部１５０ｂは、取り出したイベント受理制約（Ｄ）の後方への間隔制約を持つイベント受理制約を集め、仮イベント集合とする。ここでは、ＮＦＡ生成部１５０ｂは、イベントＤの後方への間隔制約を持つイベント受理制約がないので、空の仮イベント集合とする。そして、ＮＦＡ生成部１５０ｂは、仮イベント集合が空なので、終端ノードリストに完了ノード８ｉを追加する。ここで、イベント受理制約Ｄの処理が終了する。
【０１１６】
図１５Ｃの５段目に示すように、ＮＦＡ生成部１５０ｂは、仮イベント集合に集められたイベント受理制約（Ｄ、Ｅ）から未処理のイベント受理制約を１つ取り出す。ここでは、ＮＦＡ生成部１５０ｂは、イベントＤの処理が終了しているので、未処理のイベントＥを取り出す。そして、ＮＦＡ生成部１５０ｂは、イベント受理完了ノード８ｉを生成し、生成したノード８ｊに、現ノード番号ｉに１を加算した値９を割り当てる。そして、ＮＦＡ生成部１５０ｂは、前方間隔制約５を満たすイベントＥの受理によりイベント入力ノード８ｈからイベント受理完了ノード８ｊに遷移するエッジで接続する。すなわち、イベント入力ノード８ｈからイベント受理完了ノード８ｊへの遷移が「間隔条件ありの通常遷移」となる。さらに、ＮＦＡ生成部１５０ｂは、イベント入力ノード８ｈの＠リストのタイムアウトに前方間隔制約５を加えてからイベント受理完了ノード８ｊの＠リストにコピーする。ここで、イベント受理制約Ｅの処理が終了する。
【０１１７】
続いて、ＮＦＡ生成部１５０ｂは、現在のイベント受理制約（Ｅ）の前方の間隔制約の数の数をＦとする。ここでは、イベントＥの前方間隔制約はイベントＢからの５の制約とイベントＣからの４の制約があるので、ＮＦＡ生成部１５０ｂは、前方の間隔制約の数Ｆを２に設定する。そして、ＮＦＡ生成部１５０ｂは、Ｆが２以上であり、現在のイベント受理制約（Ｅ）に対応する生成済みのイベント受理完了ノードがノード８ｊの１個のみであるので、仮イベント集合に集められたイベント受理制約のうち未処理のものがあるか否かを判定する。ここでは、ＮＦＡ生成部１５０ｂは、仮イベント集合に集められたイベント受理制約Ｄ、ＥおよびＢの処理が終了したので、元の仮イベント集合および元の起点ノードに戻す。すなわち、起点ノードは初期状態のノード８ａとなり、仮イベント集合はイベント受理制約Ａ、Ｃになる。
【０１１８】
図１５Ｄの１段目に示すように、ＮＦＡ生成部１５０ｂは、仮イベント集合に集められたイベント受理制約（Ａ、Ｃ）から未処理のイベント受理制約を１つ取り出す。ここでは、ＮＦＡ生成部１５０ｂは、イベントＡの処理が終了しているので、イベントＣを取り出す。そして、ＮＦＡ生成部１５０ｂは、イベント受理完了ノード８ｋを生成し、生成したノード８ｋに、現ノード番号ｉに１を加算した値１０を割り当てる。そして、ＮＦＡ生成部１５０ｂは、イベントＣの受理によりイベント入力ノード８ｃからイベント受理完了ノード８ｋに遷移するエッジで接続し、＠リストをコピーする。
【０１１９】
続いて、ＮＦＡ生成部１５０ｂは、現在のイベント受理制約（Ｃ）の前方の間隔制約がないので、イベント受理完了ノード８ｋを完了ノードとする。さらに、ＮＦＡ生成部１５０ｂは、取り出したイベント受理制約（Ｃ）の後方への間隔制約を持つイベント受理制約を集め、仮イベント集合とする。ここでは、ＮＦＡ生成部１５０ｂは、イベントＣの後方イベントＥまでの間隔制約が４であるので、イベント受理制約Ｅを仮イベント集合とする。そして、ＮＦＡ生成部１５０ｂは、完了ノード８ｋを起点ノードとする。
【０１２０】
図１５Ｄの２段目に示すように、ＮＦＡ生成部１５０ｂは、起点ノード８ｋが初期状態のノードでなく、且つ仮イベント集合に集められたイベント受理制約（Ｅ）が２つ以上でないので、次の処理を行う。すなわち、ＮＦＡ生成部１５０ｂは、仮イベント集合に集められたイベント受理制約（Ｅ）に対応するイベント入力ノード８ｌを生成する。そして、ＮＦＡ生成部１５０ｂは、生成したノード８ｌに現ノード番号ｉに１を加算した値１１を割り当てる。そして、ＮＦＡ生成部１５０ｂは、起点ノード８ｋからイベント入力ノード８ｌへε遷移で接続する。
【０１２１】
図１５Ｄの３段目に示すように、ＮＦＡ生成部１５０ｂは、仮イベント集合に集められたイベント受理制約（Ｅ）から未処理のイベント受理制約を１つ取り出す。ここでは、ＮＦＡ生成部１５０ｂはイベントＥを取り出す。そして、ＮＦＡ生成部１５０ｂは、イベント受理完了ノード８ｍを生成し、生成したノード８ｍに、現ノード番号ｉに１を加算した値１２を割り当てる。そして、ＮＦＡ生成部１５０ｂは、前方間隔制約４を満たすイベントＥの受理によりイベント入力ノード８ｌからイベント受理完了ノード８ｍに遷移するエッジで接続する。すなわち、イベント入力ノード８ｌからイベント受理完了ノード８ｍへの遷移が「間隔条件ありの通常遷移」となる。さらに、ＮＦＡ生成部１５０ｂは、イベント入力ノード８ｌの＠リストのタイムアウトに前方間隔制約４を加えてからイベント受理完了ノード８ｍの＠リストにコピーする。
【０１２２】
続いて、ＮＦＡ生成部１５０ｂは、現在のイベント受理制約（Ｅ）の前方の間隔制約の数をＦとする。ここでは、イベントＥの前方間隔制約はイベントＢからの５の制約とイベントＣからの４の制約があるので、ＮＦＡ生成部１５０ｂは、前方の間隔制約の数Ｆを２に設定する。
【０１２３】
図１５Ｄの４段目に示すように、ＮＦＡ生成部１５０ｂは、Ｆが２以上であり、現在のイベント受理制約（Ｅ）に対応する生成済みのイベント受理完了ノードがノード８ｊおよびノード８ｍの２個あるので、次の処理を行う。すなわち、ＮＦＡ生成部１５０ｂは、現在のイベント受理制約（Ｅ）に対応する合流ノード８ｎを生成する。そして、ＮＦＡ生成部１５０ｂは、生成したノード８ｎに現ノード番号ｉに１を加算した値１３を割り当てる。そして、ＮＦＡ生成部１５０ｂは、生成済みのイベント受理完了ノード８ｊ、８ｍから合流ノード８ｎへε＝遷移で接続する。
【０１２４】
図１５Ｄの５段目に示すように、ＮＦＡ生成部１５０ｂは、現在の＠番号ｊ（１）およびタイムアウト０を現在のイベント受理制約（Ｅ）に対応する生成済みの全てのイベント受理完了ノード８ｊ、８ｍに割り当て、それぞれの＠リストに追加する。すなわち、このイベント受理完了ノード８ｊ、８ｍは、＠番号１（＠１）を有する受理時刻保持ノードとなる。そして、ＮＦＡ生成部１５０ｂは、＠番号ｊに１を加算して２を設定する。
【０１２５】
図１５Ｅの１段目に示すように、ＮＦＡ生成部１５０ｂは、現在のイベント受理制約（Ｅ）に対応する生成済みのイベント受理完了ノード８ｊ、８ｍの＠リストにおいて、双方共が持っている同一の＠番号を合流ノード８ｎの指定＠番号とする。ここでは、ノード８ｊが持っている＠番号は＠０、＠１であり、ノード８ｊが持っている＠番号は＠１であるので、ＮＦＡ生成部１５０ｂは、＠１を合流ノード８ｎの指定＠番号とする。そして、ＮＦＡ生成部１５０ｂは、タイムアウトの中で一番大きい値（ここでは０）をタイムアウト長として、＠番号＠１とともに合流ノードに対応付けて登録する。
【０１２６】
図１５Ｅの２段目に示すように、ＮＦＡ生成部１５０ｂは、現在のイベント受理制約（Ｅ）に対応する生成済みのイベント受理完了ノード８ｊ、８ｍの各＠リストに含まれる＠番号および各＠番号で最大のタイムアウト長を合流ノード８ｎの＠リストに設定する。ここでは、ＮＦＡ生成部１５０ｂは、＠番号＠０およびタイムアウト長５を対応付けて設定し、＠番号＠１およびタイムアウト長０を対応付けて設定する。そして、ＮＦＡ生成部１５０ｂは、合成ノード８ｎを完了ノードとする。
【０１２７】
続いて、ＮＦＡ生成部１５０ｂは、現在のイベント受理制約（Ｅ）の後方の間隔制約がないので、終端ノードリストに完了ノードである合成ノード８ｎを追加する。すなわち、終端ノードリストには、完了ノード８ｉ、８ｎがある。ここで、イベント受理制約Ｅの処理が終了する。この結果、イベント受理制約Ａの処理が終了する。
【０１２８】
続いて、ＮＦＡ生成部１５０ｂは、仮イベント集合に集められたイベント受理制約（Ｅ）の処理が終了したので、元の仮イベント集合および元の起点ノードに戻す。すなわち、起点ノードは初期状態のノード８ａとなり、仮イベント集合はイベント受理制約Ａ、Ｃとなる。
【０１２９】
図１５Ｅの３段目に示すように、ＮＦＡ生成部１５０ｂは、戻した仮イベント集合に含まれるイベント受理制約Ａ、Ｃの処理を終了しているので、最終状態のノード８ｏを生成し、生成したノード８ｏに、現ノード番号ｉに１を加算した値１４を割り当てる。そして、ＮＦＡ生成部１５０ｂは、終端ノードリストに含まれるそれぞれの完了ノード８ｉ、８ｎから、生成した最終状態のノード８ｏへε＝遷移で接続する。
【０１３０】
図１５Ｅの４段目に示すように、ＮＦＡ生成部１５０ｂは、終端ノードリストに含まれる異なるノードについて、各ノードの＠リストを取り出す。ここでは、ＮＦＡ生成部１５０ｂは、終端ノードリストに含まれる完了ノード８ｉ、８ｎの各＠リストを取り出す。そして、ＮＦＡ生成部１５０ｂは、取り出した各＠リストに存在する共通の＠番号を指定＠番号として、タイムアウトの中で一番大きいものをタイムアウト長として最終状態のノード８ｏに登録する。ここでは、完了ノード８ｉの＠リストには、＠番号０とタイムアウト長６とが対応付けられている。また、完了ノード８ｎの＠リストには、＠番号０とタイムアウト長５とが対応付けられ、＠番号１とタイムアウト長０とが対応付けられている。このため、ＮＦＡ生成部１５０ｂは、指定＠番号を０として、タイムアウト長を６として最終状態のノード８ｏに登録する。
【０１３１】
上述したように、ＮＦＡ生成部１５０ｂは、図１５Ａ〜図１５Ｅ示す処理を実行することで、図１５Ａに示すイベントパターン１４０ａからＮＦＡ１４０ｂを生成する。
【０１３２】
［実施例に係る照合部におけるパターン照合の処理手順］
次に、実施例に係る照合部１５０ｃにおけるパターン照合の処理手順を、図１６〜図１８を参照して説明する。図１６は照合部におけるパターン照合の主処理の手順を示し、図１７は通常遷移を発動する処理の手順を示し、図１８は全てのε遷移とε＝遷移を発動する処理の手順を示す。
【０１３３】
［パターン照合の主処理の手順］
まず、パターン照合の主処理の手順について、図１６を参照して説明する。図１６は、実施例に係る照合部におけるパターン照合の主処理の手順を示すフローチャートである。例えば、図１６に示す処理は、イベントパターン１４０ａとイベントストリーム１４０ｃとを取得した後に、ＮＦＡ１４０ｂを生成したことを契機にして実行される。
【０１３４】
まず、照合部１５０ｃは、現在のイベント位置ｉの値を１に設定する（ステップＳ２１）。そして、照合部１５０ｃは、イベントＳ［ｉ］が存在するか否かを判定する（ステップＳ２２）。ここで、イベントＳ［ｉ］は、イベントストリーム１４０ｃの現在のイベント位置ｉ、言い換えると時刻ｉのイベントに対応する。
【０１３５】
イベントＳ［ｉ］が存在しない場合（ステップＳ２２；Ｎｏ）、照合部１５０ｃは、主処理を終了する。一方、イベントＳ［ｉ］が存在する場合（ステップＳ２２；Ｙｅｓ）、照合部１５０ｃは、イベントストリーム１４０ｃからイベントＳ［ｉ］を読み込む（ステップＳ２３）。
【０１３６】
続いて、照合部１５０ｃは、読み込んだイベントＳ［ｉ］に関するＮＦＡ（Ｎ（Ｐ））の全ての通常遷移を発動する（ステップＳ２４）。ここで、ＮＦＡ（Ｎ（Ｐ））は、ＮＦＡ１４０ｂに対応する。
【０１３７】
さらに、照合部１５０ｃは、ＮＦＡ（Ｎ（Ｐ））の全てのε遷移とε＝遷移を発動する（ステップＳ２５）。そして、照合部１５０ｃは、現在のイベント位置ｉの値に１を加算し（ステップＳ２６）、ステップＳ２２に移行する。
【０１３８】
［通常遷移を発動する処理の手順］
次に、図１６のステップＳ２４に示した通常遷移を発動する処理について、図１７を参照して説明する。図１７は、通常遷移を発動する処理の手順を示すフローチャートである。
【０１３９】
図１７に示すように、照合部１５０ｃは、状態ｊの値を１に設定し、遷移先状態ｋの値を０に設定する（ステップＳ２１１）。ここで、状態ｊはＮＦＡ１４０ｂのノード番号、すなわち状態番号に対応するものである。また、遷移先状態ｋは遷移先のノード番号、すなわち遷移先の状態番号に対応するものである。
【０１４０】
そして、照合部１５０ｃは、状態ｊが存在するか否かを判定し（ステップＳ２１２）、状態ｊが存在しない場合には（ステップＳ２１２；Ｎｏ）、処理を終了する。一方、照合部１５０ｃは、状態ｊが存在する場合には（ステップＳ２１２；Ｙｅｓ）、状態ｊからイベントＳ［ｉ］に関する通常遷移が出ているか否かを判定する（ステップＳ２１３）。通常遷移が出ていない場合には（ステップＳ２１３；Ｎｏ）、状態ｊの値に１を加算し（ステップＳ２１４）、ステップＳ２１２に移行する。
【０１４１】
一方、通常遷移が出ている場合には（ステップＳ２１３；Ｙｅｓ）、照合部１５０ｃは、間隔条件付きの通常遷移であるか否かを判定する（ステップＳ２１３Ａ）。そして、照合部１５０ｃは、間隔条件付きの通常遷移でない場合には（ステップＳ２１３Ａ；Ｎｏ）、仮リストを空に設定する（ステップＳ２１５）。ここで、仮リストはイベントリストを生成するための一時的に用いられる仮のリストであり、イベントリストと同じ構成を有する。また、イベントリストは、イベントを受理したノード毎に対応付けられ、イベントの受理状態が設定される。受理状態には、例えば＠番号位置と最終受理位置とが対応付けられる。＠番号位置には、＠番号が割り当てられた受理時刻保持ノードで受理したイベントのイベント位置を書き込む領域を指す。また、最終受理位置とは、現段階で最終的に受理したイベントのイベント位置を書き込む領域を指す。
【０１４２】
そして、照合部１５０ｃは、状態ｊの通常遷移先の状態番号を状態ｋに設定する（ステップＳ２１６）。そして、照合部１５０ｃは、状態ｋが＠番号が割り当てられているか否かを判定する（ステップＳ２１７）。すなわち、照合部１５０ｃは、状態ｋのノード番号に対応するノードが受理時刻保持ノードであるか否かを判定する。状態ｋが＠番号が割り当てられている場合には（ステップＳ２１７；Ｙｅｓ）、照合部１５０ｃは、仮リストの＠番号位置に現在のイベント位置ｉを書き込み（ステップＳ２１８）、ステップＳ２１９に移行する。そして、照合部１５０ｃは、仮リストの最終受理位置に現在のイベント位置ｉを書き込み、状態ｋのイベントリストとして追加する（ステップＳ２１９）。そして、照合部１５０ｃは、ステップＳ２２４に移行する。
【０１４３】
一方、照合部１５０ｃは、間隔条件付きの通常遷移である場合には（ステップＳ２１３Ａ；Ｙｅｓ）、状態ｊに未処理のイベントリストがあるか否かを判定する（ステップＳ２２０）。状態ｊに未処理のイベントリストがある場合には（ステップＳ２２０；Ｙｅｓ）、照合部１５０ｃは、未処理のイベントリストを選択し、選択したイベントリストの最終受理位置と現在のイベント位置ｉが間隔条件を満たすか否かを判定する（ステップＳ２２１）。そして、間隔条件を満たさない場合には（ステップＳ２２１；Ｎｏ）、照合部１５０ｃは、選択したイベントリストを削除し（ステップＳ２２２）、状態ｊの処理を継続すべく、ステップＳ２２０に移行する。一方、間隔条件を満たす場合には（ステップＳ２２１；Ｙｅｓ）、照合部１５０ｃは、選択したイベントリストを仮リストにコピーし（ステップＳ２２３）、ステップＳ２１６に移行する。
【０１４４】
すなわち、照合部１５０ｃは、状態ｊの通常遷移先の状態番号を状態ｋに設定する。そして、照合部１５０ｃは、状態ｋが＠番号が割り当てられている場合には、仮リストの＠番号位置に現在のイベント位置ｉを上書きし、仮リストの最終受理位置に現在のイベント位置ｉを上書きし、状態ｋのイベントリストとして追加する。一方、照合部１５０ｃは、状態ｋが＠番号が割り当てられていない場合には、仮リストの最終受理位置に現在のイベント位置ｉを上書きし、状態ｋのイベントリストとして追加する。
【０１４５】
続いて、照合部１５０ｃは、状態ｋが最終状態であり、且つイベントリストがあるか否かを判定する（ステップＳ２２４）。状態ｋが最終状態であり、且つイベントリストがある場合には（ステップＳ２２４；Ｙｅｓ）、照合部１５０ｃは、現在のイベント位置ｉを通知し、状態ｋのイベントリストを削除する（ステップＳ２２５）。すなわち、照合部１５０ｃは、イベント位置ｉをイベントパターンの終了時刻として通知する。そして、照合部１５０ｃは、状態ｊの処理を継続すべく、ステップＳ２２０に移行する。一方、状態ｋが最終状態でない場合、またはイベントリストがない場合には（ステップＳ２２４；Ｎｏ）、照合部１５０ｃは、状態ｊの処理を継続すべく、ステップＳ２２０に移行する。
【０１４６】
［全てのε遷移とε＝遷移を発動する処理の手順］
次に、図１６のステップＳ２５に示した全てのε遷移とε＝遷移を発動する処理について、図１８を参照して説明する。図１８は、全てのε遷移とε＝遷移を発動する処理の手順を示すフローチャートである。
【０１４７】
図１８に示すように、照合部１５０ｃは、状態ｊの値に１を設定する（ステップＳ２３１）。そして、照合部１５０ｃは、状態ｊが存在するか否かを判定する（ステップＳ２３２）。状態ｊが存在しない場合には（ステップＳ２３２；Ｎｏ）、照合部１５０ｃは処理を終了する。
【０１４８】
一方、状態ｊが存在する場合には（ステップＳ２３２；Ｙｅｓ）、照合部１５０ｃは状態ｊが合流ノードであるか否かを判定する（ステップＳ２３３）。状態ｊが合流ノードでない場合には（ステップＳ２３３；Ｎｏ）、照合部１５０ｃは状態ｊからε遷移が出ているか否かを判定する（ステップＳ２３４）。状態ｊからε遷移が出ていない場合には（ステップＳ２３４；Ｎｏ）、照合部１５０ｃは状態ｊの値に１を加算し（ステップＳ２３５）、ステップＳ２３２に移行する。一方、状態ｊからε遷移が出ている場合には（ステップＳ２３４；Ｙｅｓ）、照合部１５０ｃは状態ｊの全てのイベントリストを全ての遷移先の状態のイベントリストとして追加し、状態ｊのイベントリストを削除する（ステップＳ２３６）。
【０１４９】
続いて、照合部１５０ｃは、状態ｋが最終状態であり、且つイベントリストがあるか否かを判定する（ステップＳ２３７）。状態ｋが最終状態であり、且つイベントリストがある場合には（ステップＳ２３７；Ｙｅｓ）、照合部１５０ｃは、現在のイベント位置ｉを照合結果として通知し、状態ｋのイベントリストを削除する（ステップＳ２３８）。すなわち、照合部１５０ｃは、照合が完了した結果として、イベントパターンの終了時刻を通知する。そして、照合部１５０ｃは、状態ｊの処理を継続すべく、ステップＳ２３５に移行する。一方、状態ｋが最終状態でない場合、またはイベントリストがない場合には（ステップＳ２３７；Ｎｏ）、照合部１５０ｃは、状態ｊの処理を継続すべく、ステップＳ２３５に移行する。
【０１５０】
一方、状態ｊが合流ノードである場合には（ステップＳ２３３；Ｙｅｓ）、照合部１５０ｃは、状態ｊのε＝遷移元のイベントリストの、状態ｊで指定された指定＠番号の＠番号位置のイベント位置が一致しているイベントリストを探索する。そして、照合部１５０ｃは、探索の結果、＠番号位置のイベント位置が一致しているイベントリストの全ての組み合わせに対して、イベントリストを結合し、結合したイベントリストを状態ｊに追加する（ステップＳ２３９）。
【０１５１】
そして、照合部１５０ｃは、状態ｊの各ε＝遷移元のイベントリストの、状態ｊで指定された指定＠番号の＠番号位置のイベント位置を取り出す。そして、照合部１５０ｃは、取り出したイベント位置が｛「現在のイベント位置」−「状態ｊの各＠番号に対応するタイムアウト長」｝以下の場合、タイムアウトであると判断し、そのイベントリストを削除する（ステップＳ２４０）。
【０１５２】
続いて、照合部１５０ｃは、状態ｊが最終状態であり、且つイベントリストがあるか否かを判定する（ステップＳ２４１）。状態ｊが最終状態であり、且つイベントリストがある場合には（ステップＳ２４１；Ｙｅｓ）、照合部１５０ｃは、現在のイベント位置ｉを照合結果として通知し、状態ｊのイベントリストを削除する（ステップＳ２４２）。すなわち、照合部１５０ｃは、照合が完了した結果として、イベントパターンの終了時刻を通知する。そして、照合部１５０ｃは、状態ｊの処理を継続すべく、ステップＳ２３４に移行する。一方、状態ｊが最終状態でない場合、またはイベントリストがない場合には（ステップＳ２４１；Ｎｏ）、照合部１５０ｃは、状態ｊの処理を継続すべく、ステップＳ２３４に移行する。
【０１５３】
［パターン照合処理の一例］
次に、図を用いて照合部１５０ｃの処理を説明する。図１９Ａ〜図１９Ｋは、照合部の処理を説明するための図である。なお、図１９Ａ〜図１９Ｋの説明では、状態番号によって、各ノードを区別して説明する。以下では、状態番号１〜１４のノードを、状態１〜１４として説明する。また、ＮＦＡ１４０ｂと比較するイベントストリーム１４０ｃを、図３に示すものとし、各イベントをＳ［ｉ］（ｉ＝１〜１０）に保持するものとする。
【０１５４】
図１９Ａに示すように、イベントパターン１４０ａのデータ構造を、符号２０４ｐに示すものとする。イベントパターン１４０ａは、イベントＡからイベントＢまでの間隔を２以内とする非連続直列パターンを有する。そして、イベントパターン１４０ａは、イベントＢを分岐の起点とし、イベントＢからイベントＡまでの間隔を６以内とし、イベントＢからイベントＥまでの間隔を３以内とする分岐パターンを有する。さらに、イベントパターン１４０ａは、イベントＢからイベントＥまでの間隔を３以内とし、イベントＣからイベントＥまでの間隔を４以内とし、イベントＥを結合の終点とする結合パターンを有する。このイベントパターン１４０ａを入力としてＮＦＡ生成部１５０ｂによって生成されたＮＦＡは、符号２０４ｎに示すものとなる。
【０１５５】
図１９Ｂの１段目に示すように、照合部１５０ｃは、現在のイベント位置ｉの値を１に設定し、イベントストリーム１４０ｃからイベント位置１のイベントＳ［１］、すなわちイベント「Ａ」を読み込む。言い換えれば、照合部１５０ｃは、時刻１のイベント「Ａ」を読み込む。
【０１５６】
図１９Ｂの２段目に示すように、照合部１５０ｃは、状態ｊの値と遷移先状態ｋの値を初期化し、状態ｊの値を１に設定し、遷移先状態ｋの値を０に設定する。照合部１５０ｃは、状態ｊの値を１ずつ加算し、状態ｊからイベント「Ａ」に関する通常遷移が出ているか否かを判定する。ここでは、状態１からイベント「Ａ」に関する間隔条件なしの通常遷移が出ているので、照合部１５０ｃは、イベントの受理状態を設定する仮リストを空に設定する。そして、照合部１５０ｃは、状態ｋに状態１の通常遷移先である状態３を設定する。
【０１５７】
図１９Ｂの３段目に示すように、照合部１５０ｃは、状態３に＠番号が割り当てられていないので、仮リストの最終受理位置に現在のイベント位置１を設定し、設定後仮リストを状態３のイベントリスト１ｒとして追加する。そして、状態２から状態５まで各状態からイベント「Ａ」に関する通常遷移が出ていないので、照合部１５０ｃは、状態ｊの値を１ずつ増やし、５を設定する。
【０１５８】
図１９Ｂの４段目に示すように、照合部１５０ｃは、さらに状態ｊの値を１増やした状態６からイベント「Ａ」に関する間隔条件付きの通常遷移が出ているが、状態６に未処理のイベントリストがなく、間隔条件を比較する対象がないので、そのまま処理を継続する。
【０１５９】
続いて、照合部１５０ｃは、状態７から状態１４まで各状態からイベント「Ａ」に関する通常遷移が出ていないので、照合部１５０ｃは、現在のイベント位置１（時刻１）のイベント「Ａ」に関する全ての通常遷移の発動を終了する。
【０１６０】
図１９Ｂの５段目に示すように、照合部１５０ｃは、状態ｊの値を１ずつ増やしながら、状態ｊから出ている全てのε遷移とε＝遷移の発動を実行する。照合部１５０ｃは、状態３からε遷移が出ているので、状態３のイベントリストｒ１を遷移先の状態４のイベントリストｒ２として追加し、状態３のイベントリストｒ１を削除する。そして、照合部１５０ｃは、状態１４まで処理を完了すると、全てのε遷移とε＝遷移の発動を終了する。
【０１６１】
図１９Ｃの１段目に示すように、照合部１５０ｃは、現在のイベント位置ｉの値を２に設定し、イベントストリーム１４０ｃからイベント位置１のイベントＳ［２］、すなわちイベント「Ｃ」を読み込む。言い換えれば、照合部１５０ｃは、時刻２のイベント「Ｃ」を読み込む。
【０１６２】
図１９Ｃの２段目に示すように、照合部１５０ｃは、状態ｊの値と遷移先状態ｋの値を初期化し、状態ｊの値を１に設定し、遷移先状態ｋの値を０に設定する。照合部１５０ｃは、状態ｊの値を１ずつ加算し、状態ｊからイベント「Ｃ」に関する通常遷移が出ているか否かを判定する。ここでは、状態２からイベント「Ｃ」に関する間隔条件なしの通常遷移が出ているので、照合部１５０ｃは、仮リストを空に設定する。そして、照合部１５０ｃは、状態ｋに状態２の通常遷移先である状態１０を設定する。
【０１６３】
図１９Ｃの３段目に示すように、照合部１５０ｃは、状態１０に＠番号が割り当てられていないので、仮リストの最終受理位置に現在のイベント位置２を設定し、設定後仮リストを状態１０のイベントリストｒ３として追加する。そして、状態３から状態１４まで各状態からイベント「Ｃ」に関する通常遷移が出ていないので、照合部１５０ｃは、現在のイベント位置２（時刻２）のイベント「Ｃ」に関する全ての通常遷移の発動を終了する。
【０１６４】
図１９Ｃの４段目に示すように、照合部１５０ｃは、状態ｊの値を１ずつ増やしながら、状態ｊから出ている全てのε遷移とε＝遷移の発動を実行する。照合部１５０ｃは、状態３からε遷移が出ているが、状態３のイベントリストがもともと空なので、状態３のイベントリストに変化はない。
【０１６５】
図１９Ｃの５段目に示すように、照合部１５０ｃは、状態１０からε遷移を発動し、状態１０のイベントリストｒ３を遷移先の状態１１のイベントリストｒ４として追加し、状態１０のイベントリストｒ３を削除する。そして、照合部１５０ｃは、状態１４まで処理を完了すると、全てのε遷移とε＝遷移の発動を終了する。
【０１６６】
図１９Ｄの１段目に示すように、照合部１５０ｃは、現在のイベント位置ｉの値を３に設定し、イベントストリーム１４０ｃからイベント位置３のイベントＳ［３］、すなわちイベント「Ａ」を読み込む。言い換えれば、照合部１５０ｃは、時刻３のイベント「Ａ」を読み込む。
【０１６７】
図１９Ｄの２段目に示すように、照合部１５０ｃは、状態ｊの値と遷移先状態ｋの値を初期化し、状態ｊの値を１に設定し、遷移先状態ｋの値を０に設定する。照合部１５０ｃは、状態ｊの値を１ずつ加算し、状態ｊからイベント「Ａ」に関する通常遷移が出ているか否かを判定する。ここでは、状態１からイベント「Ａ」に関する間隔条件なしの通常遷移が出ているので、照合部１５０ｃは、仮リストを空に設定する。そして、照合部１５０ｃは、状態ｋに状態１の通常遷移先である状態３を設定する。そして、照合部１５０ｃは、状態３に＠番号が割り当てられていないので、仮リストの最終受理位置に現在のイベント位置３を設定し、設定後仮リストを状態３のイベントリストｒ５として追加する。
【０１６８】
続いて、照合部１５０ｃは、状態６からイベント「Ａ」に関する間隔条件付きの通常遷移が出ているが、状態６に未処理のイベントリストがなく、間隔条件を比較する対象がないので、そのまま処理を継続する。そして、照合部１５０ｃは、状態７から状態１４まで各状態からイベント「Ａ」に関する通常遷移が出ていないので、照合部１５０ｃは、現在のイベント位置３（時刻３）のイベント「Ａ」に関する全ての通常遷移の発動を終了する。
【０１６９】
図１９Ｄの３段目に示すように、照合部１５０ｃは、状態ｊの値を１ずつ増やしながら、状態ｊから出ている全てのε遷移とε＝遷移の発動を実行する。照合部１５０ｃは、状態３からε遷移が出ているので、状態３のイベントリストｒ５を遷移先の状態４のイベントリストｒ６として追加し、状態３のイベントリストｒ５を削除する。そして、照合部１５０ｃは、状態１４まで処理を完了すると、全てのε遷移とε＝遷移の発動を終了する。
【０１７０】
図１９Ｅの１段目に示すように、照合部１５０ｃは、現在のイベント位置ｉの値を４に設定し、イベントストリーム１４０ｃからイベント位置４のイベントＳ［４］、すなわちイベント「Ｂ」を読み込む。言い換えれば、照合部１５０ｃは、時刻４のイベント「Ｂ」を読み込む。
【０１７１】
図１９Ｅの２段目に示すように、照合部１５０ｃは、状態ｊの値と遷移先状態ｋの値を初期化し、状態ｊの値を１に設定し、遷移先状態ｋの値を０に設定する。照合部１５０ｃは、状態ｊの値を１ずつ加算し、状態ｊからイベント「Ｂ」に関する通常遷移が出ているか否かを判定する。ここでは、状態４からイベント「Ｂ」に関する間隔条件ありの通常遷移が出ているので、照合部１５０ｃは、状態４の未処理のイベントリストｒ２を選択し、選択したイベントリストｒ２の最終受理位置と現在のイベント位置４が間隔条件を満たすか否かを判定する。選択したイベントリストｒ２の最終受理位置が１であり、現在のイベント位置４との間隔が３であるので、照合部１５０ｃは、間隔条件２を満たさないと判定し、イベントリストｒ２を削除する。
【０１７２】
図１９Ｅの３段目に示すように、照合部１５０ｃは、状態４の未処理のイベントリストｒ６を選択し、選択したイベントリストｒ６の最終受理位置と現在のイベント位置４が間隔条件を満たすか否かを判定する。選択したイベントリストｒ６の最終受理位置が３であり、現在のイベント位置４との間隔が１であるので、照合部１５０ｃは、間隔条件２を満たすと判定する。そして、照合部１５０ｃは、仮リストにそのイベントリストｒ６をコピーし、状態ｋに状態４の通常遷移先である状態５を設定する。
【０１７３】
図１９Ｅの４段目に示すように、照合部１５０ｃは、状態５に＠番号０が割り当てられているので、仮リストの＠番号位置ｘ１に現在のイベント位置４を書き込む。
【０１７４】
図１９Ｅの５段目に示すように、照合部１５０ｃは、仮リストの最終受理位置ｚ１に現在のイベント位置４を設定する。そして、照合部１５０ｃは、仮リストを状態５のイベントリストｒ７として追加する。そして、照合部１５０ｃは、状態５から状態１４まで各状態からイベント「Ｂ」に関する通常遷移が出ていないので、照合部１５０ｃは、現在のイベント位置４（時刻４）のイベント「Ｂ」に関する全ての通常遷移の発動を終了する。
【０１７５】
図１９Ｅの６段目に示すように、照合部１５０ｃは、状態ｊの値を１ずつ増やしながら、状態ｊから出ている全てのε遷移とε＝遷移の発動を実行する。照合部１５０ｃは、状態５から状態６および状態７にε遷移が出ているので、状態５のイベントリストｒ７を遷移先の状態６および状態７のイベントリストｒ８、ｒ９として追加する。そして、照合部１５０ｃは、状態５のイベントリストｒ７を削除する。そして、照合部１５０ｃは、状態１４まで処理を完了すると、全てのε遷移とε＝遷移の発動を終了する。
【０１７６】
図１９Ｆの１段目に示すように、照合部１５０ｃは、現在のイベント位置ｉの値を５に設定し、イベントストリーム１４０ｃからイベント位置５のイベントＳ［５］、すなわちイベント「Ａ」を読み込む。言い換えれば、照合部１５０ｃは、時刻５のイベント「Ａ」を読み込む。
【０１７７】
図１９Ｆの２段目に示すように、照合部１５０ｃは、状態ｊの値と遷移先状態ｋの値を初期化し、状態ｊの値を１に設定し、遷移先状態ｋの値を０に設定する。照合部１５０ｃは、状態ｊの値を１ずつ加算し、状態ｊからイベント「Ａ」に関する通常遷移が出ているか否かを判定する。ここでは、状態１からイベント「Ａ」に関する間隔条件なしの通常遷移が出ているので、照合部１５０ｃは、仮リストを空に設定する。そして、照合部１５０ｃは、状態ｋに状態１の通常遷移先である状態３を設定する。そして、照合部１５０ｃは、状態３に＠番号が割り当てられていないので、仮リストの最終受理位置に現在のイベント位置５を設定し、設定後仮リストを状態３のイベントリストｒ１０として追加する。
【０１７８】
図１９Ｆの３段目に示すように、照合部１５０ｃは、状態６からイベント「Ａ」に関する間隔条件ありの通常遷移が出ているので、照合部１５０ｃは、状態６の未処理のイベントリストｒ８を選択し、選択したイベントリストｒ８の最終受理位置と現在のイベント位置５が間隔条件を満たすか否かを判定する。選択したイベントリストｒ８の最終受理位置が４であり、現在のイベント位置５との間隔が１であるので、照合部１５０ｃは、間隔条件６を満たすと判定する。そして、照合部１５０ｃは、仮リストにそのイベントリストｒ８をコピーし、状態ｋに状態６の通常遷移先である状態８を設定する。
【０１７９】
図１９Ｆの４段目に示すように、照合部１５０ｃは、状態８に＠番号が割り当てられていないので、仮リストの最終受理位置に現在のイベント位置５を設定し、設定後仮リストを状態８のイベントリストｒ１１として追加する。そして、照合部１５０ｃは、状態７から状態１４まで各状態からイベント「Ａ」に関する通常遷移が出ていないので、照合部１５０ｃは、現在のイベント位置５（時刻５）のイベント「Ａ」に関する全ての通常遷移の発動を終了する。
【０１８０】
図１９Ｆの５段目に示すように、照合部１５０ｃは、状態ｊの値を１ずつ増やしながら、状態ｊから出ている全てのε遷移とε＝遷移の発動を実行する。照合部１５０ｃは、状態３から状態４にε遷移が出ているので、状態３のイベントリストｒ１０を遷移先の状態４のイベントリストｒ１２として追加する。そして、照合部１５０ｃは、状態３のイベントリストｒ１０を削除する。
【０１８１】
図１９Ｆの６段目に示すように、照合部１５０ｃは、状態１４が合流ノードであるので、状態１４のε＝遷移元の状態８、１３のイベントリストの、状態１４で指定された指定＠番号０の＠番号位置のイベント位置が一致しているイベントリストを探索する。ここでは、１つのε＝遷移元の状態１３にイベントリストがないので、状態１４のイベントリストに変化はない。そして、照合部１５０ｃは、状態１４まで処理を完了したので、全てのε遷移とε＝遷移の発動を終了する。
【０１８２】
図１９Ｇの１段目に示すように、照合部１５０ｃは、現在のイベント位置ｉの値を６に設定し、イベントストリーム１４０ｃからイベント位置４のイベントＳ［６］、すなわちイベント「Ｂ」を読み込む。言い換えれば、照合部１５０ｃは、時刻６のイベント「Ｂ」を読み込む。
【０１８３】
図１９Ｇの２段目に示すように、照合部１５０ｃは、状態ｊの値と遷移先状態ｋの値を初期化し、状態ｊの値を１に設定し、遷移先状態ｋの値を０に設定する。照合部１５０ｃは、状態ｊの値を１ずつ加算し、状態ｊからイベント「Ｂ」に関する通常遷移が出ているか否かを判定する。ここでは、状態４からイベント「Ｂ」に関する間隔条件ありの通常遷移が出ているので、照合部１５０ｃは、状態４の未処理のイベントリストｒ１２を選択し、選択したイベントリストｒ１２の最終受理位置と現在のイベント位置６が間隔条件を満たすか否かを判定する。選択したイベントリストｒ１２の最終受理位置が５であり、現在のイベント位置６との間隔が１であるので、照合部１５０ｃは、間隔条件２を満たすと判定する。そして、照合部１５０ｃは、仮リストにそのイベントリストｒ１２をコピーし、状態ｋに状態４の通常遷移先である状態５を設定する。照合部１５０ｃは、状態５に＠番号０が割り当てられているので、仮リストの＠番号位置に現在のイベント位置６を書き込む。そして、照合部１５０ｃは、仮リストの最終受理位置に現在のイベント位置６を設定する。そして、照合部１５０ｃは、仮リストを状態５のイベントリストｒ１３として追加する。そして、照合部１５０ｃは、状態５から状態１４まで各状態からイベント「Ｂ」に関する通常遷移が出ていないので、照合部１５０ｃは、現在のイベント位置６（時刻６）のイベント「Ｂ」に関する全ての通常遷移の発動を終了する。
【０１８４】
図１９Ｇの３段目に示すように、照合部１５０ｃは、状態ｊの値を１ずつ増やしながら、状態ｊから出ている全てのε遷移とε＝遷移の発動を実行する。照合部１５０ｃは、状態５から状態６および状態７にε遷移が出ているので、状態５のイベントリストｒ１３を遷移先の状態６および状態７のイベントリストｒ１４、ｒ１５として追加する。そして、照合部１５０ｃは、状態５のイベントリストｒ１３を削除する。そして、照合部１５０ｃは、状態１４まで処理を完了すると、全てのε遷移とε＝遷移の発動を終了する。
【０１８５】
図１９Ｈの１段目に示すように、照合部１５０ｃは、現在のイベント位置ｉの値を７に設定し、イベントストリーム１４０ｃからイベント位置７のイベントＳ［７］、すなわちイベント「Ｅ」を読み込む。言い換えれば、照合部１５０ｃは、時刻７のイベント「Ｅ」を読み込む。
【０１８６】
図１９Ｈの２段目に示すように、照合部１５０ｃは、状態ｊの値と遷移先状態ｋの値を初期化し、状態ｊの値を１に設定し、遷移先状態ｋの値を０に設定する。照合部１５０ｃは、状態ｊの値を１ずつ加算し、状態ｊからイベント「Ｅ」に関する通常遷移が出ているか否かを判定する。ここでは、状態７からイベント「Ｅ」に関する間隔条件ありの通常遷移が出ているので、照合部１５０ｃは、状態７の未処理のイベントリストｒ９を選択し、選択したイベントリストｒ９の最終受理位置と現在のイベント位置７が間隔条件を満たすか否かを判定する。選択したイベントリストｒ９の最終受理位置が４であり、現在のイベント位置７との間隔が３であるので、照合部１５０ｃは、間隔条件３を満たすと判定する。そして、照合部１５０ｃは、仮リストにそのイベントリストｒ９をコピーし、状態ｋに状態７の通常遷移先である状態９を設定する。そして、照合部１５０ｃは、状態９に＠番号１が割り当てられているので、仮リストの＠番号１の＠番号位置に現在のイベント位置７を書き込む。そして、照合部１５０ｃは、仮リストの最終受理位置に現在のイベント位置７を設定する。そして、照合部１５０ｃは、仮リストを状態９のイベントリストｒ１６として追加する。
【０１８７】
続いて、照合部１５０ｃは、状態７の未処理のイベントリストｒ１５を選択し、選択したイベントリストｒ１５の最終受理位置と現在のイベント位置７が間隔条件を満たすか否かを判定する。選択したイベントリストｒ１５の最終受理位置が６であり、現在のイベント位置７との間隔が２であるので、照合部１５０ｃは、間隔条件３を満たすと判定する。そして、照合部１５０ｃは、仮リストにそのイベントリストｒ１５をコピーし、状態ｋに状態７の通常遷移先である状態９を設定する。そして、照合部１５０ｃは、状態９に＠番号１が割り当てられているので、仮リストの＠番号１の＠番号位置に現在のイベント位置７を書き込む。そして、照合部１５０ｃは、仮リストの最終受理位置に現在のイベント位置７を設定する。そして、照合部１５０ｃは、仮リストを状態９のイベントリストｒ１７として追加する。そして、照合部１５０ｃは、状態８から状態１４まで各状態からイベント「Ｅ」に関する通常遷移が出ていないので、照合部１５０ｃは、現在のイベント位置７（時刻７）のイベント「Ｅ」に関する全ての通常遷移の発動を終了する。
【０１８８】
図１９Ｈの３段目に示すように、照合部１５０ｃは、状態ｊの値を１ずつ増やしながら、状態ｊから出ている全てのε遷移とε＝遷移の発動を実行する。照合部１５０ｃは、状態１３が合流ノードであるので、状態１３のε＝遷移元の状態９、１２のイベントリストの、状態１３で指定された指定＠番号１の＠番号位置のイベント位置が一致しているイベントリストを探索する。ここでは、１つのε＝遷移元の状態１２にイベントリストがないので、状態１３のイベントリストに変化はない。
【０１８９】
続いて、照合部１５０ｃは、状態１３のε＝遷移元９、１２のイベントリストｒ１６、ｒ１７の、状態１３で指定された指定＠番号１に対応するイベント位置（＠１の受理時刻）を取り出す。ここでは、照合部１５０ｃは、イベントリストｒ１６から７、イベントリストｒ１７から７を取り出す。そして、照合部１５０ｃは、取り出したイベント位置が｛「現在のイベント位置」−「状態１３の＠番号１に対応するタイムアウト長」｝以下であるか否かを判定する。ここでは、取り出したイベント位置が７、現在のイベント位置は７、状態１３の＠番号１に対応するタイムアウト長が０であり、「７＝７−０」となるので、照合部１５０ｃは、タイムアウトであると判断し、イベントリストｒ１６、ｒ１７を削除する。
【０１９０】
続いて、状態１４は合流ノードであるが、状態１４のε＝遷移元の状態８、１３のうち状態１３にイベントリストがないので、状態１４のイベントリストに変化はない。そして、状態８のイベントリストｒ１１の、状態１４で指定された指定＠番号０に対応するイベント位置が４であり、「４＞７−６」となるので、照合部１５０ｃは、タイムアウトでないと判断し、イベントリストｒ１１をそのままにする。そして、照合部１５０ｃは、状態１４まで処理を完了したので、全てのε遷移とε＝遷移の発動を終了する。
【０１９１】
図１９Ｉの１段目に示すように、照合部１５０ｃは、現在のイベント位置ｉの値を８に設定し、イベントストリーム１４０ｃからイベント位置１のイベントＳ［８］、すなわちイベント「Ｃ」を読み込む。言い換えれば、照合部１５０ｃは、時刻８のイベント「Ｃ」を読み込む。
【０１９２】
図１９Ｉの２段目に示すように、照合部１５０ｃは、状態ｊの値と遷移先状態ｋの値を初期化し、状態ｊの値を１に設定し、遷移先状態ｋの値を０に設定する。照合部１５０ｃは、状態ｊの値を１ずつ加算し、状態ｊからイベント「Ｃ」に関する通常遷移が出ているか否かを判定する。ここでは、状態２からイベント「Ｃ」に関する間隔条件なしの通常遷移が出ているので、照合部１５０ｃは、仮リストを空に設定し、状態ｋに状態２の通常遷移先である状態１０を設定する。
【０１９３】
続いて、照合部１５０ｃは、状態１０に＠番号が割り当てられていないので、仮リストの最終受理位置に現在のイベント位置８を設定し、設定後仮リストを状態１０のイベントリストｒ１６として追加する。そして、状態３から状態１４まで各状態からイベント「Ｃ」に関する通常遷移が出ていないので、照合部１５０ｃは、現在のイベント位置８（時刻８）のイベント「Ｃ」に関する全ての通常遷移の発動を終了する。
【０１９４】
図１９Ｉの３段目に示すように、照合部１５０ｃは、状態ｊの値を１ずつ増やしながら、状態ｊから出ている全てのε遷移とε＝遷移の発動を実行する。照合部１５０ｃは、状態１０からε遷移が出ているので、状態１０のイベントリストｒ１６を遷移先の状態１１のイベントリストｒ１７として追加し、状態１０のイベントリストｒ１６を削除する。そして、照合部１５０ｃは、状態１４まで処理を完了すると、全てのε遷移とε＝遷移の発動を終了する。
【０１９５】
図１９Ｊの１段目に示すように、照合部１５０ｃは、現在のイベント位置ｉの値を９に設定し、イベントストリーム１４０ｃからイベント位置９のイベントＳ［９］、すなわちイベント「Ｅ」を読み込む。言い換えれば、照合部１５０ｃは、時刻９のイベント「Ｅ」を読み込む。
【０１９６】
図１９Ｊの２段目に示すように、照合部１５０ｃは、状態ｊの値と遷移先状態ｋの値を初期化し、状態ｊの値を１に設定し、遷移先状態ｋの値を０に設定する。照合部１５０ｃは、状態ｊの値を１ずつ加算し、状態ｊからイベント「Ｅ」に関する通常遷移が出ているか否かを判定する。ここでは、状態７からイベント「Ｅ」に関する間隔条件ありの通常遷移が出ているので、照合部１５０ｃは、状態７の未処理のイベントリストｒ９を選択し、選択したイベントリストｒ９の最終受理位置と現在のイベント位置９が間隔条件を満たすか否かを判定する。選択したイベントリストｒ９の最終受理位置が４であり、現在のイベント位置９との間隔が５であり、間隔条件３を超えているので、照合部１５０ｃは、間隔条件３を満たさないと判定する。そして、照合部１５０ｃは、そのイベントリストｒ９を削除する。
【０１９７】
続いて、照合部１５０ｃは、状態７の未処理のイベントリストｒ１５を選択し、選択したイベントリストｒ１５の最終受理位置と現在のイベント位置７が間隔条件を満たすか否かを判定する。選択したイベントリストｒ１５の最終受理位置が６であり、現在のイベント位置９との間隔が３であるので、照合部１５０ｃは、間隔条件３を満たすと判定する。そして、照合部１５０ｃは、仮リストにそのイベントリストｒ１５をコピーし、状態ｋに状態７の通常遷移先である状態９を設定する。そして、照合部１５０ｃは、状態９に＠番号１が割り当てられているので、仮リストの＠番号１の＠番号位置ｙ２に現在のイベント位置９を書き込む。そして、照合部１５０ｃは、仮リストの最終受理位置ｚ２に現在のイベント位置９を設定する。そして、照合部１５０ｃは、仮リストを状態９のイベントリストｒ１８として追加する。
【０１９８】
さらに、状態１１からイベント「Ｅ」に関する間隔条件ありの通常遷移が出ているので、照合部１５０ｃは、状態７の場合と同様に処理する。すなわち、照合部１５０ｃは、＠番号位置を現在のイベント位置９とし、最終受理位置を９とした仮リストを状態１２のイベントリストｒ１９として追加する。そして、照合部１５０ｃは、状態１２から状態１４まで各状態からイベント「Ｅ」に関する通常遷移が出ていないので、照合部１５０ｃは、現在のイベント位置９（時刻９）のイベント「Ｅ」に関する全ての通常遷移の発動を終了する。
【０１９９】
図１９Ｊの３段目に示すように、照合部１５０ｃは、状態ｊの値を１ずつ増やしながら、状態ｊから出ている全てのε遷移とε＝遷移の発動を実行する。照合部１５０ｃは、状態１３が合流ノードであるので、状態１３のε＝遷移元の状態９、１２のイベントリストの、状態１３で指定された指定＠番号１の＠番号位置のイベント位置が一致しているイベントリストを探索する。ここでは、状態９のイベントリストｒ１８の指定＠番号１に対応するイベント位置と状態１２のイベントリストｒ１９の指定＠番号１に対応するイベント位置とが９で一致している。そこで、照合部１５０ｃは、これらイベントリストｒ１８、ｒ１９の組み合わせに対して、イベントリストを結合し、結合したイベントリストｒ２０を状態１３に追加する。
【０２００】
図１９Ｊの４段目に示すように、照合部１５０ｃは、状態１３のε＝遷移元９、１２のイベントリストｒ１８、ｒ１９の、状態１３で指定された指定＠番号１に対応するイベント位置（＠１の受理時刻）を取り出す。ここでは、照合部１５０ｃは、イベントリストｒ１８から９、イベントリストｒ１９から９を取り出す。そして、照合部１５０ｃは、取り出したイベント位置が｛「現在のイベント位置」−「状態１３の＠番号１に対応するタイムアウト長」｝以下であるか否かを判定する。ここでは、取り出したイベント位置が９、現在のイベント位置は９、状態１３の＠番号１に対応するタイムアウト長が０であり、「９＝９−０」となるので、照合部１５０ｃは、タイムアウトであると判断し、イベントリストｒ１８、ｒ１９を削除する。
【０２０１】
図１９Ｊの５段目に示すように、照合部１５０ｃは、状態１４が合流ノードであるので、状態１４のε＝遷移元の状態８、１３のイベントリストの、状態１４で指定された指定＠番号０の＠番号位置のイベント位置が一致しているイベントリストを探索する。ここでは、状態８のイベントリストｒ１１の指定＠番号０に対応するイベント位置が４であり、状態１３のイベントリストｒ２０の指定＠番号０に対応するイベント位置が６であり、各イベント位置が一致していないので、状態１４のイベントリストに変化はない。そして、照合部１５０ｃは、状態１４まで処理を完了したので、全てのε遷移とε＝遷移の発動を終了する。
【０２０２】
図１９Ｋの１段目に示すように、照合部１５０ｃは、現在のイベント位置ｉの値を１０に設定し、イベントストリーム１４０ｃからイベント位置１０のイベントＳ［１０］、すなわちイベント「Ａ」を読み込む。言い換えれば、照合部１５０ｃは、時刻１０のイベント「Ａ」を読み込む。
【０２０３】
図１９Ｋの２段目に示すように、照合部１５０ｃは、状態ｊの値と遷移先状態ｋの値を初期化し、状態ｊの値を１に設定し、遷移先状態ｋの値を０に設定する。照合部１５０ｃは、状態ｊの値を１ずつ加算し、状態ｊからイベント「Ａ」に関する通常遷移が出ているか否かを判定する。ここでは、状態１からイベント「Ａ」に関する間隔条件なしの通常遷移が出ているので、照合部１５０ｃは、仮リストを空に設定する。そして、照合部１５０ｃは、状態ｋに状態１の通常遷移先である状態３を設定する。そして、照合部１５０ｃは、状態３に＠番号が割り当てられていないので、仮リストの最終受理位置に現在のイベント位置１０を設定し、設定後仮リストを状態３のイベントリストｒ２１として追加する。
【０２０４】
続いて、照合部１５０ｃは、状態６からイベント「Ａ」に関する間隔条件ありの通常遷移が出ているので、照合部１５０ｃは、状態６の未処理のイベントリストｒ８を選択し、選択したイベントリストｒ８の最終受理位置と現在のイベント位置１０が間隔条件を満たすか否かを判定する。選択したイベントリストｒ８の最終受理位置が４であり、現在のイベント位置１０との間隔が６であるので、照合部１５０ｃは、間隔条件６を満たすと判定する。そして、照合部１５０ｃは、仮リストにそのイベントリストｒ８をコピーし、状態ｋに状態６の通常遷移先である状態８を設定する。そして、照合部１５０ｃは、状態８に＠番号が割り当てられていないので、仮リストの最終受理位置に現在のイベント位置１０を設定し、設定後仮リストを状態８のイベントリストｒ２２として追加する。
【０２０５】
続いて、照合部１５０ｃは、状態６の未処理のイベントリストｒ１４についてもイベントリストｒ８と同様に処理し、状態８にイベントリストｒ２３を追加する。そして、照合部１５０ｃは、状態７から状態１４まで各状態からイベント「Ａ」に関する通常遷移が出ていないので、照合部１５０ｃは、現在のイベント位置１０（時刻１０）のイベント「Ａ」に関する全ての通常遷移の発動を終了する。
【０２０６】
図１９Ｋの３段目に示すように、照合部１５０ｃは、状態ｊの値を１ずつ増やしながら、状態ｊから出ている全てのε遷移とε＝遷移の発動を実行する。照合部１５０ｃは、状態３から状態４にε遷移が出ているので、状態３のイベントリストｒ２１を遷移先の状態４のイベントリストｒ２４として追加し、状態３のイベントリストｒ２１を削除する。
【０２０７】
図１９Ｋの４段目に示すように、照合部１５０ｃは、状態１４が合流ノードであるので、状態１４のε＝遷移元の状態８、１３のイベントリストの、状態１４で指定された指定＠番号０の＠番号位置のイベント位置が一致しているイベントリストを探索する。ここでは、状態８のイベントリストｒ２３の指定＠番号０に対応するイベント位置と状態１３のイベントリストｒ２０の指定＠番号０に対応するイベント位置とが６で一致している。そこで、照合部１５０ｃは、これらイベントリストｒ２３、ｒ２０の組み合わせに対して、イベントリストを結合し、結合したイベントリストｒ２５を状態１４に追加する。
【０２０８】
図１９Ｋの５段目に示すように、照合部１５０ｃは、状態１４が最終状態で、イベントリストがあるので、現在のイベント位置１４を照合結果として通知し、状態１４のイベントリストを削除する。すなわち、照合部１５０ｃは、照合が完了した結果として、イベントパターンの終了時刻を通知する。そして、照合部１５０ｃは、状態１４まで処理を完了したので、全てのε遷移とε＝遷移の発動を終了する。
【０２０９】
照合部１５０ｃは、上述した図１９Ａ〜図１９Ｋに示す処理を実行することにより、ＮＦＡ１４０ｂを利用して、イベントストリーム１４０ｃを照合する。照合部１５０ｃは、照合結果をユーザ端末５０に通知する。なお、照合部１５０ｃは、照合結果を表示部１３０に表示させても良い。上述した図１９Ａ〜図１９Ｋでは、照合結果を、イベントストリーム１４０ｃ上のイベントパターン１４０ａの終了時刻としたが、開始時刻を含んだものとしても良い。
【０２１０】
［実施例の効果］
次に、本実施例にかかる照合装置１００の効果について説明する。照合装置１００は、イベントパターン１４０ａに含まれる分岐パターンについて、分岐パターンの分岐の起点となるイベントの受理時刻を当該イベントの遷移先を示す起点ノードに対応付けて保持させる。また、照合装置１００は、起点ノードから分岐パターンの分岐先となるイベントおよび間隔条件を対応付けた分岐ノードに接続する。また、照合装置１００は、複数の分岐ノードから、複数の分岐ノードを結合する結合点を示す結合点ノードに接続することで、ＮＦＡ１４０ｂを生成する。そして、照合装置１００は、複数のイベントの発生順序を含むイベントストリーム１４０ｃと、ＮＦＡ１４０ｂとを順次比較し、分岐パターンの分岐の起点となるイベントが起点ノードで受理されると、受理されたイベントの受理時刻を起点ノードに対応付けて保持する。また、照合装置１００は、分岐の起点となるイベントに後続するイベントが分岐ノードで受理されると、受理されたイベントの受理が分岐ノードに対応付けられた間隔条件を満たせば、該保持した受理時刻を分岐ノードの受理状態と共に遷移させる。また、照合装置１００は、結合点ノードにて複数の分岐ノードから遷移された受理時刻に同一の受理時刻があると、当該受理時刻を含む結合状態を更に遷移させることで、イベントストリーム１４０ｃにイベントパターン１４０ａが含まれているか否かを照合する。照合装置１００によれば、イベントパターンの分岐パターンにイベント間の間隔条件があっても、イベント間の分岐パターンを誤ることなく照合を行うことができるため、イベントパターンを効率的に照合することができる。
【０２１１】
また、照合装置１００は、イベントパターン１４０ａに含まれる結合パターンについて、結合パターンの結合の終点となるイベントの受理時刻を当該イベントの遷移先を示す分岐ノードに対応付けて保持させる。また、照合装置１００は、複数の分岐ノードから複数の分岐ノードを結合する結合点を示す結合点ノードに接続することで、更にＮＦＡ１４０ｂを生成する。そして、照合装置１００は、結合パターンの結合の終点となるイベントが分岐ノードで受理されると、遷移元の受理状態を複製すると共に、受理されたイベントの受理時刻を分岐ノードに対応付けて保持する。また、照合装置１００は、該保持した受理時刻を該複製した受理状態と共に結合点ノードに遷移させる。また、照合装置１００は、結合点ノードにて複数の分岐ノードから遷移された受理時刻に終点となるイベントの同一の受理時刻があると、当該受理時刻を含む結合状態を更に遷移させる。このため、照合装置１００によれば、イベントパターンの結合パターンにイベント間の間隔条件があっても、イベント間の結合パターンを誤ることなく照合を行うことができるため、イベントパターンを効率的に照合することができる。
【０２１２】
［プログラムなど］
なお、照合装置１００は、既知のパーソナルコンピュータ、ワークステーションなどの情報処理装置に、上記したＮＦＡ生成部１５０ｂ、照合部１５０ｃなどの各機能を搭載することによって実現することができる。
【０２１３】
また、図示した各装置の各構成要素は、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的態様は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、ＮＦＡ生成部１５０ｂと照合部１５０ｃとを１個の部として統合しても良い。一方、ＮＦＡ生成部１５０ｂを、分岐パターンについてＮＦＡを生成する第１の生成部と結合パターンについてＮＦＡを生成する第２の生成部とに分散しても良い。また、ＮＦＡ１４０ｂなどの記憶部を照合装置１００の外部装置としてネットワーク経由で接続するようにしても良い。
【０２１４】
また、上記実施例で説明した各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。そこで、以下では、図２に示した照合装置１００と同様の機能を実現する照合プログラムを実行するコンピュータの一例を説明する。図２０は、照合プログラムを実行するコンピュータの一例を示す図である。
【０２１５】
図２０に示すように、コンピュータ２００は、各種演算処理を実行するＣＰＵ２０１と、ユーザからのデータの入力を受け付ける入力装置２０２と、ディスプレイ２０３を有する。また、コンピュータ２００は、記憶媒体からプログラム等を読取る読み取り装置２０４と、ネットワークを介して他のコンピュータとの間でデータの授受を行うインタフェース装置２０５とを有する。また、コンピュータ２００は、各種情報を一時記憶するＲＡＭ２０６と、ハードディスク装置２０７を有する。そして、各装置２０１〜２０７は、バス２０８に接続される。
【０２１６】
ハードディスク装置２０７は、ＮＦＡ生成プログラム２０７ａ、照合プログラム２０７ｂを記憶する。ＣＰＵ２０１は、各プログラム２０７ａ〜２０７ｂを読み出して、ＲＡＭ２０６に展開する。ＮＦＡ生成プログラム２０７ａは、ＮＦＡ生成プロセス２０６ａとして機能する。照合プログラム２０７ｂは、照合プロセス２０６ｂとして機能する。
【０２１７】
例えば、ＮＦＡ生成プロセス２０６ａは、ＮＦＡ生成部１５０ｂに対応する。照合プロセス２０６ｂは、照合部１５０ｃに対応する。
【０２１８】
なお、各プログラム２０７ａ〜２０７ｂについては、必ずしも最初からハードディスク装置２０７に記憶させておかなくてもよい。例えば、コンピュータ２００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に各プログラムを記憶させておく。そして、コンピュータ２００がこれらから各プログラム２０７ａ〜２０７ｂを読み出して実行するようにしても良い。
【０２１９】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０２２０】
（付記１）イベント間の発生順序と間隔条件とを伴ったイベントパターンに含まれる分岐パターンについて、前記分岐パターンの分岐の起点となるイベントの受理時刻を当該イベントの遷移先を示す起点ノードに対応付けて保持させる処理、前記起点ノードから前記分岐パターンの分岐先となるイベントおよび間隔条件を対応付けた分岐ノードに接続する処理、複数の分岐ノードから前記複数の分岐ノードを結合する結合点を示す結合点ノードに接続する処理を行うことで、オートマトンを生成するオートマトン生成部と、
複数のイベントの発生順序を含むイベントストリームと、前記オートマトンとを順次比較し、前記分岐パターンの分岐の起点となるイベントが前記起点ノードで受理されると、受理されたイベントの受理時刻を前記起点ノードに対応付けて保持し、前記分岐の起点となるイベントに後続するイベントが前記分岐ノードで受理されると、受理されたイベントの受理が前記分岐ノードに対応付けられた間隔条件を満たせば、該保持した受理時刻を前記分岐ノードの受理状態と共に遷移させ、前記結合点ノードにて複数の分岐ノードから遷移された受理時刻に同一の受理時刻があると、当該受理時刻を含む結合状態を更に遷移させることで、前記イベントストリームに前記イベントパターンが含まれているか否かを照合する照合部と
を有することを特徴とする照合装置。
【０２２１】
（付記２）前記オートマトン生成部は、前記イベントパターンに含まれる結合パターンについて、前記結合パターンの結合の終点となるイベントの受理時刻を当該イベントの遷移先を示す分岐ノードに対応付けて保持させる処理、複数の分岐ノードから前記複数の分岐ノードを結合する結合点を示す前記結合点ノードに接続する処理を行うことで、更に前記オートマトンを生成し、
前記照合部は、前記結合パターンの結合の終点となるイベントが前記分岐ノードで受理されると、遷移元の受理状態を複製すると共に、受理されたイベントの受理時刻を前記分岐ノードに対応付けて保持し、該保持した受理時刻を該複製した受理状態と共に前記結合点ノードに遷移させ、前記結合点ノードにて複数の分岐ノードから遷移された受理時刻に前記終点となるイベントの同一の受理時刻があると、当該受理時刻を含む結合状態を更に遷移させることを特徴とする付記１に記載の照合装置。
【０２２２】
（付記３）コンピュータに、
イベント間の発生順序と間隔条件とを伴ったイベントパターンに含まれる分岐パターンについて、前記分岐パターンの分岐の起点となるイベントの受理時刻を当該イベントの遷移先を示す起点ノードに対応付けて保持させる処理、前記起点ノードから前記分岐パターンの分岐先となるイベントおよび間隔条件を対応付けた分岐ノードに接続する処理、複数の分岐ノードから前記複数の分岐ノードを結合する結合点を示す結合点ノードに接続する処理を行うことで、オートマトンを生成し、
複数のイベントの発生順序を含むイベントストリームと、前記オートマトンとを順次比較し、前記分岐パターンの分岐の起点となるイベントが前記起点ノードで受理されると、受理されたイベントの受理時刻を前記起点ノードに対応付けて保持し、前記分岐の起点となるイベントに後続するイベントが前記分岐ノードで受理されると、受理されたイベントの受理が前記分岐ノードに対応付けられた間隔条件を満たせば、保持された受理時刻を前記分岐ノードの受理状態と共に遷移させ、前記結合点ノードにて複数の分岐ノードから遷移された受理時刻に同一の受理時刻があると、当該受理時刻を含む結合状態を更に遷移させることで、前記イベントストリームに前記イベントパターンが含まれているか否かを照合する
各処理を実行させることを特徴とする照合プログラム。
【０２２３】
（付記４）前記生成する処理は、前記イベントパターンに含まれる結合パターンについて、前記結合パターンの結合の終点となるイベントの受理時刻を当該イベントの遷移先を示す分岐ノードに対応付けて保持させる処理、複数の分岐ノードから前記複数の分岐ノードを結合する結合点を示す前記結合点ノードに接続する処理を行うことで、更に前記オートマトンを生成し、
前記照合する処理は、前記結合パターンの結合の終点となるイベントが前記分岐ノードで受理されると、遷移元の受理状態を複製すると共に、受理されたイベントの受理時刻を前記分岐ノードに対応付けて保持し、該保持した受理時刻を該複製した受理状態と共に前記結合点ノードに遷移させ、前記結合点ノードにて複数の分岐ノードから遷移された受理時刻に前記終点となるイベントの同一の受理時刻があると、当該受理時刻を含む結合状態を更に遷移させることを特徴とする付記１に記載の照合装置。
【符号の説明】
【０２２４】
１００    照合装置
１１０    通信部
１２０    入力部
１３０    表示部
１４０    記憶部
１５０    制御部
【図１】
0005640910.tif 000002
【図２】
0005640910.tif 000003
【図３】
0005640910.tif 000004
【図４】
0005640910.tif 000005
【図５】
0005640910.tif 000006
【図６】
0005640910.tif 000007
【図７】
0005640910.tif 000008
【図８】
0005640910.tif 000009
【図９】
0005640910.tif 000010
【図１０】
0005640910.tif 000011
【図１１】
0005640910.tif 000012
【図１２】
0005640910.tif 000013
【図１３】
0005640910.tif 000014
【図１４Ａ】
0005640910.tif 000015
【図１４Ｂ】
0005640910.tif 000016
【図１４Ｃ】
0005640910.tif 000017
【図１５Ａ】
0005640910.tif 000018
【図１５Ｂ】
0005640910.tif 000019
【図１５Ｃ】
0005640910.tif 000020
【図１５Ｄ】
0005640910.tif 000021
【図１５Ｅ】
0005640910.tif 000022
【図１６】
0005640910.tif 000023
【図１７】
0005640910.tif 000024
【図１８】
0005640910.tif 000025
【図１９Ａ】
0005640910.tif 000026
【図１９Ｂ】
0005640910.tif 000027
【図１９Ｃ】
0005640910.tif 000028
【図１９Ｄ】
0005640910.tif 000029
【図１９Ｅ】
0005640910.tif 000030
【図１９Ｆ】
0005640910.tif 000031
【図１９Ｇ】
0005640910.tif 000032
【図１９Ｈ】
0005640910.tif 000033
【図１９Ｉ】
0005640910.tif 000034
【図１９Ｊ】
0005640910.tif 000035
【図１９Ｋ】
0005640910.tif 000036
【図２０】
0005640910.tif 000037
【図２１】
0005640910.tif 000038
【図２２】
0005640910.tif 000039
【図２３】
0005640910.tif 000040