(57)【要約】【課題】複数系列からのイベントデータに対して、２つのイベント間の系列の同一性を判定する処理を高速にする。【解決手段】照合装置１００は、イベントパターン１４１に対応するオートマトンを生成し、生成したオートマトンの中のイベント同士が同系列で接続される同系列部分に対応するオートマトン部分を複数系列分複製し、複製した各オートマトン部分を各系列のイベントで受理する遷移に置き換え、置き換えた各オートマトン部分をε遷移で結合することで、ＮＦＡ１４２を生成する。そして、照合装置１００は、イベントストリーム１４３と、ＮＦＡ１４２とを比較し、イベントストリーム１４３に含まれるイベントについて、複製したそれぞれのＮＦＡ部分のうち、当該イベントが発生した系列に対応したＮＦＡ部分で受理し当該ＮＦＡ部分を動作させることで、前記イベントストリーム１４３にイベントパターン１４１が含まれているか否かを照合する。【選択図】図２
2013097570.tif 000002
【特許請求の範囲】
【請求項１】
複数系列のイベントを含むイベントパターンであってイベント間の発生順序と間隔条件とを伴ったイベントパターンについて、前記イベントパターンに対応するオートマトンを生成する処理、生成したオートマトンの中のイベント同士が同系列で接続される同系列部分に対応するオートマトン部分を複数系列分複製し、複製した各オートマトン部分を各系列のイベントで受理する遷移に置き換え、置き換えた各オートマトン部分をε遷移で結合する処理を行うことで、オートマトンを生成するオートマトン生成部と、
複数系列の複数のイベントの発生順序を含むイベントストリームと、前記オートマトンとを順次比較し、前記イベントストリームに含まれるイベントについて、前記複製したそれぞれのオートマトン部分のうち、当該イベントが発生した系列に対応したオートマトン部分で受理し当該オートマトン部分を動作させることで、前記イベントストリームに前記イベントパターンが含まれているか否かを照合する照合部と
を有することを特徴とする照合装置。
【請求項２】
前記オートマトン生成部は、イベントパターンの中に前記同系列部分とイベント同士が任意の系列で接続される任意系列部分とが接続されている場合、生成したオートマトンの中の前記同系列部分に対応するオートマトン部分を切り離し、切り離したオートマトン部分を複数系列分複製し、複製した各オートマトン部分を各系列のイベントで受理する遷移に置き換え、置き換えた各オートマトン部分と切り離す前の元のオートマトンの接合部分とをε遷移で結合し、
前記照合部は、前記イベントストリームに含まれるイベントについて、複製した各オートマトン部分では、各オートマトン部分のうち当該イベントが発生した系列に対応したオートマトン部分で受理し当該オートマトン部分を動作させ、前記任意系列部分に対応するオートマトン部分では、当該オートマトン部分で受理し当該オートマトン部分を動作させる
ことを特徴とする請求項１に記載の照合装置。
【請求項３】
コンピュータに、
複数系列のイベントを含むイベントパターンであってイベント間の発生順序と間隔条件とを伴ったイベントパターンについて、前記イベントパターンに対応するオートマトンを生成する処理、生成したオートマトンの中のイベント同士が同系列で接続される同系列部分に対応するオートマトン部分を複数系列分複製し、複製した各オートマトン部分を各系列のイベントで受理する遷移に置き換え、置き換えた各オートマトン部分をε遷移で結合する処理を行うことで、オートマトンを生成し、
複数系列の複数のイベントの発生順序を含むイベントストリームと、前記オートマトンとを順次比較し、前記イベントストリームに含まれるイベントについて、前記複製したそれぞれのオートマトン部分のうち、当該イベントが発生した系列に対応したオートマトン部分で受理し当該オートマトン部分を動作させることで、前記イベントストリームに前記イベントパターンが含まれているか否かを照合する
各処理を実行させることを特徴とする照合プログラム。
【請求項４】
コンピュータが、
複数系列のイベントを含むイベントパターンであってイベント間の発生順序と間隔条件とを伴ったイベントパターンについて、前記イベントパターンに対応するオートマトンを生成する処理、生成したオートマトンの中のイベント同士が同系列で接続される同系列部分に対応するオートマトン部分を複数系列分複製し、複製した各オートマトン部分を各系列のイベントで受理する遷移に置き換え、置き換えた各オートマトン部分をε遷移で結合する処理を行うことで、オートマトンを生成し、
複数系列の複数のイベントの発生順序を含むイベントストリームと、前記オートマトンとを順次比較し、前記イベントストリームに含まれるイベントについて、前記複製したそれぞれのオートマトン部分のうち、当該イベントが発生した系列に対応したオートマトン部分で受理し当該オートマトン部分を動作させることで、前記イベントストリームに前記イベントパターンが含まれているか否かを照合する
各処理を実行することを特徴とする照合方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、照合装置等に関する。
【背景技術】
【０００２】
ネットワーク技術やセンサー技術の発達と普及にともない、時々刻々と大量に発生するイベントの系列を、リアルタイムに処理することを目的としたイベントストリーム処理が注目されている。以下において、イベントの系列をイベントストリームと表記する。イベントストリームを処理する分野において、イベント到着順序およびイベント到着間隔のパターンを検出するイベントパターン照合技術が重要視されており、様々な手法が提案されている。
【０００３】
イベントパターン照合には、例えば、以下に示す３つの性質が求められる。１つ目の性質について説明する。イベントパターン照合では、イベントストリームの途中に混じったノイズイベントを無視して照合を行うことが求められる。ここで、ノイズイベントは、照合対象となるイベント以外のイベントに対応するものである。
【０００４】
２つ目の性質について説明する。イベントパターン照合では、あるイベントの所定時間以内に特定のイベントが到着するようなイベントパターンの照合を行うことが求められる。例えば、時間差が大きい無関係な２つのイベントの照合を避けることができる。
【０００５】
３つ目の性質について説明する。イベントパターン照合では、複数のデータソースからのイベントデータからイベントパターンの照合を行うことが求められる。例えば、任意の２台の車が同じ場所で停止していることを発見することができる。
【０００６】
次に、イベントパターンを照合する従来技術の一例について説明する。図３０は、従来技術を説明するための図である。図３０に示すように、複数のデータソースからのイベントデータを含むイベントストリーム１０は、自動車の動作において５秒ごとの速度の差分を示すイベントの列である。図３０では、各データソースをＩＤ（identification）によって識別するものとする。説明の便宜上、横列をＩＤ毎のイベントの系列とし、縦列を同じ時刻に発生したＩＤ毎のイベントとする。イベントストリーム１０内のＩＤが１のイベントの系列は、イベントａ、ｎ、ｘ、ａ、ｂ、ｘ、ｙ、ｃ、ｎ、ａ、ｎ、ｃ、ｎ・・・を含む。また、イベントストリーム１０内のＩＤが２のイベントの系列は、イベントｂ、ｃ、ｎ、ｎ、ｎ、ｎ、ｎ、ｎ、ｎ、ｚ、ｘ、ｎ、ｎ・・・を含む。また、イベントストリーム１０内のＩＤが３のイベントの系列は、イベントａ、ｚ、ｂ、ｎ、ｚ、ｎ、ｃ、ｎ、ａ、ｎ、ｚ、ｎ、ｎ・・・を含む。図３１は、イベントとイベントの説明とを対応づけた図である。図３１に示すように、イベントｚは−３０ｋｍ／ｈ以下の急減速を示し、イベントｙは−３０〜−１５ｋｍ／ｈを示し、イベントｘは−１５〜−５ｋｍ／ｈを示す。また、イベントｎは−５〜５ｋｍ／ｈを示し、イベントａは５〜１５ｋｍ／ｈを示し、イベントｂは１５〜３０ｋｍ／ｈを示し、イベントｃは３０ｋｍ／ｈ以上の急加速を示す。
【０００７】
ここでは、あるＩＤで急減速した後５秒以内に別のＩＤで急減速するイベントパターンＰを考える。急減速とは、イベントｎ、ｚの連続した発生とする。従来技術では、イベントパターンＰと図３０に示したイベントストリーム１０とを比較する。そうすると、ＩＤが３の位置１０ａで急減速であるイベントｎ、ｚが照合され、ＩＤが２の位置１０ｂで急減速であるイベントｎ、ｚが照合される。ところが、位置１０ａでイベントｎ、ｚを受信してから位置１０ｂでイベントｃを受信するまで２０秒であるので、イベントパターンＰを検出しない。また、ＩＤが２の位置１０ｂで急減速であるイベントｎ、ｚが照合され、ＩＤが３の位置１０ｃで急減速であるイベントｎ、ｚが照合される。この場合、位置１０ｂでイベントｎ、ｚを受信してから位置１０ｃでイベントｎ、ｚを受信するまで５秒であるので、イベントパターンＰを検出する。
【０００８】
ところで、従来技術では、イベントパターンとイベントストリームを比較する場合に、イベントパターンに対応する非決定性有限オートマトン（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）等の電子回路に対応する。
【００３２】
データ取得部１５１は、イベントストリーム発生装置４０から、イベントストリームを取得し、ユーザ端末５０からイベントパターンを取得する処理部である。データ取得部１５１は、イベントパターンおよびイベントストリームを、イベントパターン１４１、イベントストリーム１４３として記憶部１４０に格納する。
【００３３】
ＮＦＡ生成部１５２は、イベントパターン１４１を基にして、ＮＦＡ１４２を生成する処理部である。なお、ＮＦＡ生成部１５２は、ＴｈｏｍｐｓｏｎＮＦＡ手法を利用して、ＮＦＡを生成するが、これに限定されるものではなく、如何なる従来技術を利用してＮＦＡを生成しても良い。また、ＮＦＡ生成部１５２は、生成したＮＦＡ１４２を記憶部１４０に格納する。
【００３４】
ここで、ＮＦＡ生成部１５２のＮＦＡ構築法について説明する。図４〜図９は、ＮＦＡ生成部のＮＦＡ構築法を説明するための図である。
【００３５】
図４は、同一系列の２つのイベントにおける間隔条件付きのイベントパターンに対するＮＦＡを示す。なお、図４では、ａ、ｂはイベントを指し、ｙはイベント間隔の間隔条件を指すものとする。
【００３６】
図４の上段に示すように、イベントパターン１４１は、任意の系列でイベントｂが発生し、その後ｙ以内にｂと同じ系列でイベントｃが発生するパターンである。
【００３７】
図４の中段に示すように、ＮＦＡ生成部１５２は、イベントパターン１４１を仮のＮＦＡに変換する。かかる仮のＮＦＡを「仮ＮＦＡ」とする。ここでは、ＮＦＡ生成部１５２は、ノード１ａとノード１ｂ、ノード１ｂとノード１ｃ、ノード１ｃとノード１ｄ、ノード１ｄとノード１ｅ、ノード１ｅとノード１ｆとをそれぞれ接続する。そして、ＮＦＡ生成部１５２は、ノード１ａからノード１ｂへの遷移、ノード１ｃからノード１ｄへの遷移およびノード１ｅからノード１ｆへの遷移を「ε遷移」とする。例えば、イベントｂがノード１ａに遷移してきた場合に、ノード１ａからノード１ｂへの遷移が発動される。そして、ＮＦＡ生成部１５２は、ノード１ｄからノード１ｅへの遷移を、イベント間隔の条件を持つ遷移「ｃ：ｙ」とする。すなわち、ノード１ｄがイベントｃを受理すると、既にノード１ｄが受理したイベントｂとの間隔条件ｙを満たすとき、ノード１ｄからノード１ｅへの遷移が発動される。このように、間隔条件をチェックしたうえでノードからノードに遷移する通常遷移を「間隔条件付きの通常遷移」とする。なお、図４の例では、ノード１ｂからノード１ｃへの遷移をイベントｂに関する間隔条件付きの通常遷移「ｂ：ｘ」としている。すなわち、ノード１ｂがイベントｂを受理したとき、既にノード１ｂが受理したイベントとの間隔条件ｘを満たすとき、ノード１ｂからノード１ｃへの遷移が発動される。
【００３８】
図４の下段に示すように、ＮＦＡ生成部１５２は、仮ＮＦＡの同系列関係のＮＦＡ部分を複数系列分複製し、複製した各ＮＦＡ部分を各系列のイベントで受理する遷移に置き換え、置き換えた各ＮＦＡ部分をε遷移で結合する。ここでは、ＮＦＡ生成部１５２は、仮ＮＦＡのノード１ｂからノード１ｅまでの同系列関係のＮＦＡ部分をＮ個の複数系列分複製し、複製した各ＮＦＡ部分の遷移を各系列のイベントで受理する遷移に置き換える。また、ＮＦＡ生成部１５２は、複製した各ＮＦＡ部分をε遷移で結合する。ここでは、ＮＦＡ生成部１５２は、１系列の間隔条件付きの通常遷移を「ｂ（１）：ｘ」および「ｃ（１）：ｙ」に置き換え、Ｎ系列の間隔条件付きの通常遷移を「ｂ（Ｎ）：ｘ」および「ｃ（Ｎ）：ｙ」に置き換える。これにより、例えば、「ｃ（１）：ｙ」では、１系列のイベントｃでのみ受理され、「ｃ（Ｎ）：ｙ」では、Ｎ系列のイベントｃでのみ受理されることとなる。
【００３９】
図５は、同一系列の２つのイベントにおける間隔条件付きイベントのパターンと任意の系列のイベントとを組み合わせたイベントパターンに対するＮＦＡを示す。なお、図５では、ａ、ｂ、ｃはイベントを指し、ｘ、ｙはイベント間隔の間隔条件を指すものとする。
【００４０】
図５の上段に示すように、イベントパターン１４１は、任意の系列でイベントａが発生した後ｘ以内に任意の系列でｂが発生し、その後ｙ以内にｂと同じ系列でイベントｃが発生するパターンである。なお、イベントパターン１４１において、同系列の遷移関係を実線で表記し、任意系列の遷移関係を破線で表記するものとする。
【００４１】
図５の中段に示すように、ＮＦＡ生成部１５２は、イベントパターン１４１を仮ＮＦＡに変換する。ここでは、ＮＦＡ生成部１５２は、ノード２ａとノード２ｂ、ノード２ｂとノード２ｃ、ノード２ｃとノード２ｄ、ノード２ｄとノード２ｅ、ノード２ｅとノード２ｆ、ノード２ｆとノード２ｇとをそれぞれ接続する。また、ＮＦＡ生成部１５２は、ノード２ａからノード２ｂへの遷移を「ａ」とする。すなわち、ノード２ａがイベントａを受理すると、ノード２ａからノード２ｂへの遷移が無条件に発動される。このように、ノードからノードに無条件に遷移する通常遷移を「間隔条件なしの通常遷移」とする。また、ＮＦＡ生成部１５２は、ノード２ｂからノード２ｃへの遷移、ノード２ｄからノード２ｅへの遷移およびノード２ｆからノード２ｇへの遷移を「ε遷移」とする。また、ＮＦＡ生成部１５２は、ノード２ｃからノード２ｄへの遷移を、イベント間隔の条件を持つ遷移「ｂ：ｘ」とする。また、ＮＦＡ生成部１５２は、ノード２ｅからノード２ｆへの遷移を、イベント間隔の条件を持つ遷移「ｃ：ｙ」とする。そして、ＮＦＡ生成部１５２は、仮ＮＦＡの中の同系列関係のＮＦＡ部分を同系列関係情報として設定する。ここでは、ＮＦＡ生成部１５２は、ノード２ｃからノード２ｆまでが同系列関係のＮＦＡ部分であり、このＮＦＡ部分を同系列関係情報として設定する。
【００４２】
図５の下段に示すように、ＮＦＡ生成部１５２は、仮ＮＦＡから同系列関係のＮＦＡ部分を探索し、探索できた同系列関係のＮＦＡ部分を切り離す。そして、ＮＦＡ生成部１５２は、切り離した同系列関係のＮＦＡ部分を複数系列分複製し、複製した各ＮＦＡ部分を各系列のイベントで受理する遷移に置き換える。そして、ＮＦＡ生成部１５２は、置き換えた各ＮＦＡ部分と切り離す前の元の仮ＮＦＡの接合部分とをε遷移で結合する。ここでは、ＮＦＡ生成部１５２は、ノード２ｃからノード２ｆまでの同系列関係のＮＦＡ部分をＮ個の複数系列分複製し、複製したＮＦＡ部分の遷移を各系列のイベントで受理する遷移に置き換える。また、ＮＦＡ生成部１５２は、複製したＮＦＡ部分と切り離す前の元の仮ＮＦＡの接合部分であるノード２ｂとをそれぞれε遷移で結合する。これにより、例えば、「ｃ（１）：ｙ」では、１系列のイベントｃでのみ受理され、「ｃ（Ｎ）：ｙ」では、Ｎ系列のイベントｃでのみ受理されることとなる。また、例えば、「ａ」では、全ての系列のイベントａで受理されることとなる。
【００４３】
図６は、仮ＮＦＡにおいて同系列関係のＮＦＡ部分と任意系列関係との接合部分が同系列関係の途中に存在する場合のＮＦＡを示す。なお、図６では、ａ、ｂ、ｃ、ｄはイベントを指し、ｘ、ｙはイベント間隔の間隔条件を指すものとする。
【００４４】
図６の上段に示すように、イベントパターン１４１は、任意の系列でイベントａが発生し、その後ｘ以内にａと同じ系列でイベントｂが発生する。そして、イベントパターン１４１は、任意の系列でイベントａが発生した後ｙ以内に任意の系列でｃが発生し、その後ｚ以内にｃと同じ系列でイベントｄが発生するパターンである。
【００４５】
図６の中段に示すように、ＮＦＡ生成部１５２は、イベントパターン１４１を仮ＮＦＡに変換する。ここでは、ＮＦＡ生成部１５２は、イベントパターン１４１の中のイベントａ、ｂにおける間隔条件付きイベントのパターンについて、ノード３ｂ〜ノード３ｅで表される同系列Ａの仮ＮＦＡに変換する。また、ＮＦＡ生成部１５２は、イベントパターン１４１の中のイベントｃ、ｄにおける間隔条件付きイベントのパターンについて、ノード３ｆ〜ノード３ｉで表される同系列Ｂの仮ＮＦＡに変換する。そして、ＮＦＡ生成部１５２は、分岐の起点となるイベントａの受理時刻を当該イベントａの遷移先を示すノード３ｃに対応付けて保持させる。すなわち、ノード３ｃが同系列Ａと同系列Ｂとの接合部分である。ここで、イベントの受理時刻を保持させるノードを「受理時刻保持ノード」（起点ノードに相当）というものとする。図６の例では、受理時刻保持ノードを「＠」で示している。そして、ＮＦＡ生成部１５２は、分岐の起点となるイベントａに対応させて、受理時刻保持ノードに一意の識別子となる＠番号（ここでは「０」）を割り当てる。そして、ＮＦＡ生成部１５２は、ノード３ｃから分岐先のノード３ｆにε遷移で接続する。また、ＮＦＡ生成部１５２は、ノード３ｅおよびノード３ｉからノード３ｊへそれぞれε＝遷移で接続する。ここで、複数のノードからε＝遷移で接続されたノード、言い換えると複数のノードを結合する結合点を示すノードを「合流ノード」というものとする。図６の例では、合流ノード３ｊを「＝＠０」で示している。すなわち、ＮＦＡ生成部１５２は、合流ノード３ｊにて複数のノード３ｅ、３ｉから遷移されるイベントａの受理時刻が同じものがあるか否かを判定させるようにする。
【００４６】
図６の下段に示すように、ＮＦＡ生成部１５２は、仮ＮＦＡから同系列関係のＮＦＡ部分を探索し、探索できた同系列関係のＮＦＡ部分を切り離す。そして、ＮＦＡ生成部１５２は、切り離した同系列関係のＮＦＡ部分を複数系列分複製し、複製したそれぞれのＮＦＡ部分と任意系列関係のＮＦＡ部分との接合部分として接続ノードを生成する。そして、ＮＦＡ生成部１５２は、生成した接続ノードと複製したそれぞれのＮＦＡ部分の接合部分とをすべてε遷移で接合し、生成した接続ノードと任意系列関係のＮＦＡ部分とをε遷移で接合する。ここでは、ＮＦＡ生成部１５２は、ノード３ｂからノード３ｅまでの同系列ＡのＮＦＡ部分をＮ個の複数系列分複製する。また、ＮＦＡ生成部１５２は、ノード３ｆからノード３ｉまでの同系列ＢのＮＦＡ部分をＮ個の複数系列分複製する。そして、ＮＦＡ生成部１５２は、複製したＮＦＡ部分の遷移を各系列のイベントで受理する遷移に置き換える。また、ＮＦＡ生成部１５２は、接合部分として接続ノード３ｋを生成し、生成した接続ノード３ｋと複製したＮＦＡ部分の接合部分とをそれぞれε遷移で接合する。
【００４７】
なお、図６の下段に示した同系列ＮＦＡ変換に基づくＮＦＡは、図７で示すようなＮＦＡであっても良い。図７は、仮ＮＦＡにおいて同系列関係のＮＦＡ部分と任意系列関係との接合部分が同系列関係の途中に存在する場合のＮＦＡの変形例である。すなわち、ＮＦＡ生成部１５２は、生成した接続ノード３ｋと複製した同系列ＡのＮＦＡ部分の接合部とをすべてε遷移で接合する。そして、ＮＦＡ生成部１５２は、生成した接続ノードと複製した同系列ＢのＮＦＡ部分の接合部とをε遷移で接合する代わりに、生成した接続ノードと複製した同系列ＢのＮＦＡ部分の接合部とを間隔条件付きの遷移で直接接続する。これにより、接続ノードからのε遷移を省略できるので、接続ノードから遷移する数をＮ個から１個に削減できる。
【００４８】
図８は、先頭で２つの接続部分があるイベントパターンに対するＮＦＡを示す。なお、図８では、ａ、ｂ、ｃ、ｅはイベントを指し、ｘ、ｗ、ｚはイベント間隔の間隔条件を指すものとする。
【００４９】
図８の上段に示すように、イベントパターン１４１は、任意の系列でイベントａが発生した後ｘ以内に任意の系列でｂが発生するパターンである。そして、イベントパターン１４１は、その後ｗ以内にｂと同じ系列でイベントｅが発生するとともに、ｂと同じ系列でイベントｃが発生し、その後ｚ以内にｂと同じ系列で先のイベントｅと同じイベントｅが発生するパターンである。すなわち、イベントｅが合流部分となる。
【００５０】
図８の中段に示すように、ＮＦＡ生成部１５２は、イベントパターン１４１を仮ＮＦＡに変換する。ここでは、ＮＦＡ生成部１５２は、イベントパターン１４１の中のイベントｂ、ｃ、ｅのパターンについて、ノード４ｅ〜ノード４ｌで表される同系列の仮ＮＦＡに変換する。そして、ＮＦＡ生成部１５２は、ノード４ｋおよびノード４ｊを受理時刻保持ノードとし、イベントｅの受理時刻を、当該イベントｅのそれぞれの遷移先を示す受理時刻保持ノードに対応付けて保持させる。そして、ＮＦＡ生成部１５２は、ノード４ｋおよびノード４ｊから合流ノード４ｌへそれぞれε＝遷移で接続する。
【００５１】
図８の下段に示すように、ＮＦＡ生成部１５２は、仮ＮＦＡから同系列関係のＮＦＡ部分を探索し、探索できた同系列関係のＮＦＡ部分を切り離す。そして、ＮＦＡ生成部１５２は、切り離した同系列関係のＮＦＡ部分を複数系列分複製し、複製したそれぞれのＮＦＡ部分を各系列のイベントで受理する遷移に置き換える。そして、ＮＦＡ生成部１５２は、置き換えたそれぞれのＮＦＡ部分をε遷移で結合する。ここでは、ＮＦＡ生成部１５２は、仮ＮＦＡのノード４ｅからノード４ｌまでの同系列関係のＮＦＡ部分をＮ個の複数系列分複製し、複製したＮＦＡ部分の遷移を各系列のイベントで受理する遷移に置き換える。また、ＮＦＡ生成部１５２は、複製したＮＦＡ部分をε遷移で結合する。
【００５２】
図９は、同一系列のイベントにおけるパターンと任意系列のイベントにおけるパターンとが同じイベントで合流するイベントパターンに対するＮＦＡを示す。なお、図９では、ａ、ｂ、ｃ、ｅはイベントを指し、ｘ、ｙ、ｚはイベント間隔の間隔条件を指すものとする。
【００５３】
図９の上段に示すように、イベントパターン１４１は、同一系列でイベントａおよびイベントｃが発生し、イベントａが発生した後ｘ以内且つイベントｃが発生した後ｚ以内にこの系列でイベントｅが発生するパターンである。そして、イベントパターン１４１は、任意の系列でイベントｂが発生した後ｙ以内に先のイベントｅが発生するパターンである。
【００５４】
図９の中段に示すように、ＮＦＡ生成部１５２は、イベントパターン１４１を仮ＮＦＡに変換する。ここでは、ＮＦＡ生成部１５２は、イベントパターン１４１の中のイベントａ、ｃ、ｅのパターンについて、ノード５ｂ〜ノード５ｊで表される同系列の仮ＮＦＡに変換する。そして、ＮＦＡ生成部１５２は、ノード５ｈおよびノード５ｉを受理時刻保持ノードとし、イベントｅの受理時刻を、当該イベントｅのそれぞれの遷移先を示す受理時刻保持ノード５ｈ、５ｉに対応付けて保持させる。また、ＮＦＡ生成部１５２は、イベントパターン１４１の中のイベントｂ、ｅのパターンについて、ノード５ａ、５ｋ、５ｌ、５ｍ、５ｎで表される仮ＮＦＡに変換する。そして、ＮＦＡ生成部１５２は、ノード５ｎを受理時刻保持ノードとし、イベントｅの受理時刻を、当該イベントｅの遷移先を示す受理時刻保持ノードに対応付けて保持させる。ここで、ＮＦＡ生成部１５２は、同系列関係に隣接する合流部分を同系列関係として扱う。ここでは、ＮＦＡ生成部１５２は、同系列関係に隣接する合流部分であるノード５ｎをイベントａ、ｃ、ｅが発生した系列と同系列関係として生成する。
【００５５】
図９の下段に示すように、ＮＦＡ生成部１５２は、仮ＮＦＡから同系列関係のＮＦＡ部分を探索し、探索できた同系列関係のＮＦＡ部分を切り離す。そして、ＮＦＡ生成部１５２は、切り離した同系列関係のＮＦＡ部分を複数系列分複製し、複製したそれぞれのＮＦＡ部分を各系列のイベントで受理する遷移に置き換える。そして、ＮＦＡ生成部１５２は、置き換えたそれぞれのＮＦＡ部分をε遷移で結合する。ここでは、ＮＦＡ生成部１５２は、仮ＮＦＡのノード５ｂからノード５ｊまでの同系列関係のＮＦＡ部分をＮ個の複数系列分複製し、複製したＮＦＡ部分の遷移を各系列のイベントで受理する遷移に置き換える。また、ＮＦＡ生成部１５２は、同系列関係として扱うノード５ｎについて、ノード５ｎとε遷移で接続するノードをＮ個の複数系列分複製する。そして、ＮＦＡ生成部１５２は、複製したＮＦＡ部分をε遷移で結合する。
【００５６】
図２に戻って、照合部１５３は、ＮＦＡ１４２を利用して、イベントストリーム１４３を照合する処理部である。例えば、照合部１５３は、イベントストリーム１４３に含まれるイベントについて、ＮＦＡ１４２内の複製系列分複製された同系列関係のＮＦＡ部分では、イベントが発生した系列に対応したＮＦＡ部分で受理し、受理したＮＦＡ部分を動作させる。また、照合部１５３は、イベントストリーム１４３に含まれるイベントについて、ＮＦＡ１４２内の任意系列関係のＮＦＡ部分では、イベントが発生した系列に関係なく受理し、受理したＮＦＡ部分を動作させる。そして、照合部１５３は、照合結果をユーザ端末５０に通知する。
【００５７】
図１０に示すものは、イベントストリーム１４３に含まれるイベントがＮＦＡ１４２の各ノードから遷移する、イベントに対応する遷移種別を照合部１５３が判定する遷移種別判定テーブルのデータ構造である。なお、図１０に示すＩＤとは、系列を一意に表す識別子を指すものとする。
【００５８】
遷移種別判定テーブルは、遷移種別と、「ＩＤ指定あり遷移」と、「ＩＤ指定なし遷移」とを対応付けて記憶する。遷移種別には、間隔条件付き遷移と間隔条件なし遷移とがある。「ＩＤ指定あり遷移」は、ＮＦＡ１４２の各ノードから出ている遷移であってＩＤが指定されている遷移を意味し、入力イベントとの関係で「イベントとＩＤ一致」および「イベントとＩＤ非一致」がある。ここで、「イベントとＩＤ一致」とは、ノードから出ている遷移に係るイベントと入力イベントそのものが一致し、且つノードから出ている遷移に係るＩＤと入力イベントが発生したＩＤが一致する場合を意味する。「イベントとＩＤ非一致」とは、どちらか一方でも一致しない場合を意味する。「ＩＤ指定なし遷移」は、ＮＦＡ１４２の各ノードから出ている遷移であってＩＤが指定されていない遷移を意味する。
【００５９】
「イベントとＩＤ一致」では、ノードから出ている遷移の遷移種別が間隔条件付き遷移の場合、イベントに対応する遷移種別を当該間隔条件付き遷移と判定させる。また、ノードから出ている遷移の遷移種別が間隔条件なし遷移の場合、イベントに対応する遷移種別を当該間隔条件なし遷移と判定させる。「イベントとＩＤ非一致」では、ノードから出ている遷移の遷移種別が間隔条件付き遷移であっても間隔条件なし遷移であっても遷移なしと判定させる。「ＩＤ指定なし遷移」では、ノードから出ている遷移の遷移種別が間隔条件付き遷移の場合、イベントに対応する遷移種別を当該間隔条件付き遷移と判定させる。また、ノードから出ている遷移の遷移種別が間隔条件なし遷移の場合、イベントに対応する遷移種別を当該間隔条件なし遷移と判定させる。
【００６０】
［実施例に係るＮＦＡ生成部におけるＮＦＡ構築の処理手順］
次に、実施例に係るＮＦＡ生成部１５２におけるＮＦＡ構築の処理手順を、図１１〜図１８を参照して説明する。図１１はＮＦＡ生成部におけるＮＦＡ構築の主処理の手順を示す。図１２〜図１６はＮＦＡ生成部１５２における仮ＮＦＡ変換処理の手順を示す。図１７はＮＦＡ生成部１５２における同系列ＮＦＡ探索処理の手順を示す。図１８はＮＦＡ生成部１５２における同系列ＮＦＡ変換処理の手順を示す。
【００６１】
［ＮＦＡ構築の主処理の手順］
まず、ＮＦＡ構築の主処理の手順について、図１１を参照して説明する。図１１は、実施例に係るＮＦＡ生成部におけるＮＦＡ構築の主処理の手順を示すフローチャートである。図１１に示す処理は、例えば、イベントのパターンＰを入力とし、ＮＦＡを指すＮ（Ｐ）を出力とする。
【００６２】
まず、ＮＦＡ生成部１５２は、イベントパターンＰを仮ＮＦＡ変換し、仮ＮＦＡを指すＮ（Ｐ´）を生成する（ステップＳ１０Ａ）。
【００６３】
続いて、ＮＦＡ生成部１５２は、生成した仮ＮＦＡに未処理の同系列のＮＦＡ部分があるか否かを判定する（ステップＳ１０Ｂ）。
【００６４】
仮ＮＦＡに未処理の同系列のＮＦＡ部分があると判定した場合（ステップＳ１０Ｂ；Ｙｅｓ）、ＮＦＡ生成部１５２は、未処理の同系列のＮＦＡ部分を仮ＮＦＡから切り離す。そして、ＮＦＡ生成部１５２は、各切り離された側のノードと、生成した接続ノードをε遷移で連結し、切り離した同系列のＮＦＡ部分を同系列対応のＮＦＡに変換する。そして、ＮＦＡ生成部１５２は、各切り離した先頭ノードと、生成した接続ノードをε遷移で連結する（ステップＳ１０Ｃ）。そして、ＮＦＡ生成部１５２は、未処理の同系列のＮＦＡ部分を処理すべく、ステップＳ１０Ｂに移行する。
【００６５】
ステップＳ１０Ｂにおいて、仮ＮＦＡに未処理の同系列のＮＦＡ部分がないと判定した場合（ステップＳ１０Ｂ；Ｎｏ）、ＮＦＡ生成部１５２は、ＮＦＡ構築処理を終了する。
【００６６】
［仮ＮＦＡ変換処理の手順］
次に、図１１のステップＳ１０Ａに示した仮ＮＦＡ変換処理について、図１２〜図１６を参照して説明する。図１２〜図１６はＮＦＡ生成部１５２における仮ＮＦＡ変換処理の手順を示すフローチャートである。図１２に示す処理は、イベントのパターンＰを入力とし、仮ＮＦＡを指すＮ（Ｐ´）を出力とする。そして、ノード番号を変数ｉとし、＠番号を変数ｊとする。ここで、ノード番号とは、各ノードに割り振られるユニークな番号であり、状態番号と同じ意味を示す。状態の種類には、ノードに応じて、例えば、初期状態、最終状態がある。＠番号とは、受理時刻保持ノード（＠ノード）に対応する番号を示す。
【００６７】
まず、ＮＦＡ生成部１５２は、ノード番号を０とする初期状態のノードを生成し、生成したノードに空の「＠リスト」を登録する。そして、ＮＦＡ生成部１５２は、現ノード番号ｉの値を０に設定し、現＠番号ｊの値を０に設定する（ステップＳ１１）。なお、「＠リスト」とは、＠番号とタイムアウトの期間とを対応付けたリストである。
【００６８】
そして、ＮＦＡ生成部１５２は、入力されたパターンＰに示されたイベント（以降、「イベント受理制約」と同義）の内、イベントの前に間隔制約がないものを集め、仮のイベント集合（仮イベント集合）とする（ステップＳ１２）。なお、間隔制約とは、間隔条件と同じ意味であるものとする。
【００６９】
そして、ＮＦＡ生成部１５２は、初期状態のノードを起点ノードとして、仮イベント集合に集めたイベント受理制約について、サブルーチン処理を行なう（ステップＳ１３）。
【００７０】
その後、サブルーチン処理が終了すると、ＮＦＡ生成部１５２は、「終端ノードリスト」にノードが２つ以上あるか否かを判定する（ステップＳ１４）。なお、「終端ノードリスト」は、終端となるノードを集めたリストであり、サブルーチン処理で作成される。
【００７１】
「終端ノードリスト」にノードが２つ以上あると判定した場合（ステップＳ１４；Ｙｅｓ）、ＮＦＡ生成部１５２は、最終状態のノードを生成し、生成したノードに、現ノード番号ｉに１を加算した値を割り当てる。そして、ＮＦＡ生成部１５２は、「終端ノードリスト」に含まれるそれぞれのノードから、生成した最終状態のノードへε＝遷移で接続する（ステップＳ１５）。
【００７２】
そして、ＮＦＡ生成部１５２は、終端ノードリストに含まれる異なるノードについて、各ノードの＠リストを取り出す。そして、ＮＦＡ生成部１５２は、取り出した＠リストに存在する共通の＠番号を指定＠番号として、タイムアウトの中で一番大きいものをタイムアウト長として最終状態のノードに登録し（ステップＳ１６）、仮ＮＦＡ変換処理を終了する。
【００７３】
一方、「終端ノードリスト」にノードが２つ以上ないと判定した場合（ステップＳ１４；Ｎｏ）、ＮＦＡ生成部１５２は、終端ノードリストのノードを最終状態ノードとし（ステップＳ１７）、仮ＮＦＡ変換処理を終了する。
【００７４】
［サブルーチン処理の手順］
次に、図１２のステップＳ１３に示したサブルーチン処理について、図１３〜図１６を参照して説明する。図１３〜図１６は、サブルーチン処理の手順を示すフローチャートである。
【００７５】
ＮＦＡ生成部１５２は、起点ノードが初期状態のノードでない、且つ仮イベント集合に集めたイベント受理制約が２つ以上であるか否かを判定する（ステップＳ１３１）。起点ノードが初期状態のノードである場合、又は、起点ノードが初期状態のノードでない、且つ仮イベント集合に集めたイベント受理制約が２つ以上でない場合（ステップＳ１３１；Ｎｏ）、ＮＦＡ生成部１５２は、ステップＳ１３２に移行する。
【００７６】
ステップＳ１３２では、ＮＦＡ生成部１５２が、集めた各イベント受理制約に対応するイベントを入力するノード（以降、「イベント入力ノード」という。）を生成する。そして、ＮＦＡ生成部１５２は、現ノード番号ｉに１を加算しながら、現ノード番号ｉを生成したノードに割り当てる。そして、ＮＦＡ生成部１５２は、起点ノードから、生成したイベント入力ノードへε遷移で接続する。すなわち、ＮＦＡ生成部１５２は、起点ノードからイベント入力ノードへの遷移をε遷移とする。さらに、ＮＦＡ生成部１５２は、起点ノードの＠リストを、生成したノードの＠リストにコピーする（ステップＳ１３２）。
【００７７】
一方、起点ノードが初期状態のノードでない、且つ仮イベント集合に集めたイベント受理制約が２つ以上である場合（ステップＳ１３１；Ｙｅｓ）、ＮＦＡ生成部１５２は、ステップＳ１３３に移行する。すなわち、仮イベント集合に集めたイベント受理制約が分岐するようなパターン（分岐パターン）となるイベント受理制約である場合である。
【００７８】
ステップＳ１３３では、ＮＦＡ生成部１５２が、起点ノードに現＠番号ｊを割り当て、＠番号ｊに１を加算する（ステップＳ１３３）。すなわち、この起点ノードは、分岐の起点となるイベントの受理時刻を保持する「受理時刻保持ノード」となる。そして、ＮＦＡ生成部１５２は、起点ノードの＠リストに、割り当てた＠番号およびタイムアウト０を設定し（ステップＳ１３４）、ステップＳ１３２に移行する。
【００７９】
ステップＳ１３２の処理後、ＮＦＡ生成部１５２は、仮イベント集合に集めたイベント受理制約の中で未処理のものがあるか否かを判定する（ステップＳ１３５）。集めたイベント受理制約の中で未処理のものがない場合（ステップＳ１３５；Ｎｏ）、ＮＦＡ生成部１５２は、サブルーチン処理を終了する。
【００８０】
一方、集めたイベント受理制約の中で未処理のものがある場合（ステップＳ１３５；Ｙｅｓ）、ＮＦＡ生成部１５２は、集めたイベント受理制約から未処理のイベント受理制約を１つ取り出す（ステップＳ１３６）。
【００８１】
そして、ＮＦＡ生成部１５２は、現在のイベント受理制約に付随する前方間隔制約があるか否かを判定する（ステップＳ１３７）。現在のイベント受理制約に付随する前方の間隔制約がない場合（ステップＳ１３７；Ｎｏ）、ＮＦＡ生成部１５２は、現ノード番号ｉに１を加算し、イベント受理完了ノードを生成し、生成したノードに、加算した現ノード番号を割り当てる。そして、ＮＦＡ生成部１５２は、指定したイベントの受理によりイベント入力ノードからイベント受理完了ノードに遷移するエッジで接続する。すなわち、ＮＦＡ生成部１５２は、イベント入力ノードからイベント受理完了ノードへの遷移を「間隔条件なしの通常遷移」とする。さらに、ＮＦＡ生成部１５２は、イベント入力ノードの＠リストをイベント受理完了ノードの＠リストにコピーする（ステップＳ１３８）。その後、ＮＦＡ生成部１５２は、ステップＳ１４３に移行する。
【００８２】
一方、現在のイベント受理制約に付随する前方間隔制約がある場合（ステップＳ１３７；Ｙｅｓ）、ＮＦＡ生成部１５２は、現ノード番号ｉに１を加算し、イベント受理完了ノードを生成し、生成したノードに、加算した現ノード番号を割り当てる。そして、ＮＦＡ生成部１５２は、前方間隔制約を満たすイベントの受理で、イベント入力ノードからイベント受理完了ノードに遷移するエッジで接続する。すなわち、ＮＦＡ生成部１５２は、イベント入力ノードからイベント受理完了ノードへの遷移を「間隔条件付きの通常遷移」とする。さらに、ＮＦＡ生成部１５２は、イベント入力ノードの＠リストの各タイムアウトに前方間隔制約を加えてから、生成したイベント受理完了ノードの＠リストにコピーする（ステップＳ１３９）。その後、ＮＦＡ生成部１５２は、ステップＳ１４１に移行する。
【００８３】
ステップＳ１４１では、ＮＦＡ生成部１５２は、現在のイベント受理制約に付随する前方間隔制約の種別が同系列関係であるか否かを判定する（ステップＳ１４１）。現在のイベント受理制約に付随する前方間隔制約の種別が同系列関係であると判定した場合（ステップＳ１４１；Ｙｅｓ）、ＮＦＡ生成部１５２は、イベント入力ノードに同系列関係情報を付加し（ステップＳ１４２）、ステップＳ１４３に移行する。一方、現在のイベント受理制約に付随する前方間隔制約の種別が同系列関係でないと判定した場合（ステップＳ１４１；Ｎｏ）、ＮＦＡ生成部１５２は、ステップＳ１４３に移行する。
【００８４】
ステップＳ１４３では、ＮＦＡ生成部１５２は、現在のイベント受理制約の後方間隔制約の中で同系列関係のものがあるか否かを判定する（ステップＳ１４３）。現在のイベント受理制約の後方間隔制約の中で同系列関係のものがあると判定した場合（ステップＳ１４３；Ｙｅｓ）、ＮＦＡ生成部１５２は、イベント受理完了ノードに同系列関係情報を付加し（ステップＳ１４４）、ステップＳ１５１に移行する。一方、現在のイベント受理制約の後方間隔制約の中で同系列関係のものがないと判定した場合（ステップＳ１４３；Ｎｏ）、ＮＦＡ生成部１５２は、ステップＳ１５１に移行する。
【００８５】
続いて、ＮＦＡ生成部１５２は、現在のイベント受理制約の前方間隔制約の数をＦに設定する（ステップＳ１５１）。そして、ＮＦＡ生成部１５２は、Ｆの値が２以上であるか否かを判定する（ステップＳ１５２）。Ｆの値が２以上でない場合（ステップＳ１５２；Ｎｏ）、ＮＦＡ生成部１５２は、生成したイベント受理完了ノードを完了ノードとする（ステップＳ１５３）。その後、ＮＦＡ生成部１５２は、現在のイベント受理制約の後方間隔制約における処理を行うべく、ステップＳ１６１に移行する。
【００８６】
一方、Ｆの値が２以上である場合（ステップＳ１５２；Ｙｅｓ）、ＮＦＡ生成部１５２は、現在のイベント受理制約に対応する生成済みのイベント受理完了ノードの数がＦの値と一致するか否かを判定する（ステップＳ１５４）。現在のイベント受理制約に対応する生成済みのイベント受理完了ノードの数がＦの値と一致しない場合（ステップＳ１５４；Ｎｏ）、ＮＦＡ生成部１５２は、集めたイベント受理制約の中で未処理のイベント受理制約の処理をすべく、ステップＳ１３５に移行する。
【００８７】
一方、現在のイベント受理制約に対応する生成済みのイベント受理完了の数がＦの値と一致する場合（ステップＳ１５４；Ｙｅｓ）、ＮＦＡ生成部１５２は、現ノード番号ｉに１を加算し、現在のイベント受理制約に対応する合流ノードを生成する。そして、ＮＦＡ生成部１５２は、現在のイベント受理制約に対応する生成済みの全てのイベント受理完了ノードから、生成した合流ノードへε＝遷移で接続する（ステップＳ１５５）。すなわち、ＮＦＡ生成部１５２は、イベント受理完了ノードから合流ノードへの遷移を「ε＝遷移」とする。
【００８８】
そして、ＮＦＡ生成部１５２は、合流ノードに同系列関係情報を付加する（ステップＳ１５６）。
【００８９】
続いて、ＮＦＡ生成部１５２は、現在の＠番号ｊおよびタイムアウト０を現在のイベント受理制約に対応する生成済みの全てのイベント受理完了ノードに割り当て、それぞれの＠リストに追加する。すなわち、これら生成済みの全てのイベント受理完了ノードは、イベントの受理時刻を保持する「受理時刻保持ノード」となる。さらに、ＮＦＡ生成部１５２は、は、＠番号ｊに１を加算する（ステップＳ１５７）。
【００９０】
続いて、ＮＦＡ生成部１５２は、現在のイベント受理制約に対応する生成済みのイベント受理完了ノードの＠リストにおいて、複数の生成済みのイベント受理完了ノードが持っている同一の＠番号を合流ノードの指定＠番号とする。そして、ＮＦＡ生成部１５２は、タイムアウトの中で一番大きい値をタイムアウト長として、＠番号とともに合流ノードに対応付けて登録する（ステップＳ１５８）。
【００９１】
続いて、ＮＦＡ生成部１５２は、現在のイベント受理制約に対応する生成済みのイベント受理完了ノードの＠リストに含まれる＠番号および各＠番号で最大のタイムアウトを重複なく合流ノードの＠リストに設定する（ステップＳ１５９）。そして、ＮＦＡ生成部１５２は、合流ノードを完了ノードとし（ステップＳ１６０）、現在のイベント受理制約の後方間隔制約における処理を行うべく、ステップＳ１６１に移行する。
【００９２】
ステップＳ１６１では、ＮＦＡ生成部１５２が、ステップＳ１３６で取り出したイベント受理制約の後方への間隔制約を持つイベント受理制約を、前方間隔制約と前方間隔制約の種別と共に集め、仮イベント集合とする（ステップＳ１６１）。そして、ＮＦＡ生成部１５２は、仮イベント集合に集めたイベント受理制約が１つ以上であるか否かを判定する（ステップＳ１６２）。集めたイベント受理制約が１つ以上でない場合、すなわち０である場合（ステップＳ１６２；Ｎｏ）、ＮＦＡ生成部１５２は、終端ノードリストに完了ノードを追加する（ステップＳ１６３）。その後、ＮＦＡ生成部１５２は、集めたイベント受理制約の中で未処理のイベント受理制約の処理をすべく、ステップＳ１３５に移行する。
【００９３】
一方、集めたイベント受理制約が１つ以上である場合（ステップＳ１６２；Ｙｅｓ）、ＮＦＡ生成部１５２は、完了ノードを起点ノードとして、仮イベント集合に集めたイベント受理制約について、サブルーチン処理を再帰的に行う（ステップＳ１６４）。その後、ＮＦＡ生成部１５２は、集めたイベント受理制約の中で未処理のイベント受理制約の処理をすべく、ステップＳ１３５に移行する。
【００９４】
［同系列ＮＦＡ探索処理の手順］
次に、図１１のステップＳ１０Ｂに示した同系列ＮＦＡ探索処理について、図１７を参照して説明する。図１７は、同系列ＮＦＡ探索処理の手順を示すフローチャートである。図１７に示す処理は、仮ＮＦＡを指すＮ（Ｐ´）を入力とし、仮ＮＦＡにおいて同系列関係を有するＮＦＡ部分のノードの集合（同系列ノード集合）の組を出力とする。
【００９５】
ＮＦＡ生成部１５２は、入力された仮ＮＦＡの初期状態のノードを現在のノードとする（ステップＳ２１）。そして、ＮＦＡ生成部１５２は、現在のノードと接続する未処理の遷移があるか否かを判定する（ステップＳ２２）。現在ノードと接続する未処理の遷移があると判定した場合（ステップＳ２２；Ｙｅｓ）、ＮＦＡ生成部１５２は、あると判定した未処理の遷移がε遷移であるか否かを判定する（ステップＳ２３）。未処理の遷移がε遷移であると判定した場合（ステップＳ２３；Ｙｅｓ）、ＮＦＡ生成部１５２は、現在のノードと遷移先・遷移元ノードがともに同系列関係であるか否かを判定する（ステップＳ２４）。一方、未処理の遷移がε遷移でないと判定した場合（ステップＳ２３；Ｎｏ）、ＮＦＡ生成部１５２は、現在のノードあるいは遷移先・遷移元ノードが同系列関係であるか否かを判定する（ステップＳ２５）。
【００９６】
現在のノードと遷移先・遷移元ノードがともに同系列関係である場合（ステップＳ２４；Ｙｅｓ）、またはどちらか一方が同系列関係である場合（ステップＳ２５；Ｙｅｓ）、ＮＦＡ生成部１５２は、次の処理を行う。ＮＦＡ生成部１５２は、現在のノードと遷移先・遷移元ノードを同系列ノード集合に追加する（ステップＳ２６）。一方、現在のノードと遷移先・遷移元ノードがともに同系列関係でない場合（ステップＳ２４；Ｎｏ）、またはどちらも同系列関係でない場合（ステップＳ２５：Ｎｏ）、ＮＦＡ生成部１５２は、遷移先・遷移元ノードを未処理ノード集合に追加する（ステップＳ２７）。そして、ＮＦＡ生成部１５２は、現在のノードと接続する未処理の遷移について処理すべく、ステップＳ２２に移行する。
【００９７】
ステップＳ２２では、現在ノードと接続する未処理の遷移がないと判定した場合（ステップＳ２２；Ｎｏ）、ＮＦＡ生成部１５２は、同系列ノード集合に含まれるノードをすべて処理したか否かを判定する（ステップＳ２８）。同系列ノード集合に含まれるノードをすべて処理していないと判定した場合（ステップＳ２８；Ｎｏ）、ＮＦＡ生成部１５２は、同系列ノード集合の中で未処理のノードの１つを現在のノードとする（ステップＳ３０）。そして、ＮＦＡ生成部１５２は、ステップＳ２２に移行する。
【００９８】
一方、同系列ノード集合に含まれるノードをすべて処理したと判定した場合（ステップＳ２８；Ｙｅｓ）、ＮＦＡ生成部１５２は、同系列ノード集合を出力し、出力後同系列ノード集合を空にする（ステップＳ２９）。そして、ＮＦＡ生成部１５２は、未処理ノード集合の中に最終状態ノードを除く未処理のノードがあるか否かを判定する（ステップＳ３１）。未処理ノード集合に最終状態ノードを除く未処理のノードがある場合（ステップＳ３１；Ｙｅｓ）、ＮＦＡ生成部１５２は、未処理ノード集合の中の最終状態ノードを除く系列（ＩＤ）の一番小さい未処理のノードを現在のノードとする（ステップＳ３２）。そして、ＮＦＡ生成部１５２は、ステップＳ２２に移行する。
【００９９】
一方、未処理ノード集合に最終状態ノードを除く未処理のノードがない場合（ステップＳ３１；Ｎｏ）、ＮＦＡ生成部１５２は、同系列ＮＦＡ探索処理を終了する。
【０１００】
［同系列ＮＦＡ変換処理の手順］
次に、図１１のステップＳ１０Ｃに示した同系列ＮＦＡ変換処理について、図１８を参照して説明する。図１８は、同系列ＮＦＡ変換処理の手順を示すフローチャートである。図１８に示す処理は、仮ＮＦＡを指すＮ（Ｐ´）および同系列ノード集合の組を入力とし、ＮＦＡを指すＮ（Ｐ）を出力とする。
【０１０１】
ＮＦＡ生成部１５２は、入力された同系列ノード集合の組が空であるか否かを判定する（ステップＳ４１）。同系列ノード集合の組が空でないと判定した場合（ステップＳ４１；Ｎｏ）、ＮＦＡ生成部１５２は、同系列ノード集合の組から同系列ノード集合を１つ取り出す（ステップＳ４２）。
【０１０２】
そして、ＮＦＡ生成部１５２は、同系列ノード集合に未処理のノードがあるか否かを判定する（ステップＳ４３）。同系列ノード集合に未処理のノードがあると判定した場合（ステップＳ４３；Ｙｅｓ）、ＮＦＡ生成部１５２は、同系列ノード集合の未処理の１ノードを現在のノードとする（ステップＳ４４）。そして、ＮＦＡ生成部１５２は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがあるか否かを判定する（ステップＳ４５）。
【０１０３】
現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがあると判定した場合（ステップＳ４５；Ｙｅｓ）、ＮＦＡ生成部１５２は、新しいノードを生成し、現在のノードの代わりに、生成したノードと先の同系列ノード集合にないノードとをそのままの遷移制約等で接続する。そして、ＮＦＡ生成部１５２は、現在のノードと生成したノードとこれら２つのノードの遷移方向の組とを、同系列の部分と同系列でない部分とが切り離された境界のノードの組を集めた境界ノード組集合に加える（ステップＳ４６）。ここで、ＮＦＡ生成部１５２は、現在のノードの代わりに生成したノードが現在のノードの前方にある場合には、該生成したノードから現在のノードへの遷移方向とする。一方、ＮＦＡ生成部１５２は、現在のノードの代わりに生成したノードが現在のノードの後方にある場合には、現在のノードから該生成したノードへの遷移方向とする。そして、ＮＦＡ生成部１５２は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のノードを判定すべく、ステップＳ４５に移行する。
【０１０４】
一方、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがないと判定した場合（ステップＳ４５；Ｎｏ）、ＮＦＡ生成部１５２は、同系列ノード集合の未処理のノードを判定すべく、ステップＳ４３に移行する。
【０１０５】
一方、同系列ノード集合に未処理のノードがないと判定した場合（ステップＳ４３；Ｎｏ）、ＮＦＡ生成部１５２は、同系列ノード集合のノードおよびそのノード間の遷移エッジすべてを１セットとして、系列数分だけ複製する。そして、ＮＦＡ生成部１５２は、各系列のイベントで受理する遷移に置き換える（ステップＳ４７）。すなわち、ＮＦＡ生成部１５２は、間隔条件付きの通常遷移および間隔条件なしの通常遷移を各系列のイベントでのみ受理されるように置き換える。
【０１０６】
続いて、ＮＦＡ生成部１５２は、境界ノード組集合に未処理の組があるか否かを判定する（ステップＳ４８）。境界ノード組集合に未処理の組があると判定した場合（ステップＳ４８；Ｙｅｓ）、ＮＦＡ生成部１５２は、境界ノード組集合から未処理の１組を取り出す（ステップＳ４９）。そして、ＮＦＡ生成部１５２は、取り出した１組の現在のノードと生成ノードと遷移方向とに従い、現在のノードに対応する複製したすべてのノードと生成ノードとを遷移方向どおりにすべてε遷移で接続する（ステップＳ５０）。そして、ＮＦＡ生成部１５２は、境界ノード組集合に未処理の組があるか否かを判定すべく、ステップＳ４８に移行する。
【０１０７】
一方、境界ノード組集合に未処理の組がないと判定した場合（ステップＳ４８；Ｎｏ）、ＮＦＡ生成部１５２は、次の同系列ノード集合の処理をすべく、ステップＳ４１に移行する。
【０１０８】
ステップＳ４１では、同系列ノード集合の組が空であると判定した場合（ステップＳ４１；Ｙｅｓ）、ＮＦＡ生成部１５２は、以下のようにノード番号を振りなおす。すなわち、ＮＦＡ生成部１５２は、系列（ＩＤ）の大小関係を保ちつつ、境界ノード組集合の遷移元が小さいノード番号となるように、一意なノード番号を振りなおす（ステップＳ５１）。そして、ＮＦＡ生成部１５２は、同系列ＮＦＡ変換処理を終了する。
【０１０９】
［ＮＦＡを生成する処理の一例］
次に、あるパターンをイベントパターン１４１とした場合に、図１１〜図１８に示したＮＦＡの構築法を用いて、ＮＦＡ生成部１５２が、イベントパターン１４１からＮＦＡ１４２を生成する処理の一例について説明する。図１９Ａ〜図１９Ｄは、仮ＮＦＡを生成する処理を説明する図である。図２０Ａ〜図２０Ｆは、同系列のＮＦＡを探索する処理を説明する図である。図２１Ａ〜図２１Ｇは、同系列のＮＦＡを変換する処理を説明する図である。
【０１１０】
［仮ＮＦＡ生成処理の説明］
図１９Ａに示すように、イベントパターン１４１のデータ構造を、符号２０１ｐに示すものとする。イベントパターン１４１は、任意の系列でイベントＡが発生し、その後２以内にＡと同じ系列でイベントＢが発生する。そして、イベントパターン１４１は、任意の系列でイベントＡが発生した後５以内に任意の系列でＣが発生するパターンである。
【０１１１】
図１９Ｂの１段目に示すように、ＮＦＡ生成部１５２は、ノード番号を０とする初期状態のノード６ａを生成し、生成したノード６ａに空の＠リストを登録する。そして、ＮＦＡ生成部１５２は、現ノード番号ｉの値を０に設定し、現＠番号ｊの値を０に設定する。そして、ＮＦＡ生成部１５２は、入力されたイベントパターン１４１に示されたイベント受理制約の内、前に間隔制約がないものを集め、仮イベント集合とする。ここでは、ＮＦＡ生成部１５２は、イベントＡのイベント受理制約を仮イベント集合とする。そして、ＮＦＡ生成部１５２は、初期状態のノード６ａを起点ノードとする。
【０１１２】
図１９Ｂの２段目に示すように、ＮＦＡ生成部１５２は、起点ノードが初期状態のノード６ａであるので、仮イベント集合に集められたイベント受理制約（Ａ）に対応するイベント入力ノード６ｂを生成する。そして、ＮＦＡ生成部１５２は、生成したノード６ｂに現ノード番号ｉに１を加算した値１を割り当てる。そして、ＮＦＡ生成部１５２は、起点ノード６ａからイベント入力ノード６ｂへε遷移で接続する。
【０１１３】
図１９Ｂの３段目に示すように、ＮＦＡ生成部１５２は、仮イベント集合に集められたイベント受理制約（Ａ）から未処理のイベント受理制約を１つ取り出す。ここでは、ＮＦＡ生成部１５２はイベントＡを取り出す。そして、ＮＦＡ生成部１５２は、イベント受理完了ノード６ｃを生成し、生成したノード６ｃに、現ノード番号ｉに１を加算した値２を割り当てる。そして、ＮＦＡ生成部１５２は、イベントＡの受理によりイベント入力ノード６ｂからイベント受理完了ノード６ｃに遷移するエッジで接続する。すなわち、イベント入力ノード６ｂからイベント受理完了ノード６ｃへの遷移が「間隔条件なしの通常遷移」となる。さらに、ＮＦＡ生成部１５２は、イベント入力ノード６ｂの＠リストをイベント受理完了ノード６ｃの＠リストにコピーする。
【０１１４】
図１９Ｂの４段目に示すように、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ａ）の後方間隔制約の中で同系列関係のものＢがあるので、イベント受理完了ノード６ｃに同系列関係情報「＝」を付加する。
【０１１５】
続いて、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ａ）の前方の間隔制約の数をＦとする。ここでは、ＮＦＡ生成部１５２は、イベントＡの前方の間隔に制約がないので、Ｆを０に設定する。そして、ＮＦＡ生成部１５２は、Ｆが２以上でないので、イベント受理完了ノード６ｃを完了ノードとする。さらに、ＮＦＡ生成部１５２は、取り出したイベント受理制約（Ａ）の後方への間隔制約を持つイベント受理制約を前方間隔制約と前方間隔制約種別と共に集め、仮イベント集合とする。前方間隔制約種別とは、前方間隔制約に付随する種別であって同系列の遷移関係か任意系列の遷移関係かを区別する種別である。ここでは、ＮＦＡ生成部１５２は、イベントＡの後方イベントＢまでの間隔制約が２であり、同系列の遷移関係であるので、イベント受理制約Ｂを前方間隔制約２と同系列の遷移関係の制約であることを示す種別と共に仮イベント集合に設定する。また、ＮＦＡ生成部１５２は、イベントＡの後方イベントＣまでの間隔制約が５であり、任意系列の遷移関係であるので、イベント受理制約Ｃを前方間隔制約５と任意系列の遷移関係の制約であることを示す種別と共に仮イベント集合に設定する。そして、ＮＦＡ生成部１５２は、完了ノード６ｃを起点ノードとする。
【０１１６】
図１９Ｃの１段目に示すように、ＮＦＡ生成部１５２は、起点ノード６ｃが初期状態のノードでなく、且つ仮イベント集合に集められたイベント受理制約（Ｂ、Ｃ）が２つ以上であるので、起点ノード６ｃに現＠番号ｊの値０を割り当てる。すなわち、この起点ノード６ｃは、＠番号０（＠０）を有する受理時刻保持ノードとなる。そして、ＮＦＡ生成部１５２は、現＠番号ｊの値を、１加算した値１に設定する。
【０１１７】
図１９Ｃの２段目に示すように、ＮＦＡ生成部１５２は、起点ノード６ｃの＠リスト１ｍに、割り当てた＠番号０およびタイムアウト０を設定する。
【０１１８】
図１９Ｃの３段目に示すように、ＮＦＡ生成部１５２は、仮イベント集合に集められたイベント受理制約（Ｂ、Ｃ）に対応するイベント入力ノード６ｄ、６ｅを生成する。そして、ＮＦＡ生成部１５２は、生成したノード６ｄに現ノード番号ｉ（２）に１を加算した値３を割り当て、生成したノード６ｅにさらに現ノード番号ｉ（３）に１を加算した値４を割り当てる。そして、ＮＦＡ生成部１５２は、起点ノード６ｃからイベント入力ノード６ｄへε遷移で接続し、起点ノード６ｃからイベント入力ノード６ｅへε遷移で接続する。そして、ＮＦＡ生成部１５２は、起点ノード６ｃの＠リストをイベント入力ノード６ｄ、６ｅのそれぞれの＠リストにコピーする。
【０１１９】
図１９Ｃの４段目に示すように、ＮＦＡ生成部１５２は、仮イベント集合に集められたイベント受理制約（Ｂ、Ｃ）から未処理のイベント受理制約を１つ取り出す。ここでは、ＮＦＡ生成部１５２はイベントＢを取り出す。そして、ＮＦＡ生成部１５２は、イベント受理完了ノード６ｆを生成し、生成したノード６ｆに、現ノード番号ｉに１を加算した値５を割り当てる。そして、ＮＦＡ生成部１５２は、前方間隔制約２を満たすイベントＢの受理によりイベント入力ノード６ｄからイベント受理完了ノード６ｆに遷移するエッジで接続する。すなわち、イベント入力ノード６ｄからイベント受理完了ノード６ｆへの遷移が「間隔条件付きの通常遷移」となる。さらに、ＮＦＡ生成部１５２は、イベント入力ノード６ｄの＠リストのタイムアウトに前方間隔制約２を加えてからイベント受理完了ノード６ｆの＠リストにコピーする。
【０１２０】
図１９Ｃの５段目に示すように、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ｂ）に付随する前方間隔制約種別が同系列関係であるので、イベント入力ノード６ｄに同系列関係情報「＝」を付加する。
【０１２１】
続いて、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ｂ）の前方の間隔制約の数をＦとする。ここでは、イベントＢの前方間隔制約は２のものだけであるので、ＮＦＡ生成部１５２は、前方の間隔制約の数Ｆを１に設定する。そして、ＮＦＡ生成部１５２は、Ｆが２以上でないので、イベント受理完了ノード６ｆを完了ノードとする。さらに、ＮＦＡ生成部１５２は、取り出したイベント受理制約（Ｂ）の後方への間隔制約を持つイベント受理制約を集め、仮イベント集合とする。ここでは、ＮＦＡ生成部１５２は、イベントＢの後方への間隔制約を持つイベント受理制約がないので、空の仮イベント集合とする。そして、ＮＦＡ生成部１５２は、仮イベント集合が空なので、終端ノードリストに完了ノード６ｆを追加する。ここで、イベント受理制約Ｂの処理が終了する。
【０１２２】
図１９Ｄの１段目に示すように、ＮＦＡ生成部１５２は、仮イベント集合に集められたイベント受理制約（Ｂ、Ｃ）から未処理のイベント受理制約を１つ取り出す。ここでは、ＮＦＡ生成部１５２は、イベントＢの処理が終了しているので、未処理のイベントＣを取り出す。そして、ＮＦＡ生成部１５２は、イベント受理完了ノード６ｇを生成し、生成したノード６ｇに、現ノード番号ｉに１を加算した値６を割り当てる。そして、ＮＦＡ生成部１５２は、前方間隔制約５を満たすイベントＣの受理によりイベント入力ノード６ｅからイベント受理完了ノード６ｇに遷移するエッジで接続する。すなわち、イベント入力ノード６ｅからイベント受理完了ノード６ｇへの遷移が「間隔条件付きの通常遷移」となる。さらに、ＮＦＡ生成部１５２は、イベント入力ノード６ｅの＠リストのタイムアウトに前方間隔制約５を加えてからイベント受理完了ノード６ｇの＠リストにコピーする。
【０１２３】
続いて、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ｃ）もイベントＢと同様に、前方の間隔制約の数が１つで、後方の間隔制約がないので、終端ノードリストに完了ノード６ｇを追加する。すなわち、終端ノードリストには、完了ノード６ｆ、６ｇがある。ここで、イベント受理制約Ｃの処理が終了する。この結果、イベント受理制約Ａの処理が終了する。
【０１２４】
続いて、ＮＦＡ生成部１５２は、仮イベント集合に集められたイベント受理制約（Ｂ、Ｃ）の処理が終了したので、元の仮イベント集合および元の起点ノードに戻す。すなわち、起点ノードは初期状態のノード６ａとなり、仮イベント集合はイベント受理制約Ａを含んだものになる。
【０１２５】
図１９Ｄの２段目に示すように、ＮＦＡ生成部１５２は、戻した仮イベント集合に含まれるイベント受理制約Ａの処理を終了しているので、最終状態のノード６ｈを生成し、生成したノード６ｈに、現ノード番号ｉに１を加算した値７を割り当てる。そして、ＮＦＡ生成部１５２は、終端ノードリストに含まれるそれぞれの完了ノード６ｆ、６ｇから、生成した最終状態のノード６ｈへε＝遷移で接続する。
【０１２６】
図１９Ｄの５段目に示すように、ＮＦＡ生成部１５２は、終端ノードリストに含まれる異なるノードについて、各ノードの＠リストを取り出す。ここでは、ＮＦＡ生成部１５２は、終端ノードリストに含まれる完了ノード６ｆ、６ｇの＠リストを取り出す。そして、ＮＦＡ生成部１５２は、取り出した＠リストに存在する共通の＠番号を指定＠番号として、タイムアウトの中で一番大きいものをタイムアウト長として最終状態のノード６ｈに登録する。ここでは、完了ノード６ｆの＠リストには、＠番号０とタイムアウト長２とが対応付けられ、完了ノード６ｇの＠リストには、＠番号０とタイムアウト長５とが対応付けられている。このため、ＮＦＡ生成部１５２は、指定＠番号を０として、タイムアウト長を５として最終状態のノード６ｈに登録する。
【０１２７】
上述したように、ＮＦＡ生成部１５２は、図１９Ａ〜図１９Ｄに示す処理を実行することで、図１９Ａに示すイベントパターン１４１から仮ＮＦＡを生成する。
【０１２８】
［同系列ＮＦＡ探索処理の説明］
次に、同系列ＮＦＡ探索処理について説明する。図２０Ａの１段目に示すように、ＮＦＡ生成部１５２は、生成した仮ＮＦＡの初期状態ノード６ａを現在のノードとする。また、ＮＦＡ生成部１５２は、未処理ノード集合および同系列ノード集合を空にする。ここで、未処理ノード集合とは、各ノードの遷移について同系列関係であるか否かの探索処理が行われていないノードの集合を意味する。同系列ノード集合とは、同系列関係のノードの集合を意味する。
【０１２９】
図２０Ａの２段目に示すように、ＮＦＡ生成部１５２は、現在のノード６ａと接続する未処理の遷移がε遷移であるので、現在のノード６ａと遷移先のノード６ｂがともに同系列関係であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノード６ａと遷移先のノード６ｂがともに同系列関係情報「＝」が付加されていないので、同系列関係で無いと判定する。そして、ＮＦＡ生成部１５２は、遷移先のノード６ｂを未処理ノード集合に追加する。
【０１３０】
図２０Ａの３段目に示すように、ＮＦＡ生成部１５２は、現在のノード６ａと接続する未処理の遷移がなく、同系列ノード集合に含まれるノードが空であるので、同系列ノード集合を出力しない。
【０１３１】
図２０Ｂの１段目に示すように、ＮＦＡ生成部１５２は、未処理ノード集合の中の最終状態ノードを除くノード番号の一番小さい未処理のノードを現在のノードとする。ここでは、ＮＦＡ生成部１５２は、未処理ノード集合の中のノード番号１のノード６ｂを現在のノードとする。
【０１３２】
図２０Ｂの２段目に示すように、ＮＦＡ生成部１５２は、現在のノード６ａと接続する未処理の遷移が間隔条件なしの通常遷移であるので、現在のノード６ｂあるいは遷移先のノード６ｃが同系列関係であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、遷移先のノード６ｃが同系列関係情報「＝」が付加されているので、同系列関係であると判定する。そして、ＮＦＡ生成部１５２は、現在のノード６ｂと遷移先のノード６ｃを同系列ノード集合に追加する。
【０１３３】
図２０Ｂの３段目に示すように、ＮＦＡ生成部１５２は、現在のノード６ａと接続する未処理の遷移がないので、同系列ノード集合に含まれるノードがすべて処理したか否かを判定する。そして、ＮＦＡ生成部１５２は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号２のノード６ｃを現在のノードとする。
【０１３４】
図２０Ｃの１段目に示すように、ＮＦＡ生成部１５２は、現在のノード６ｃと接続する未処理の遷移がε遷移であるので、現在のノード６ｃと遷移先のノードがともに同系列関係であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノード６ｃと遷移先のノード６ｄがともに同系列関係情報「＝」が付加されているので、同系列関係であると判定する。そして、ＮＦＡ生成部１５２は、現在のノード６ｃと遷移先のノード６ｄを同系列ノード集合に追加する。また、ＮＦＡ生成部１５２は、現在のノード６ｃには同系列関係情報「＝」が付加されているが、遷移先のノード６ｅには付加されていないので、遷移先のノード６ｅを未処理ノード集合に追加する。
【０１３５】
図２０Ｃの２段目に示すように、ＮＦＡ生成部１５２は、現在のノード６ｃと接続する未処理の遷移がないので、同系列ノード集合に含まれるノードがすべて処理したか否かを判定する。そして、ＮＦＡ生成部１５２は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号３のノード６ｄを現在のノードとする。
【０１３６】
図２０Ｃの３段目に示すように、ＮＦＡ生成部１５２は、現在のノード６ｄと接続する未処理の遷移が間隔条件付きの通常遷移であるので、現在のノード６ｄあるいは遷移先のノード６ｆが同系列関係であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノード６ｄが同系列関係情報「＝」が付加されているので、同系列関係であると判定する。そして、ＮＦＡ生成部１５２は、現在のノード６ｄと遷移先のノード６ｆを同系列ノード集合に追加する。
【０１３７】
図２０Ｄの１段目に示すように、ＮＦＡ生成部１５２は、現在のノード６ｄと接続する未処理の遷移がないので、同系列ノード集合に含まれるノードがすべて処理したか否かを判定する。そして、ＮＦＡ生成部１５２は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号５のノード６ｆを現在のノードとする。
【０１３８】
図２０Ｄの２段目に示すように、ＮＦＡ生成部１５２は、現在のノード６ｆと接続する未処理の遷移がε遷移でないので、現在のノード６ｆあるいは遷移先のノードが同系列関係であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノード６ｆと遷移先のノード６ｈがどちらにも同系列関係情報「＝」が付加されていない。そこで、ＮＦＡ生成部１５２は、同系列関係でないと判定し、遷移先のノード６ｈを未処理ノード集合に追加する。
【０１３９】
図２０Ｄの３段目に示すように、ＮＦＡ生成部１５２は、現在のノード６ｆと接続する未処理の遷移がなく、同系列ノード集合に含まれるノードが空であるので、同系列ノード集合を出力する。ここでは、ＮＦＡ生成部１５２は、ノード番号１、２、３、５のノードを同系列ノード集合として出力する。そして、ＮＦＡ生成部１５２は、出力後、同系列ノード集合を空にする。
【０１４０】
図２０Ｅの１段目に示すように、ＮＦＡ生成部１５２は、未処理ノード集合の中の最終状態ノードを除くノード番号の一番小さい未処理のノードを現在のノードとする。ここでは、ＮＦＡ生成部１５２は、未処理ノード集合の中のノード番号４のノード６ｂを現在のノードとする。
【０１４１】
図２０Ｅの２段目に示すように、ＮＦＡ生成部１５２は、現在のノード６ｂと接続する未処理の遷移が間隔条件付きの通常遷移であるので、現在のノードあるいは遷移先・元ノードが同系列関係であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノードあるいは遷移先・元ノードが同系列関係でないと判定する。そして、ＮＦＡ生成部１５２は、遷移先・元ノード６ｃ、６ｇを未処理ノード集合に追加する。
【０１４２】
図２０Ｅの３段目に示すように、ＮＦＡ生成部１５２は、現在のノード６ｅと接続する未処理の遷移がなく、同系列ノード集合に含まれるノードが空であるので、同系列ノード集合を出力しない。
【０１４３】
図２０Ｆの１段目に示すように、ＮＦＡ生成部１５２は、未処理ノード集合の中の最終状態ノードを除くノード番号の一番小さい未処理のノードを現在のノードとする。ここでは、ＮＦＡ生成部１５２は、未処理ノード集合の中のノード番号６のノード６ｇを現在のノードとする。
【０１４４】
続いて、ＮＦＡ生成部１５２は、現在のノード６ｇと接続する未処理の遷移がε遷移でないので、現在のノード６ｇあるいは遷移先のノードが同系列関係であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノード６ｇと遷移先のノード６ｈがどちらにも同系列関係情報「＝」が付加されていない。ＮＦＡ生成部１５２は、同系列関係でないと判定し、遷移先のノード６ｈを未処理ノード集合に追加する。
【０１４５】
図２０Ｆの２段目に示すように、ＮＦＡ生成部１５２は、現在のノード６ｇと接続する未処理の遷移がなく、同系列ノード集合に含まれるノードが空であるので、同系列ノード集合を出力しない。そして、ＮＦＡ生成部１５２は、未処理ノード集合に最終状態ノード６ｈを除く未処理のノードがあるか否かを判定する。ここでは、ＮＦＡ生成部１５３は、未処理ノード集合に含まれる最終状態ノード６ｈ（ノード番号７）を除くノード番号１、４、２、６のノードはすべて処理されているので、未処理のノードがないと判定する。そして、ＮＦＡ生成部１５２は、同系列ＮＦＡ探索処理を終了する。
【０１４６】
上述したように、ＮＦＡ生成部１５２は、図２０Ａ〜図２０Ｆに示す処理を実行することで、仮ＮＦＡから同系列ノード集合を出力する。すなわち、ＮＦＡ生成部１５２は、ノード番号１、２、３、５のノードを１組とした同系列ノード集合を出力する
【０１４７】
［同系列ＮＦＡ変換処理の説明］
次に、同系列ＮＦＡ変換処理について説明する。図２１Ａの１段目に示すように、ＮＦＡ生成部１５２は、同系列ノード集合の組が空であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、同系列ノード集合の組が存在するので空でないと判定する。そこで、ＮＦＡ生成部１５２は、同系列ノード集合の組から１組の同系列ノード集合を取り出す。すなわち、ＮＦＡ生成部１５２は、ノード番号１、２、３、５のノードを１組とした同系列ノード集合を取り出す。
【０１４８】
図２１Ｂの１段目に示すように、ＮＦＡ生成部１５２は、取り出した同系列ノード集合の未処理の１ノードを現在のノードとする。ここでは、ＮＦＡ生成部１５２は、同系列ノード集合の中から未処理のノードであるノード番号１のノード６ｂを現在のノードとする。
【０１４９】
図２１Ｂの２段目に示すように、ＮＦＡ生成部１５２は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがあるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノード６ｂと接続されているノード６ａ、６ｂの中にノード番号０のノード６ａが同系列ノード集合にない未処理のものであるので、未処理のものがあると判定する。そして、ＮＦＡ生成部１５２は、新しいノード６ｂ´を生成し、現在のノード６ｂの代わりに生成したノード６ｂ´と先の同系列ノード集合にないノード６ａとをそのままの遷移（ε遷移）で接続する。そして、ＮＦＡ生成部１５２は、現在のノード６ｂと生成したノード６ｂ´とこれら２つのノードの遷移方向の組とを境界ノード組集合に加える。かかる場合は、生成したノード６ｂ´が現在のノード６ｂの前方にある場合であるので、ＮＦＡ生成部１５２は、生成したノード６ｂ´から現在のノード６ｂへの遷移方向とする。
【０１５０】
図２１Ｃの１段目に示すように、ＮＦＡ生成部１５２は、同系列ノード集合の未処理の１ノードを現在のノードとする。ここでは、ＮＦＡ生成部１５２は、同系列ノード集合の中から未処理のノードであるノード番号２のノード６ｃを現在のノードとする。
【０１５１】
図２１Ｃの２段目に示すように、ＮＦＡ生成部１５２は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがあるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノード６ｃと接続されているノード６ｂ、６ｄの中にノード番号４のノード６ｅが同系列ノード集合にない未処理のものであるので、未処理のものがあると判定する。そして、ＮＦＡ生成部１５２は、新しいノード６ｃ´を生成し、現在のノード６ｃの代わりに生成したノード６ｃ´と先の同系列ノード集合にないノード６ｅとをそのままの遷移（ε遷移）で接続する。そして、ＮＦＡ生成部１５２は、現在のノード６ｃと生成したノード６ｃ´とこれら２つのノードの遷移方向の組とを境界ノード組集合に加える。かかる場合は、生成したノード６ｂ´が現在のノード６ｂの後方にある場合であるので、ＮＦＡ生成部１５２は、現在のノード６ｃから、生成したノード６ｃ´への遷移方向とする。
【０１５２】
図２１Ｄの１段目に示すように、ＮＦＡ生成部１５２は、同系列ノード集合の未処理の１ノードを現在のノードとする。ここでは、ＮＦＡ生成部１５２は、同系列ノード集合の中から未処理のノードであるノード番号３のノード６ｄを現在のノードとする。
【０１５３】
続いて、ＮＦＡ生成部１５２は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがあるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノード６ｄと接続されているノード６ｃ、６ｆの中に同系列ノード集合にない未処理のものでないので、未処理のものがないと判定する。
【０１５４】
図２１Ｄの２段目に示すように、ＮＦＡ生成部１５２は、同系列ノード集合の未処理の１ノードを現在のノードとする。ここでは、ＮＦＡ生成部１５２は、同系列ノード集合の中から未処理のノードであるノード番号５のノード６ｆを現在のノードとする。
【０１５５】
図２１Ｅの１段目に示すように、ＮＦＡ生成部１５２は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがあるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノード６ｆと接続されているノード６ｄ、６ｈの中にノード番号７のノード６ｈが同系列ノード集合にない未処理のものであるので、未処理のものがあると判定する。そして、ＮＦＡ生成部１５２は、新しいノード６ｆ´を生成し、現在のノード６ｆの代わりに生成したノード６ｆ´と先の同系列ノード集合にないノード６ｈとをそのままの遷移（ε遷移）で接続する。そして、ＮＦＡ生成部１５２は、現在のノード６ｆと生成したノード６ｆ´とこれら２つのノードの遷移方向の組とを境界ノード組集合に加える。かかる場合は、生成したノード６ｆ´が現在のノード６ｆの後方にある場合であるので、ＮＦＡ生成部１５２は、現在のノード６ｆから、生成したノード６ｆ´への遷移方向とする。
【０１５６】
図２１Ｅの２段目に示すように、ＮＦＡ生成部１５２は、同系列ノード集合に未処理のノードがないので、同系列ノード集合のノードおよびそのノード間の遷移エッジすべてを１セットとして、系列数分だけ複製する。ここでは、系列数を３とすると、ＮＦＡ生成部１５２は、同系列ノード集合のノード６ｂ、６ｃ、６ｄ、６ｆおよびそのノード間の遷移エッジすべてを３系列数分複製する。そして、ＮＦＡ生成部１５２は、ノード間の遷移を各系列のイベントで受理する遷移に置き換える。すなわち、ＮＦＡ生成部１５２は、複製元の一段目の遷移を０系列のイベントで受理する遷移に置き換え、複製した２段目の遷移を１系列のイベントで受理する遷移に置き換え、複製した３段目の遷移を２系列のイベントで受理する遷移に置き換える。
【０１５７】
図２１Ｆの１段目に示すように、ＮＦＡ生成部１５２は、境界ノード組集合から未処理の１組の境界ノードの組を取り出す。ここでは、ＮＦＡ生成部１５２は、境界ノード組集合から、ノード番号が１´である生成ノード６ｂ´からノード番号が１である現在のノード６ｂへの遷移方向の境界ノードの組を取り出す。そして、ＮＦＡ生成部１５２は、取り出した１組の現在のノードと生成ノードと遷移方向に従い、現在のノードに対応する複製したすべてのノードと生成ノードを遷移方向どおりにすべてε遷移で接続する。ここでは、ＮＦＡ生成部１５２は、現在のノード６ｂに対応する、複製した３系列のノード６ｂと生成ノード６ｂ´を、生成ノード６ｂ´から現在のノード６ｂへの遷移方向どおりにすべてε遷移で接続する。
【０１５８】
図２１Ｆの２段目に示すように、ＮＦＡ生成部１５２は、境界ノード組集合から未処理の１組の境界ノードの組を取り出す。ここでは、ＮＦＡ生成部１５２は、境界ノード組集合から、ノード番号が２である現在のノード６ｃからノード番号が２´である生成ノード６ｃ´への遷移方向の境界ノードの組を取り出す。そして、ＮＦＡ生成部１５２は、取り出した１組の現在のノードと生成ノードと遷移方向に従い、現在のノードに対応する複製したすべてのノードと生成ノードを遷移方向どおりにすべてε遷移で接続する。ここでは、ＮＦＡ生成部１５２は、現在のノード６ｃに対応する、複製した３系列のノード６ｃと生成ノード６ｃ´を、現在のノード６ｃから生成ノード６ｃ´への遷移方向どおりにすべてε遷移で接続する。
【０１５９】
図２１Ｇの１段目に示すように、ＮＦＡ生成部１５２は、境界ノード組集合から未処理の１組の境界ノードの組を取り出す。ここでは、ＮＦＡ生成部１５２は、境界ノード組集合から、ノード番号が５である現在のノード６ｆからノード番号が５´である生成ノード６ｆ´への遷移方向の境界ノードの組を取り出す。そして、ＮＦＡ生成部１５２は、取り出した１組の現在のノードと生成ノードと遷移方向に従い、現在のノードに対応する複製したすべてのノードと生成ノードを遷移方向どおりにすべてε遷移で接続する。ここでは、ＮＦＡ生成部１５２は、現在のノード６ｆに対応する、複製した３系列のノード６ｆと生成ノード６ｆ´を、現在のノード６ｆから生成ノード６ｆ´への遷移方向どおりにすべてε遷移で接続する。
【０１６０】
図２１Ｇの２段目に示すように、ＮＦＡ生成部１５２は、同系列ノード集合の組が空なので、系列の値の大小関係を保ち、境界ノード組集合の遷移元が小さいノード番号となるよう、ユニークなノード番号を振りなおす。
【０１６１】
［別のパターンにおけるＮＦＡを生成する処理の一例］
次に、別のパターンをイベントパターン１４１とした場合に、図１１〜図１８に示したＮＦＡの構築法を用いて、ＮＦＡ生成部１５２が、イベントパターン１４１からＮＦＡ１４２を生成する処理の一例について説明する。図２２Ａ〜図２２Ｇは、仮ＮＦＡを生成する処理を説明する図である。図２３Ａ〜図２３Ｇは、同系列のＮＦＡを探索する処理を説明する図である。図２４Ａ〜図２４Ｍは、同系列のＮＦＡを変換する処理を説明する図である。
【０１６２】
［仮ＮＦＡ生成処理の説明］
図２２Ａに示すように、イベントパターン１４１のデータ構造を、符号２０２ｐに示すものとする。イベントパターン１４３は、任意の系列でイベントＡが発生し、その後２以内にＡと同じ系列でイベントＢが発生するパターンを有する。そして、イベントパターン１４３は、任意の系列で発生したイベントＡの発生後４以内に任意の系列でイベントＣが発生するパターンを有する。そして、イベントパターン１４３は、イベントＣの発生後３以内且つイベントＤの発生後５以内且つイベントＢの発生後４以内にイベントＣと同じ系列でイベントＥが発生するパターンを有する。
【０１６３】
図２２Ｂの１段目に示すように、ＮＦＡ生成部１５２は、ノード番号を０とする初期状態のノード７ａを生成し、生成したノード７ａに空の＠リストを登録する。そして、ＮＦＡ生成部１５２は、現ノード番号ｉの値を０に設定し、現＠番号ｊの値を０に設定する。そして、ＮＦＡ生成部１５２は、入力されたイベントパターン１４１に示されたイベント受理制約の内、前に間隔制約がないものを集め、仮イベント集合とする。ここでは、ＮＦＡ生成部１５２は、イベントＡのイベント受理制約およびイベントＤのイベント受理制約を仮イベント集合とする。そして、ＮＦＡ生成部１５２は、初期状態のノード７ａを起点ノードとする。
【０１６４】
図２２Ｂの２段目に示すように、ＮＦＡ生成部１５２は、起点ノードが初期状態のノード７ａであるので、仮イベント集合に集められた１つのイベント受理制約（Ａ）に対応するイベント入力ノード７ｂを生成する。そして、ＮＦＡ生成部１５２は、生成したノード７ｂに現ノード番号ｉに１を加算した値１を割り当てる。そして、ＮＦＡ生成部１５２は、起点ノード７ａからイベント入力ノード７ｂへε遷移で接続する。また、ＮＦＡ生成部１５２は、仮イベント集合に集められたもう１つのイベント受理制約（Ｄ）に対応するイベント入力ノード７ｃを生成する。そして、ＮＦＡ生成部１５２は、生成したノード７ｃに現ノード番号ｉに１を加算した値２を割り当てる。そして、ＮＦＡ生成部１５２は、起点ノード７ａからイベント入力ノード７ｃへε遷移で接続する。
【０１６５】
図２２Ｂの３段目に示すように、ＮＦＡ生成部１５２は、仮イベント集合に集められたイベント受理制約から未処理のイベント受理制約を１つ取り出す。ここでは、ＮＦＡ生成部１５２はイベントＡを取り出す。そして、ＮＦＡ生成部１５２は、取り出したイベントＡに付随する前方間隔制約がないので、イベント受理完了ノード７ｄを生成し、生成したノード７ｄに、現ノード番号ｉに１を加算した値３を割り当てる。そして、ＮＦＡ生成部１５２は、イベントＡの受理によりイベント入力ノード７ｂからイベント受理完了ノード７ｄに遷移するエッジで接続する。さらに、ＮＦＡ生成部１５２は、イベント入力ノード７ｂの＠リストをイベント受理完了ノード７ｄの＠リストにコピーする。
【０１６６】
図２２Ｂの４段目に示すように、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ａ）の後方間隔制約の中で同系列関係のものＢがあるので、イベント受理完了ノード７ｄに同系列関係情報「＝」を付加する。
【０１６７】
続いて、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ａ）の前方の間隔制約の数をＦとする。ここでは、ＮＦＡ生成部１５２は、イベントＡの前方の間隔に制約がないので、Ｆを０に設定する。そして、ＮＦＡ生成部１５２は、Ｆが２以上でないので、イベント受理完了ノード７ｄを完了ノードとする。さらに、ＮＦＡ生成部１５２は、取り出したイベント受理制約（Ａ）の後方への間隔制約を持つイベント受理制約を前方間隔制約と前方間隔制約種別と共に集め、仮イベント集合とする。ここでは、ＮＦＡ生成部１５２は、イベントＡの後方イベントＢまでの間隔制約が２であり、同系列の遷移関係であるので、イベント受理制約Ｂを前方間隔制約２と同系列の遷移関係の制約であることを示す種別と共に仮イベント集合に設定する。また、ＮＦＡ生成部１５２は、イベントＡの後方イベントＣまでの間隔制約が４であり、任意系列の遷移関係であるので、イベント受理制約Ｃを前方間隔制約４と任意系列の遷移関係の制約であることを示す種別と共に仮イベント集合に設定する。そして、ＮＦＡ生成部１５２は、完了ノード７ｄを起点ノードとする。
【０１６８】
図２２Ｃの１段目に示すように、ＮＦＡ生成部１５２は、起点ノード７ｄが初期状態のノードでなく、且つ仮イベント集合に集められたイベント受理制約（Ｂ、Ｃ）が２つ以上であるので、起点ノード７ｄに現＠番号ｊの値０を割り当てる。すなわち、この起点ノード７ｄは、＠番号０（＠０）を有する受理時刻保持ノードとなる。そして、ＮＦＡ生成部１５２は、現＠番号ｊの値を、１加算した値１に設定する。
【０１６９】
図２２Ｃの２段目に示すように、ＮＦＡ生成部１５２は、起点ノード７ｄの＠リスト２ｍに、割り当てた＠番号０およびタイムアウト０を設定する。
【０１７０】
図２２Ｃの３段目に示すように、ＮＦＡ生成部１５２は、仮イベント集合に集められたイベント受理制約（Ｂ、Ｃ）に対応するイベント入力ノード７ｅ、７ｆを生成する。そして、ＮＦＡ生成部１５２は、生成したノード７ｅに現ノード番号ｉ（３）に１を加算した値４を割り当て、生成したノード７ｆにさらに現ノード番号ｉ（４）に１を加算した値５を割り当てる。そして、ＮＦＡ生成部１５２は、起点ノード７ｄからイベント入力ノード７ｅへε遷移で接続し、起点ノード７ｄからイベント入力ノード７ｆへε遷移で接続する。そして、ＮＦＡ生成部１５２は、起点ノード７ｄの＠リストをイベント入力ノード７ｅ、７ｆのそれぞれの＠リストにコピーする。
【０１７１】
図２２Ｃの４段目に示すように、ＮＦＡ生成部１５２は、仮イベント集合に集められたイベント受理制約（Ｂ、Ｃ）から未処理のイベント受理制約を１つ取り出す。ここでは、ＮＦＡ生成部１５２はイベントＢを取り出す。そして、ＮＦＡ生成部１５２は、イベント受理完了ノード７ｇを生成し、生成したノード７ｇに、現ノード番号ｉに１を加算した値６を割り当てる。そして、ＮＦＡ生成部１５２は、前方間隔制約２を満たすイベントＢの受理によりイベント入力ノード７ｅからイベント受理完了ノード７ｇに遷移するエッジで接続する。すなわち、イベント入力ノード７ｅからイベント受理完了ノード７ｇへの遷移が「間隔条件付きの通常遷移」となる。さらに、ＮＦＡ生成部１５２は、イベント入力ノード７ｅの＠リストのタイムアウトに前方間隔制約２を加えてからイベント受理完了ノード７ｇの＠リストにコピーする。
【０１７２】
図２２Ｃの５段目に示すように、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ｂ）に付随する前方間隔制約種別が同系列関係であるので、イベント入力ノード７ｅに同系列関係情報「＝」を付加する。
【０１７３】
続いて、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ｂ）の前方の間隔制約の数をＦとする。ここでは、イベントＢの前方間隔制約は２のものだけであるので、ＮＦＡ生成部１５２は、前方の間隔制約の数Ｆを１に設定する。そして、ＮＦＡ生成部１５２は、Ｆが２以上でないので、イベント受理完了ノード７ｇを完了ノードとする。さらに、ＮＦＡ生成部１５２は、取り出したイベント受理制約（Ｂ）の後方への間隔制約を持つイベント受理制約を集め、仮イベント集合とする。ここでは、ＮＦＡ生成部１５２は、イベントＢの後方イベントＥまでの間隔制約が４であり、任意系列の遷移関係であるので、イベント受理制約Ｅを前方間隔制約４と任意系列の遷移関係の制約であることを示す種別と共に仮イベント集合に設定する。そして、ＮＦＡ生成部１５２は、完了ノード７ｇを起点ノードとする。
【０１７４】
図２２Ｄの１段目に示すように、ＮＦＡ生成部１５２は、仮イベント集合に集められたイベント受理制約（Ｅ）に対応するイベント入力ノード７ｈを生成する。そして、ＮＦＡ生成部１５２は、生成したノード７ｈに現ノード番号ｉ（６）に１を加算した値７を割り当てる。そして、ＮＦＡ生成部１５２は、起点ノード７ｇからイベント入力ノード７ｈへε遷移で接続する。そして、ＮＦＡ生成部１５２は、起点ノード７ｇの＠リストをイベント入力ノード７ｈの＠リストにコピーする。
【０１７５】
図２２Ｄの２段目に示すように、ＮＦＡ生成部１５２は、仮イベント集合に集められたイベント受理制約から未処理のイベント受理制約を１つ取り出す。ここでは、ＮＦＡ生成部１５２はイベントＥを取り出す。そして、ＮＦＡ生成部１５２は、イベント受理完了ノード７ｉを生成し、生成したノード７ｉに、現ノード番号ｉに１を加算した値８を割り当てる。そして、ＮＦＡ生成部１５２は、前方間隔制約４を満たすイベントＥの受理によりイベント入力ノード７ｈからイベント受理完了ノード７ｉに遷移するエッジで接続する。さらに、ＮＦＡ生成部１５２は、イベント入力ノード７ｈの＠リストのタイムアウトに前方間隔制約４を加えてからイベント受理完了ノード７ｉの＠リストにコピーする。
【０１７６】
続いて、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ｅ）に付随する前方間隔制約種別が同系列関係でないので、イベント入力ノード７ｈに同系列関係情報を付加しない。また、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ｅ）の後方間隔制約がないので、イベント受理完了ノード７ｉに同系列関係情報を付加しない。
【０１７７】
続いて、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ｅ）の前方の間隔制約の数の数をＦとする。ここでは、イベントＥの前方間隔制約はイベントＢからの４の制約とイベントＣからの３の制約とイベントＤからの５の制約があるので、ＮＦＡ生成部１５２は、前方の間隔制約の数Ｆを３に設定する。そして、ＮＦＡ生成部１５２は、Ｆが２以上であり、現在のイベント受理制約（Ｅ）に対応する生成済みのイベント受理完了ノードがノード７ｉの１個のみであるので、仮イベント集合に集められたイベント受理制約のうち未処理のものがあるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、仮イベント集合に集められたイベント受理制約Ｅの処理が終了したので、元の仮イベント集合および元の起点ノードに戻す。すなわち、起点ノードはノード番号が３であるノード７ｄとなり、仮イベント集合はイベント受理制約Ｂ、Ｃになる。
【０１７８】
図２２Ｄの３段目に示すように、ＮＦＡ生成部１５２は、仮イベント集合に集められたイベント受理制約（Ｂ、Ｃ）から未処理のイベント受理制約を１つ取り出す。ここでは、ＮＦＡ生成部１５２は、イベントＢの処理が終了しているので、イベント受理制約Ｃを取り出す。そして、ＮＦＡ生成部１５２は、イベント受理完了ノード７ｊを生成し、生成したノード７ｊに、現ノード番号ｉに１を加算した値９を割り当てる。そして、ＮＦＡ生成部１５２は、イベントＣの受理によりイベント入力ノード７ｆからイベント受理完了ノード７ｊに遷移するエッジで接続し、＠リストをコピーする。さらに、ＮＦＡ生成部１５２は、現在のイベント受理制約Ｃの後方間隔制約に同系列関係のものがあるので、イベント受理完了ノード７ｊに同系列関係情報「＝」を付加する。
【０１７９】
続いて、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ｃ）の前方の間隔制約が１つなので、イベント受理完了ノード７ｊを完了ノードとする。さらに、ＮＦＡ生成部１５２は、取り出したイベント受理制約（Ｃ）の後方への間隔制約を持つイベント受理制約を前方間隔制約と前方間隔制約種別と共に集め、仮イベント集合とする。ここでは、ＮＦＡ生成部１５２は、イベントＣの後方イベントＥまでの間隔制約が３であり、同系列の遷移関係であるので、イベント受理制約Ｅを前方間隔制約３と同系列の遷移関係の制約であることを示す種別と共に仮イベント集合に設定する。そして、ＮＦＡ生成部１５２は、完了ノード７ｊを起点ノードとする。
【０１８０】
図２２Ｄの４段目に示すように、ＮＦＡ生成部１５２は、仮イベント集合に集められたイベント受理制約（Ｅ）に対応するイベント入力ノード７ｋを生成する。そして、ＮＦＡ生成部１５２は、生成したノード７ｋに現ノード番号ｉ（９）に１を加算した値１０を割り当てる。そして、ＮＦＡ生成部１５２は、起点ノード７ｊからイベント入力ノード７ｋへε遷移で接続する。そして、ＮＦＡ生成部１５２は、起点ノード７ｊの＠リストをイベント入力ノード７ｋの＠リストにコピーする。
【０１８１】
図２２Ｄの５段目に示すように、ＮＦＡ生成部１５２は、仮イベント集合に集められたイベント受理制約から未処理のイベント受理制約を１つ取り出す。ここでは、ＮＦＡ生成部１５２はイベントＥを取り出す。そして、ＮＦＡ生成部１５２は、イベント受理完了ノード７ｌを生成し、生成したノード７ｌに、現ノード番号ｉに１を加算した値１１を割り当てる。そして、ＮＦＡ生成部１５２は、前方間隔制約３を満たすイベントＥの受理によりイベント入力ノード７ｋからイベント受理完了ノード７ｌに遷移するエッジで接続する。さらに、ＮＦＡ生成部１５２は、イベント入力ノード７ｋの＠リストのタイムアウトに前方間隔制約３を加えてからイベント受理完了ノード７ｌの＠リストにコピーする。
【０１８２】
続いて、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ｅ）に付随する前方間隔制約種別が同系列関係でないので、イベント入力ノード７ｋに同系列関係情報を付加しない。また、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ｅ）の後方間隔制約がないので、イベント受理完了ノード７ｌに同系列関係情報を付加しない。
【０１８３】
続いて、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ｅ）の前方の間隔制約の数の数をＦとする。ここでは、イベントＥの前方間隔制約はイベントＢからの４の制約とイベントＣからの３の制約とイベントＤからの５の制約があるので、ＮＦＡ生成部１５２は、前方の間隔制約の数Ｆを３に設定する。そして、ＮＦＡ生成部１５２は、Ｆが２以上であり、現在のイベント受理制約（Ｅ）に対応する生成済みのイベント受理完了ノードがノード７ｉとノード７ｌの２個であるので、仮イベント集合に集められたイベント受理制約のうち未処理のものがあるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、仮イベント集合に集められたイベント受理制約Ｅの処理が終了したので、元の仮イベント集合および元の起点ノードに戻す。すなわち、起点ノードは初期状態のノード７ａとなり、仮イベント集合はイベント受理制約Ａ、Ｄになる。
【０１８４】
図２２Ｅの１段目に示すように、ＮＦＡ生成部１５２は、仮イベント集合に集められたイベント受理制約（Ａ、Ｄ）から未処理のイベント受理制約を１つ取り出す。ここでは、ＮＦＡ生成部１５２は、イベントＡの処理が終了しているので、イベントＤを取り出す。そして、ＮＦＡ生成部１５２は、イベント受理完了ノード７ｍを生成し、生成したノード７ｍに、現ノード番号ｉに１を加算した値１２を割り当てる。そして、ＮＦＡ生成部１５２は、イベントＤの受理によりイベント入力ノード７ｃからイベント受理完了ノード７ｍに遷移するエッジで接続し、＠リストをコピーする。さらに、ＮＦＡ生成部１５２は、現在のイベント受理制約Ｄの後方間隔制約に同系列関係のものがあるので、イベント受理完了ノード７ｍに同系列関係情報「＝」を付加する。
【０１８５】
続いて、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ｄ）の前方の間隔制約が１つなので、イベント受理完了ノード７ｍを完了ノードとする。さらに、ＮＦＡ生成部１５２は、取り出したイベント受理制約（Ｄ）の後方への間隔制約を持つイベント受理制約を前方間隔制約と前方間隔制約種別と共に集め、仮イベント集合とする。ここでは、ＮＦＡ生成部１５２は、イベントＤの後方イベントＥまでの間隔制約が５であり、同系列の遷移関係であるので、イベント受理制約Ｅを前方間隔制約５と同系列の遷移関係の制約であることを示す種別と共に仮イベント集合に設定する。そして、ＮＦＡ生成部１５２は、完了ノード７ｍを起点ノードとする。
【０１８６】
図２２Ｅの２段目に示すように、ＮＦＡ生成部１５２は、仮イベント集合に集められたイベント受理制約（Ｅ）に対応するイベント入力ノード７ｎを生成する。そして、ＮＦＡ生成部１５２は、生成したノード７ｎに現ノード番号ｉ（１２）に１を加算した値１３を割り当てる。そして、ＮＦＡ生成部１５２は、起点ノード７ｍからイベント入力ノード７ｎへε遷移で接続する。そして、ＮＦＡ生成部１５２は、起点ノード７ｍの＠リストをイベント入力ノード７ｎの＠リストにコピーする。
【０１８７】
図２２Ｅの３段目に示すように、ＮＦＡ生成部１５２は、仮イベント集合に集められたイベント受理制約から未処理のイベント受理制約を１つ取り出す。ここでは、ＮＦＡ生成部１５２はイベントＥを取り出す。そして、ＮＦＡ生成部１５２は、イベント受理完了ノード７ｏを生成し、生成したノード７ｏに、現ノード番号ｉに１を加算した値１４を割り当てる。そして、ＮＦＡ生成部１５２は、前方間隔制約５を満たすイベントＥの受理によりイベント入力ノード７ｎからイベント受理完了ノード７ｏに遷移するエッジで接続する。さらに、ＮＦＡ生成部１５２は、イベント入力ノード７ｎの＠リストのタイムアウトに前方間隔制約５を加えてからイベント受理完了ノード７ｏの＠リストにコピーする。
【０１８８】
続いて、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ｅ）の前方の間隔制約の数の数をＦとする。ここでは、イベントＥの前方間隔制約はイベントＢからの４の制約とイベントＣからの３の制約とイベントＤからの５の制約があるので、ＮＦＡ生成部１５２は、前方の間隔制約の数Ｆを３に設定する。そして、ＮＦＡ生成部１５２は、Ｆが２以上であり、現在のイベント受理制約（Ｅ）に対応する生成済みのイベント受理完了ノードがノード７ｉとノード７ｌとノード７ｏの３個であるので、次の処理を行う。
【０１８９】
図２２Ｆの１段目に示すように、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ｅ）に対応する合流ノード７ｐを生成する。そして、ＮＦＡ生成部１５２は、生成したノード７ｐに現ノード番号ｉに１を加算した値１５を割り当てる。そして、ＮＦＡ生成部１５２は、生成済みのイベント受理完了ノード７ｉ、７ｌ、７ｏから合流ノード７ｐへε＝遷移で接続する。
【０１９０】
図２２Ｆの２段目に示すように、ＮＦＡ生成部１５２は、合流ノード７ｐに同系列関係情報「＝」を付加する。
【０１９１】
図２２Ｆの３段目に示すように、ＮＦＡ生成部１５２は、現在の＠番号ｊ（１）およびタイムアウト０を現在のイベント受理制約（Ｅ）に対応する生成済みの全てのイベント受理完了ノード７ｉ、７ｌ、７ｏに割り当て、それぞれの＠リストに追加する。すなわち、このイベント受理完了ノード７ｉ、７ｌ、７ｏは、＠番号１（＠１）を有する受理時刻保持ノードとなる。そして、ＮＦＡ生成部１５２は、＠番号ｊに１を加算して２を設定する。
【０１９２】
図２２Ｇの１段目に示すように、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ｅ）に対応する生成済みのイベント受理完了ノード７ｉ、７ｌ、７ｏの＠リストにおいて、複数のノードで同一の番号を持っている＠番号を合流ノードの指定＠番号とする。そして、ＮＦＡ生成部１５２は、＠番号毎にタイムアウトの中で一番大きい値をタイムアウト長として登録する。ここでは、ノード７ｉが持っている＠番号は＠０、＠１であり、ノード７ｌが持っている＠番号は＠０、＠１であり、ノード７ｏが持っている＠番号は＠１である。そこで、ＮＦＡ生成部１５２は、＠０、＠１を合流ノード７ｐの指定＠番号とし、＠０のタイムアウト長を７、＠１のタイムアウト長を０として登録する。
【０１９３】
図２２Ｇの２段目に示すように、ＮＦＡ生成部１５２は、現在のイベント受理制約（Ｅ）に対応する生成済みのイベント受理完了ノード７ｉ、７ｌ、７ｏの各＠リストに含まれる＠番号および各＠番号で最大のタイムアウト長を合流ノード７ｐの＠リストに設定する。ここでは、ＮＦＡ生成部１５２は、＠番号＠０およびタイムアウト長７を対応付けて設定し、＠番号＠１およびタイムアウト長０を対応付けて設定する。そして、ＮＦＡ生成部１５２は、合成ノード７ｐを完了ノードとする。さらに、ＮＦＡ生成部１５２は、終端ノードリストに完了ノード７ｐを追加する。
【０１９４】
図２２Ｇの３段目に示すように、ＮＦＡ生成部１５２は、終端ノードリストにノードが２つ以上あるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、終端ノードリストにノード７ｐが１つあるのみであるので、終端ノードリストのノード７ｐを最終状態ノードとする。
【０１９５】
上述したように、ＮＦＡ生成部１５２は、図２２Ａ〜図２２Ｇに示す処理を実行することで、図２２Ａに示すイベントパターン１４１から仮ＮＦＡを生成する。
【０１９６】
［別のパターンにおける同系列ＮＦＡ探索処理の説明］
次に、別のパターンにおける同系列ＮＦＡ探索処理について説明する。まず、ＮＦＡ生成部１５２は、生成した仮ＮＦＡの初期状態ノード７ａを現在のノードとする。また、ＮＦＡ生成部１５２は、未処理ノード集合および同系列ノード集合を空にする。そして、ＮＦＡ生成部１５２は、現在のノード７ａと接続する１つのε遷移について、現在のノード７ａと遷移先のノード７ｂとがともに同系列関係でないので、遷移先のノード７ｂを未処理ノード集合に追加する。同様に、ＮＦＡ生成部１５２は、現在のノード７ａと接続するもう１つのε遷移について、現在のノード７ａと遷移先のノード７ｃとがともに同系列関係でないので、遷移先のノード７ｃを未処理ノード集合に追加する。さらに、ＮＦＡ生成部１５２は、現在のノード７ａと接続する未処理の遷移がなく、同系列ノード集合に含まれるノードが空であるので、同系列ノード集合を出力しない。そして、ＮＦＡ生成部１５２は、未処理ノード集合の中の最終状態ノードを除くノード番号の一番小さい未処理のノードを現在のノードとする。ここでは、ＮＦＡ生成部１５２は、未処理ノード集合の中のノード番号１のノード７ｂを現在のノードとする。
【０１９７】
図２３Ａの１段目に示すように、ＮＦＡ生成部１５２は、現在のノード７ｂと接続する未処理の遷移が間隔条件なしの通常遷移であるので、現在のノード７ｂあるいは遷移先のノード７ｄが同系列関係であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、遷移先のノード７ｄが同系列関係情報「＝」が付加されているので、同系列関係であると判定する。そして、ＮＦＡ生成部１５２は、現在のノード７ｂと遷移先のノード７ｄを同系列ノード集合に追加する。
【０１９８】
図２３Ａの２段目に示すように、ＮＦＡ生成部１５２は、現在のノード７ｂと接続する未処理の遷移がないので、同系列ノード集合に含まれるノードがすべて処理したか否かを判定する。そして、ＮＦＡ生成部１５２は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号３のノード７ｄを現在のノードとする。そして、ＮＦＡ生成部１５２は、現在のノード７ｄと接続する未処理の遷移がε遷移であるので、現在のノード７ｄと遷移先のノードとが同系列関係であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノード７ｄと遷移先のノード７ｅとがともに同系列関係情報「＝」が付加されているので、ともに同系列関係であると判定する。そして、ＮＦＡ生成部１５２は、現在のノード７ｄと遷移先のノード７ｅを同系列ノード集合に追加する。また、ＮＦＡ生成部１５２は、現在のノード７ｄと遷移先のノード７ｆとが双方ともに同系列関係情報「＝」が付加されていないので、ともに同系列関係でないと判定する。そして、ＮＦＡ生成部１５２は、遷移先のノード７ｆを未処理ノード集合に追加する。
【０１９９】
図２３Ａの３段目に示すように、ＮＦＡ生成部１５２は、現在のノード７ｄと接続する未処理の遷移がないので、同系列ノード集合に含まれるノードがすべて処理したか否かを判定する。そして、ＮＦＡ生成部１５２は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号４のノード７ｅを現在のノードとする。そして、ＮＦＡ生成部１５２は、現在のノード７ｅと接続する未処理の遷移が間隔条件付きの通常遷移であるので、現在のノード７ｅあるいは遷移先のノード７ｇが同系列関係であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノード７ｅが同系列関係情報「＝」が付加されているので、同系列関係であると判定する。そして、ＮＦＡ生成部１５２は、現在のノード７ｅと遷移先のノード７ｇを同系列ノード集合に追加する。
【０２００】
図２３Ｂの１段目に示すように、ＮＦＡ生成部１５２は、現在のノード７ｅと接続する未処理の遷移がないので、同系列ノード集合に含まれるノードがすべて処理したか否かを判定する。そして、ＮＦＡ生成部１５２は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号６のノード７ｇを現在のノードとする。そして、ＮＦＡ生成部１５２は、現在のノード７ｅと接続する未処理の遷移がε遷移であるので、現在のノード７ｅと遷移先のノード７ｈがともに同系列関係であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノード７ｅと遷移先のノード７ｈがともに同系列関係情報「＝」が付加されていないので、同系列関係でないと判定する。そして、ＮＦＡ生成部１５２は、遷移先のノード７ｈを未処理ノード集合に追加する。
【０２０１】
図２３Ｂの２段目に示すように、ＮＦＡ生成部１５２は、現在のノード７ｇと接続する未処理の遷移がなく、同系列ノード集合に含まれるノードはすべて処理したので、同系列ノード集合を出力する。ここでは、ＮＦＡ生成部１５２は、ノード番号１、３、４、６のノードを同系列ノード集合として出力する。そして、ＮＦＡ生成部１５２は、出力後、同系列ノード集合を空にする。
【０２０２】
図２３Ｃの１段目に示すように、ＮＦＡ生成部１５２は、未処理ノード集合の中の最終状態ノードを除くノード番号の一番小さい未処理のノードを現在のノードとする。ここでは、ＮＦＡ生成部１５２は、未処理ノード集合の中のノード番号２のノード７ｃを現在のノードとする。
【０２０３】
図２３Ｃの２段目に示すように、ＮＦＡ生成部１５２は、現在のノード７ｃと接続する未処理の遷移が間隔条件なしの通常遷移であるので、現在のノード７ｃあるいは遷移先のノード７ｍが同系列関係であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、遷移先のノード７ｍが同系列関係情報「＝」が付加されているので、同系列関係であると判定する。そして、ＮＦＡ生成部１５２は、現在のノード７ｃと遷移先のノード７ｍを同系列ノード集合に追加する。そして、ＮＦＡ生成部１５２は、現在のノード７ｃと接続する未処理の遷移がないので、同系列ノード集合に含まれるノードがすべて処理したか否かを判定する。そして、ＮＦＡ生成部１５２は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号１２のノード７ｍを現在のノードとする。
【０２０４】
図２３Ｃの３段目に示すように、ＮＦＡ生成部１５２は、現在のノード７ｍと接続する未処理の遷移がε遷移であるので、現在のノード７ｍと遷移先のノードとが同系列関係であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノード７ｍと遷移先のノード７ｎとがともに同系列関係情報「＝」が付加されているので、ともに同系列関係であると判定する。そして、ＮＦＡ生成部１５２は、現在のノード７ｍと遷移先のノード７ｎを同系列ノード集合に追加する。そして、ＮＦＡ生成部１５２は、現在のノード７ｍと接続する未処理の遷移がないので、同系列ノード集合に含まれるノードがすべて処理したか否かを判定する。そして、ＮＦＡ生成部１５２は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号１３のノード７ｎを現在のノードとする。
【０２０５】
図２３Ｄの１段目に示すように、ＮＦＡ生成部１５２は、現在のノード７ｎと接続する未処理の遷移が間隔条件付きの通常遷移であるので、現在のノード７ｎあるいは遷移先のノード７ｏが同系列関係であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノード７ｎに同系列関係情報「＝」が付加されているので、同系列関係であると判定する。そして、ＮＦＡ生成部１５２は、現在のノード７ｎと遷移先のノード７ｏを同系列ノード集合に追加する。そして、ＮＦＡ生成部１５２は、現在のノード７ｎと接続する未処理の遷移がないので、同系列ノード集合に含まれるノードがすべて処理したか否かを判定する。そして、ＮＦＡ生成部１５２は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号１４のノード７ｏを現在のノードとする。
【０２０６】
図２３Ｄの２段目に示すように、ＮＦＡ生成部１５２は、現在のノード７ｏと接続する未処理の遷移がε遷移でないので、現在のノード７ｏあるいは遷移先・元ノードが同系列関係であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、同系列ノード集合に現在のノード７ｏが含まれ、遷移先ノード７ｐに同系列関係情報「＝」が付加されているので、同系列関係であると判定する。そして、ＮＦＡ生成部１５２は、現在のノード７ｏと遷移先・元ノード７ｐ（ノード番号１５）を同系列ノード集合に追加する。そして、ＮＦＡ生成部１５２は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号１５のノード７ｐを現在のノードとする。
【０２０７】
図２３Ｄの３段目に示すように、ＮＦＡ生成部１５２は、現在のノード７ｐと接続する未処理の遷移がε遷移でないので、現在のノード７ｐあるいは遷移先・元ノードが同系列関係であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノード７ｐが同系列関係なので、現在のノード７ｐと遷移先・元ノード７ｉ（ノード番号８）を同系列ノード集合に追加する。また、ＮＦＡ生成部１５２は、現在のノード７ｐが同系列関係なので、現在のノード７ｐと遷移先・元ノード７ｌ（ノード番号１１）を同系列ノード集合に追加する。
【０２０８】
図２３Ｅの１段目に示すように、ＮＦＡ生成部１５２は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号８のノード７ｉを現在のノードとする。
【０２０９】
図２３Ｅの２段目に示すように、ＮＦＡ生成部１５２は、現在のノード７ｉと接続する未処理の遷移がないので、同系列ノード集合に含まれるノードに未処理のノードがあるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号１１のノード７ｌを現在のノードとする。そして、ＮＦＡ生成部１５２は、現在のノード７ｌと接続する未処理の遷移が間隔条件付きの通常遷移であるので、現在のノード７ｌあるいは遷移先・元ノードが同系列関係であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、遷移先・元ノード７ｋが同系列関係であるので、現在のノード７ｌと遷移先・元ノード７ｋを同系列ノード集合に追加する。
【０２１０】
図２３Ｅの３段目に示すように、ＮＦＡ生成部１５２は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号９のノード７ｊを現在のノードとする。
【０２１１】
図２３Ｆの１段目に示すように、ＮＦＡ生成部１５２は、現在のノード７ｊと接続する未処理の遷移が間隔条件付きの通常遷移であるので、現在のノード７ｊあるいは遷移先・元ノードが同系列関係であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノード７ｊが同系列関係であるので、現在のノード７ｊと遷移先・元ノード７ｅを同系列ノード集合に追加する。
【０２１２】
図２３Ｆの２段目に示すように、ＮＦＡ生成部１５２は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号５のノード７ｅを現在のノードとする。そして、ＮＦＡ生成部１５２は、現在のノード７ｅと接続する未処理の遷移がε遷移であるので、現在のノード７ｅと遷移先・元ノードがともに同系列関係であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、ともに同系列関係でないので、遷移先・元ノード７ｃ（ノード番号３）を未処理ノード集合に追加する。
【０２１３】
図２３Ｇの１段目に示すように、ＮＦＡ生成部１５２は、現在のノード７ｆと接続する未処理の遷移がなく、同系列ノード集合に含まれるノードが空であるので、同系列ノード集合を出力する。ここでは、ＮＦＡ生成部１５２は、ノード番号２、１２、１３、１４、１５、８、１１、１０、９、５のノードを同系列ノード集合として出力する。そして、ＮＦＡ生成部１５２は、出力後、同系列ノード集合を空にする。さらに、ＮＦＡ生成部１５２は、未処理ノード集合の中の最終状態ノードを除くノード番号の一番小さい未処理のノードを現在のノードとする。ここでは、ＮＦＡ生成部１５２は、未処理ノード集合の中のノード番号５のノード７ｅを現在のノードとする。ところが、ＮＦＡ生成部１５２は、現在のノード７ｅと接続する未処理の遷移がない。
【０２１４】
図２３Ｇの２段目に示すように、ＮＦＡ生成部１５２は、未処理ノード集合の中の最終状態ノードを除くノード番号の一番小さい未処理のノードを現在のノードとする。ここでは、ＮＦＡ生成部１５２は、未処理ノード集合の中のノード番号７のノード７ｅを現在のノードとする。そして、ＮＦＡ生成部１５２は、現在のノード７ｅと接続する遷移先・元ノードが同系列関係でないので、遷移先・元ノード７ｆ、７ｈを未処理ノード集合に追加する。ところが、ＮＦＡ生成部１５２は、ノード７ｆおよびノード７ｈと接続する未処理の遷移がないので、これらを現在のノードとする処理を終了する。
【０２１５】
図２３Ｇの３段目に示すように、ＮＦＡ生成部１５２は、未処理ノード集合に最終状態ノードを除く未処理のノードがないので、同系列ＮＦＡ探索処理を終了する。
【０２１６】
上述したように、ＮＦＡ生成部１５２は、図２３Ａ〜図２３Ｇに示す処理を実行することで、仮ＮＦＡから同系列ノード集合を出力する。すなわち、ＮＦＡ生成部１５２は、ノード番号１、３、４、６のノードを１組とした同系列ノード集合と、ノード番号２、１２、１３、１４、１５、８、１１、１０、９、５のノードを１組とした同系列ノード集合とを出力する。
【０２１７】
［別のパターンにおける同系列ＮＦＡ変換処理の説明］
次に、別のパターンにおける同系列ＮＦＡ変換処理について説明する。図２４Ａに示すように、ＮＦＡ生成部１５２は、同系列ノード集合の組が空であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、同系列ノード集合の組が存在するので空でないと判定する。
【０２１８】
図２４Ｂに示すように、ＮＦＡ生成部１５２は、同系列ノード集合の組から１組の同系列ノード集合を取り出す。すなわち、ＮＦＡ生成部１５２は、ノード番号１、３、４、６のノードを１組とした同系列ノード集合を取り出す。
【０２１９】
図２４Ｃの１段目に示すように、ＮＦＡ生成部１５２は、取り出した同系列ノード集合の未処理の１ノードを現在のノードとする。ここでは、ＮＦＡ生成部１５２は、同系列ノード集合の中から未処理のノードであるノード番号１のノード７ｂを現在のノードとする。そして、ＮＦＡ生成部１５２は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがあるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノード７ｂと接続されているノード７ａ（ノード番号０）が同系列ノード集合にない未処理のものであるので、未処理のものがあると判定する。そして、ＮＦＡ生成部１５２は、新しいノード７ｂ´を生成し、現在のノード７ｂの代わりに生成したノード７ｂ´と先の同系列ノード集合にないノード７ａとをそのままの遷移（ε遷移）で接続する。そして、ＮＦＡ生成部１５２は、現在のノード７ｂと生成したノード７ｂ´とこれら２つのノードの遷移方向の組とを境界ノード組集合に加える。かかる場合は、生成したノード７ｂ´が現在のノード７ｂの前方にある場合であるので、ＮＦＡ生成部１５２は、生成したノード７ｂ´から現在のノード７ｂへの遷移方向とする。
【０２２０】
図２４Ｃの２段目に示すように、ＮＦＡ生成部１５２は、同系列ノード集合の未処理の１ノードを現在のノードとする。ここでは、ＮＦＡ生成部１５２は、同系列ノード集合の中から未処理のノードであるノード番号３のノード７ｄを現在のノードとする。そして、ＮＦＡ生成部１５２は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがあるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノード７ｄと接続されているノード７ｅ、７ｆの中にノード番号５のノード７ｆが同系列ノード集合にない未処理のものであるので、未処理のものがあると判定する。そして、ＮＦＡ生成部１５２は、新しいノード７ｄ´を生成し、現在のノード７ｄの代わりに生成したノード７ｄ´と先の同系列ノード集合にないノード７ｄとをそのままの遷移（ε遷移）で接続する。そして、ＮＦＡ生成部１５２は、現在のノード７ｄと生成したノード７ｄ´とこれら２つのノードの遷移方向の組とを境界ノード組集合に加える。かかる場合は、生成したノード７ｄ´が現在のノード７ｄの後方にある場合であるので、ＮＦＡ生成部１５２は、現在のノード７ｄから、生成したノード７ｄ´への遷移方向とする。
【０２２１】
図２４Ｄの１段目に示すように、ＮＦＡ生成部１５２は、同系列ノード集合の未処理の１ノードを現在のノードとする。ここでは、ＮＦＡ生成部１５２は、同系列ノード集合の中から未処理のノードであるノード番号４のノード７ｅを現在のノードとする。そして、ＮＦＡ生成部１５２は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがあるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノード７ｅと接続されているノード７ｇ、７ｄの中に同系列ノード集合にない未処理のものがないので、未処理のものがないと判定する。
【０２２２】
図２４Ｄの２段目に示すように、ＮＦＡ生成部１５２は、同系列ノード集合の未処理の１ノードを現在のノードとする。ここでは、ＮＦＡ生成部１５２は、同系列ノード集合の中から未処理のノードであるノード番号６のノード７ｇを現在のノードとする。そして、ＮＦＡ生成部１５２は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがあるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、現在のノード７ｇと接続されているノード７ｅ、７ｈの中にノード番号７のノード７ｈが同系列ノード集合にない未処理のものであるので、未処理のものがあると判定する。そして、ＮＦＡ生成部１５２は、新しいノード７ｇ´を生成し、現在のノード７ｇの代わりに生成したノード７ｇ´と先の同系列ノード集合にないノード７ｈとをそのままの遷移（ε遷移）で接続する。そして、ＮＦＡ生成部１５２は、現在のノード７ｇと生成したノード７ｇ´とこれら２つのノードの遷移方向の組とを境界ノード組集合に加える。かかる場合は、生成したノード７ｇ´が現在のノード７ｇの後方にある場合であるので、ＮＦＡ生成部１５２は、現在のノード７ｇから、生成したノード７ｇ´への遷移方向とする。
【０２２３】
図２４Ｅの１段目に示すように、ＮＦＡ生成部１５２は、同系列ノード集合に未処理のノードがないので、同系列ノード集合のノードおよびそのノード間の遷移エッジすべてを１セットとして、系列数分だけ複製する。ここでは、系列数を３とすると、ＮＦＡ生成部１５２は、同系列ノード集合のノード７ｂ、７ｄ、７ｅ、７ｇおよびそのノード間の遷移エッジすべてを３系列数分複製する。そして、ＮＦＡ生成部１５２は、ノード間の遷移を各系列のイベントで受理する遷移に置き換える。すなわち、ＮＦＡ生成部１５２は、複製元の一段目の遷移を０系列のイベントで受理する遷移に置き換え、複製した２段目の遷移を１系列のイベントで受理する遷移に置き換え、複製した３段目の遷移を２系列のイベントで受理する遷移に置き換える。
【０２２４】
図２４Ｅの２段目に示すように、ＮＦＡ生成部１５２は、境界ノード組集合から未処理の１組の境界ノードの組を取り出す。ここでは、ＮＦＡ生成部１５２は、境界ノード組集合から、ノード番号が１´である生成ノード７ｂ´からノード番号が１である現在のノード７ｂへの遷移方向の境界ノードの組を取り出す。そして、ＮＦＡ生成部１５２は、取り出した１組の現在のノードと生成ノードと遷移方向に従い、現在のノードに対応する複製したすべてのノードと生成ノードを遷移方向どおりにすべてε遷移で接続する。ここでは、ＮＦＡ生成部１５２は、現在のノード７ｂに対応する、複製した３系列のノード７ｂと生成ノード７ｂ´を、生成ノード７ｂ´から現在のノード７ｂへの遷移方向どおりにすべてε遷移で接続する。
【０２２５】
図２４Ｆの１段目に示すように、ＮＦＡ生成部１５２は、境界ノード組集合から未処理の１組の境界ノードの組を取り出す。ここでは、ＮＦＡ生成部１５２は、境界ノード組集合から、ノード番号が３である現在のノード７ｄからノード番号が３´である生成ノード７ｄ´への遷移方向の境界ノードの組を取り出す。そして、ＮＦＡ生成部１５２は、取り出した１組の現在のノードと生成ノードと遷移方向に従い、現在のノードに対応する複製したすべてのノードと生成ノードを遷移方向どおりにすべてε遷移で接続する。ここでは、ＮＦＡ生成部１５２は、現在のノード７ｄに対応する、複製した３系列のノード７ｄと生成ノード７ｄ´を、現在のノード７ｄから生成ノード７ｄ´への遷移方向どおりにすべてε遷移で接続する。
【０２２６】
図２４Ｆの２段目に示すように、ＮＦＡ生成部１５２は、境界ノード組集合から未処理の１組の境界ノードの組を取り出す。ここでは、ＮＦＡ生成部１５２は、境界ノード組集合から、ノード番号が６である現在のノード７ｇからノード番号が６´である生成ノード７ｇ´への遷移方向の境界ノードの組を取り出す。そして、ＮＦＡ生成部１５２は、取り出した１組の現在のノードと生成ノードと遷移方向に従い、現在のノードに対応する複製したすべてのノードと生成ノードを遷移方向どおりにすべてε遷移で接続する。ここでは、ＮＦＡ生成部１５２は、現在のノード７ｇに対応する、複製した３系列のノード７ｇと生成ノード７ｇ´を、現在のノード７ｇから生成ノード７ｇ´への遷移方向どおりにすべてε遷移で接続する。
【０２２７】
図２４Ｇの１段目に示すように、さらに、ＮＦＡ生成部１５２は、同系列ノード集合の組が空であるか否かを判定する。ここでは、ＮＦＡ生成部１５２は、同系列ノード集合の組が存在するので空でないと判定する。そこで、ＮＦＡ生成部１５２は、同系列ノード集合の組から１組の同系列ノード集合を取り出す。すなわち、ＮＦＡ生成部１５２は、ノード番号２、１２、１３、１４、１５、８、１１、１０、９、５のノードを１組とした同系列ノード集合を取り出す。
【０２２８】
図２４Ｇの２段目に示すように、ＮＦＡ生成部１５２は、取り出した同系列ノード集合の未処理の１ノードであるノード番号２のノード７ｃを現在のノードとする。そして、ＮＦＡ生成部１５２は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のノード７ａがあるので、新しいノード７ｃ´を生成する。そして、ＮＦＡ生成部１５２は、現在のノード７ｃの代わりに生成したノード７ｃ´と先の同系列ノード集合にないノード７ａとをそのままの遷移（ε遷移）で接続する。そして、ＮＦＡ生成部１５２は、現在のノード７ｃと生成したノード７ｃ´とこれら２つのノードの遷移方向の組とを境界ノード組集合に加える。かかる場合は、生成したノード７ｃ´が現在のノード７ｃの前方にある場合であるので、ＮＦＡ生成部１５２は、生成したノード７ｃ´から現在のノード７ｃへの遷移方向とする。
【０２２９】
図２４Ｈの１段目に示すように、ＮＦＡ生成部１５２は、取り出した同系列ノード集合の未処理の１ノードであるノード番号８のノード７ｉを現在のノードとする。そして、ＮＦＡ生成部１５２は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のノード７ｈがあるので、新しいノード７ｉ´を生成する。そして、ＮＦＡ生成部１５２は、現在のノード７ｉの代わりに生成したノード７ｉ´と先の同系列ノード集合にないノード７ｈとをそのままの遷移（間隔条件付きの通常遷移）で接続する。そして、ＮＦＡ生成部１５２は、現在のノード７ｉと生成したノード７ｉ´とこれら２つのノードの遷移方向の組とを境界ノード組集合に加える。かかる場合は、生成したノード７ｉ´が現在のノード７ｉの前方にある場合であるので、ＮＦＡ生成部１５２は、生成したノード７ｉ´から現在のノード７ｉへの遷移方向とする。
【０２３０】
図２４Ｈの２段目に示すように、ＮＦＡ生成部１５２は、取り出した同系列ノード集合の未処理の１ノードであるノード番号５のノード７ｆを現在のノードとする。そして、ＮＦＡ生成部１５２は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のノード７ｄ´があるので、新しいノード７ｆ´を生成する。そして、ＮＦＡ生成部１５２は、現在のノード７ｆの代わりに生成したノード７ｆ´と先の同系列ノード集合にないノード７ｄ´とをそのままの遷移（ε遷移）で接続する。そして、ＮＦＡ生成部１５２は、現在のノード７ｆと生成したノード７ｆ´とこれら２つのノードの遷移方向の組とを境界ノード組集合に加える。かかる場合は、生成したノード７ｆ´が現在のノード７ｆの前方にある場合であるので、ＮＦＡ生成部１５２は、生成したノード７ｆ´から現在のノード７ｆへの遷移方向とする。
【０２３１】
図２４Ｉの１段目に示すように、ＮＦＡ生成部１５２は、同系列ノード集合に未処理のノードがないので、同系列ノード集合のノードおよびそのノード間の遷移エッジすべてを１セットとして、系列数分だけ複製する。ここでは、系列数を３とすると、ＮＦＡ生成部１５２は、同系列ノード集合のノード７ｃ、７ｍ、７ｎ、７ｏ、７ｐ、７ｌ、７ｋ、７ｊ、７ｆ、７ｉおよびそのノード間の遷移エッジすべてを３系列数分複製する。そして、ＮＦＡ生成部１５２は、ノード間の遷移を各系列のイベントで受理する遷移に置き換える。
【０２３２】
図２４Ｊに示すように、ＮＦＡ生成部１５２は、境界ノード組集合から未処理の１組である、ノード番号が２´である生成ノード７ｃ´からノード番号が２である現在のノード７ｃへの遷移方向の境界ノードの組を取り出す。そして、ＮＦＡ生成部１５２は、取り出した１組の現在のノードと生成ノードと遷移方向に従い、現在のノードに対応する複製したすべてのノードと生成ノードを遷移方向どおりにすべてε遷移で接続する。
【０２３３】
図２４Ｋに示すように、ＮＦＡ生成部１５２は、境界ノード組集合から未処理の１組である、ノード番号が８´である生成ノード７ｉ´からノード番号が８である現在のノード７ｉへの遷移方向の境界ノードの組を取り出す。そして、ＮＦＡ生成部１５２は、取り出した１組の現在のノードと生成ノードと遷移方向に従い、現在のノードに対応する複製したすべてのノードと生成ノードを遷移方向どおりにすべてε遷移で接続する。
【０２３４】
図２４Ｌに示すように、ＮＦＡ生成部１５２は、境界ノード組集合から未処理の１組である、ノード番号が５´である生成ノード７ｆ´からノード番号が５である現在のノード７ｆへの遷移方向の境界ノードの組を取り出す。そして、ＮＦＡ生成部１５２は、取り出した１組の現在のノードと生成ノードと遷移方向に従い、現在のノードに対応する複製したすべてのノードと生成ノードを遷移方向どおりにすべてε遷移で接続する。
【０２３５】
図２４Ｍに示すように、ＮＦＡ生成部１５２は、同系列ノード集合の組が空なので、系列の値の大小関係を保ち、境界ノード組集合の遷移元が小さいノード番号となるよう、ユニークなノード番号を振りなおす。
【０２３６】
［実施例に係る照合部におけるパターン照合の処理手順］
次に、実施例に係る照合部１５３におけるパターン照合の処理手順を、図２５〜図２７を参照して説明する。図２５は照合部におけるパターン照合の主処理の手順を示し、図２６は通常遷移を発動する処理の手順を示し、図２７は全てのε遷移とε＝遷移を発動する処理の手順を示す。
【０２３７】
［パターン照合の主処理の手順］
まず、パターン照合の主処理の手順について、図２５を参照して説明する。図２５は、実施例に係る照合部におけるパターン照合の主処理の手順を示すフローチャートである。例えば、図２５に示す処理は、イベントパターン１４１とイベントストリーム１４３とを取得した後に、ＮＦＡ１４２を生成したことを契機にして実行される。なお、イベントストリーム１４３における系列に対応する各ＩＤの現在のイベントをＳ［ｉ］［ＩＤ］とする。ここで、ｉは現在のイベント位置の値、言い換えると時刻の値を示す。ＩＤは系列の値を示す。
【０２３８】
まず、照合部１５３は、現在のイベント位置ｉの値を０に設定する（ステップＳ５１）。そして、照合部１５３は、いずれかのＩＤでイベントＳ［ｉ］［ＩＤ］が存在するか否かを判定する（ステップＳ５２）。
【０２３９】
いずれのＩＤでもイベントＳ［ｉ］［ＩＤ］が存在しない場合（ステップＳ５２；Ｎｏ）、照合部１５３は、主処理を終了する。一方、いずれかのＩＤでイベントＳ［ｉ］［ＩＤ］が存在する場合（ステップＳ５２；Ｙｅｓ）、照合部１５３は、イベントストリーム１４３からイベントＳ［ｉ］［ＩＤ］を読み込む（ステップＳ５３）。
【０２４０】
続いて、照合部１５３は、読み込んだイベントＳ［ｉ］［ＩＤ］に関するＮＦＡ（Ｎ（Ｐ））の全ての通常遷移を発動する（ステップＳ５４）。ここで、ＮＦＡ（Ｎ（Ｐ））は、ＮＦＡ１４２に対応する。
【０２４１】
さらに、照合部１５３は、ＮＦＡ（Ｎ（Ｐ））の全てのε遷移とε＝遷移を発動する（ステップＳ５５）。そして、照合部１５３は、現在のイベント位置ｉの値に１を加算し（ステップＳ５６）、ステップＳ５２に移行する。
【０２４２】
［通常遷移を発動する処理の手順］
次に、図２５のステップＳ５４に示した通常遷移を発動する処理について、図２６を参照して説明する。図２６は、通常遷移を発動する処理の手順を示すフローチャートである。
【０２４３】
図２６に示すように、照合部１５３は、状態ｊの値を１に設定し、遷移先状態ｋの値を０に設定する（ステップＳ５１１）。ここで、状態ｊはＮＦＡ１４２のノード番号、すなわち状態番号に対応するものである。また、遷移先状態ｋは遷移先のノード番号、すなわち遷移先の状態番号に対応するものである。
【０２４４】
そして、照合部１５３は、状態ｊが存在するか否かを判定し（ステップＳ５１２）、状態ｊが存在しない場合には（ステップＳ５１２；Ｎｏ）、処理を終了する。一方、照合部１５３は、状態ｊが存在する場合には（ステップＳ５１２；Ｙｅｓ）、状態ｊからイベントＳ［ｉ］［ＩＤ］に関する通常遷移が出ているか否かを判定する（ステップＳ５１３）。通常遷移が出ていない場合には（ステップＳ５１３；Ｎｏ）、状態ｊの値に１を加算し（ステップＳ５１４）、ステップＳ５１２に移行する。
【０２４５】
一方、通常遷移が出ている場合には（ステップＳ５１３；Ｙｅｓ）、照合部１５３は、遷移種別判定テーブルを用いて、イベントＳ［ｉ］［ＩＤ］に対応する遷移種別を判定する（ステップＳ５１３Ａ）。具体的には、照合部１５３は、状態ｊから出ている通常遷移がＩＤ指定遷移であるか否かを判定する。そして、照合部１５３は、ＩＤ指定遷移であれば、イベントとＩＤとがそれぞれ一致するか否かによってイベントＳ［ｉ］［ＩＤ］に対応する遷移種別を判定する。すなわち、照合部１５３は、出ている通常遷移に係るイベントとイベントＳ［ｉ］［ＩＤ］が一致し、且つ出ている通常遷移に係るＩＤと現在のイベントＳ［ｉ］［ＩＤ］の発生したＩＤが一致する場合、出ている通常遷移をイベントに対応する遷移種別とする。かかる遷移種別は、間隔条件付き通常遷移または間隔条件なし通常遷移を示す。また、照合部１５３は、出ている通常遷移に係るイベントとイベントＳ［ｉ］［ＩＤ］が一致しないか、または出ている通常遷移に係るＩＤと現在のイベントＳ［ｉ］［ＩＤ］の発生したＩＤが一致しない場合、イベントに対応する遷移種別を遷移なしとする。また、照合部１５３は、状態ｊから出ている通常遷移がＩＤ指定遷移でなければ、出ている通常遷移をイベントに対応する遷移種別とする。
【０２４６】
そして、照合部１５３は、イベントに対応する遷移種別が遷移なしであるか否かを判定する（ステップＳ５１３Ｂ）。イベントに対応する遷移種別が遷移なしであると判定した場合（ステップＳ５１３Ｂ；Ｙｅｓ）、照合部１５３は、ステップＳ５１４に移行する。一方、イベントに対応する遷移種別が遷移なしでないと判定した場合（ステップＳ５１３Ｂ；Ｎｏ）、照合部１５３は、イベントに対応する遷移種別が間隔条件付きの通常遷移であるか否かを判定する（ステップＳ５１３Ｃ）。そして、照合部１５３は、間隔条件付きの通常遷移でない場合には（ステップＳ５１３Ｃ；Ｎｏ）、仮リストを空に設定する（ステップＳ５１５）。ここで、仮リストはイベントリストを生成するための一時的に用いられる仮のリストであり、イベントリストと同じ構成を有する。また、イベントリストは、イベントを受理したノード毎に対応付けられ、イベントの受理状態が設定される。受理状態には、例えば＠番号位置と最終受理位置とが対応付けられる。＠番号位置には、＠番号が割り当てられた受理時刻保持ノードで受理したイベントのイベント位置を書き込む領域を指す。また、最終受理位置とは、現段階で最終的に受理したイベントのイベント位置を書き込む領域を指す。
【０２４７】
そして、照合部１５３は、状態ｊの通常遷移先の状態番号を状態ｋに設定する（ステップＳ５１６）。そして、照合部１５３は、状態ｋが＠番号が割り当てられているか否かを判定する（ステップＳ５１７）。すなわち、照合部１５３は、状態ｋのノード番号に対応するノードが受理時刻保持ノードであるか否かを判定する。状態ｋが＠番号が割り当てられている場合には（ステップＳ５１７；Ｙｅｓ）、照合部１５３は、仮リストの＠番号位置に現在のイベント位置ｉを書き込み（ステップＳ５１８）、ステップＳ５１９に移行する。そして、照合部１５３は、仮リストの最終受理位置に現在のイベント位置ｉを書き込み、状態ｋのイベントリストとして追加する（ステップＳ５１９）。そして、照合部１５３は、ステップＳ５２４に移行する。
【０２４８】
一方、照合部１５３は、間隔条件付きの通常遷移である場合には（ステップＳ５１３Ｃ；Ｙｅｓ）、状態ｊに未処理のイベントリストがあるか否かを判定する（ステップＳ５２０）。状態ｊに未処理のイベントリストがある場合には（ステップＳ５２０；Ｙｅｓ）、照合部１５３は、未処理のイベントリストを選択し、選択したイベントリストの最終受理位置と現在のイベント位置ｉが間隔条件を満たすか否かを判定する（ステップＳ５２１）。そして、間隔条件を満たさない場合には（ステップＳ５２１；Ｎｏ）、照合部１５３は、選択したイベントリストを削除し（ステップＳ５２２）、状態ｊの処理を継続すべく、ステップＳ５２０に移行する。一方、間隔条件を満たす場合には（ステップＳ５２１；Ｙｅｓ）、照合部１５３は、選択したイベントリストを仮リストにコピーし（ステップＳ５２３）、ステップＳ５１６に移行する。
【０２４９】
すなわち、照合部１５３は、状態ｊの通常遷移先の状態番号を状態ｋに設定する。そして、照合部１５３は、状態ｋが＠番号が割り当てられている場合には、仮リストの＠番号位置に現在のイベント位置ｉを上書きし、仮リストの最終受理位置に現在のイベント位置ｉを上書きし、状態ｋのイベントリストとして追加する。一方、照合部１５３は、状態ｋが＠番号が割り当てられていない場合には、仮リストの最終受理位置に現在のイベント位置ｉを上書きし、状態ｋのイベントリストとして追加する。
【０２５０】
続いて、照合部１５３は、状態ｋが最終状態であり、且つイベントリストがあるか否かを判定する（ステップＳ５２４）。状態ｋが最終状態であり、且つイベントリストがある場合には（ステップＳ５２４；Ｙｅｓ）、照合部１５３は、現在のイベント位置ｉを通知し、状態ｋのイベントリストを削除する（ステップＳ５２５）。すなわち、照合部１５３は、イベント位置ｉをイベントパターンの終了時刻として通知する。そして、照合部１５３は、状態ｊの処理を継続すべく、ステップＳ５２０に移行する。一方、状態ｋが最終状態でない場合、またはイベントリストがない場合には（ステップＳ５２４；Ｎｏ）、照合部１５３は、状態ｊの処理を継続すべく、ステップＳ５２０に移行する。
【０２５１】
［全てのε遷移とε＝遷移を発動する処理の手順］
次に、図２５のステップＳ５５に示した全てのε遷移とε＝遷移を発動する処理について、図２７を参照して説明する。図２７は、全てのε遷移とε＝遷移を発動する処理の手順を示すフローチャートである。
【０２５２】
図２７に示すように、照合部１５３は、状態ｊの値に１を設定する（ステップＳ５５１）。そして、照合部１５３は、状態ｊが存在するか否かを判定する（ステップＳ５５２）。状態ｊが存在しない場合には（ステップＳ５５２；Ｎｏ）、照合部１５３は処理を終了する。
【０２５３】
一方、状態ｊが存在する場合には（ステップＳ５５２；Ｙｅｓ）、照合部１５３は状態ｊが合流ノードであるか否かを判定する（ステップＳ５５３）。状態ｊが合流ノードでない場合には（ステップＳ５５３；Ｎｏ）、照合部１５３は状態ｊからε遷移が出ているか否かを判定する（ステップＳ５５４）。状態ｊからε遷移が出ていない場合には（ステップＳ５５４；Ｎｏ）、照合部１５３は状態ｊの値に１を加算し（ステップＳ５５５）、ステップＳ５５２に移行する。一方、状態ｊからε遷移が出ている場合には（ステップＳ５５４；Ｙｅｓ）、照合部１５３は状態ｊの全てのイベントリストを全ての遷移先の状態のイベントリストとして追加し、状態ｊのイベントリストを削除する（ステップＳ５５６）。
【０２５４】
続いて、照合部１５３は、状態ｋが最終状態であり、且つイベントリストがあるか否かを判定する（ステップＳ５５７）。状態ｋが最終状態であり、且つイベントリストがある場合には（ステップＳ５５７；Ｙｅｓ）、照合部１５３は、現在のイベント位置ｉを照合結果として通知し、状態ｋのイベントリストを削除する（ステップＳ５５８）。すなわち、照合部１５３は、照合が完了した結果として、イベントパターンの終了時刻を通知する。そして、照合部１５３は、状態ｊの処理を継続すべく、ステップＳ５５５に移行する。一方、状態ｋが最終状態でない場合、またはイベントリストがない場合には（ステップＳ５５７；Ｎｏ）、照合部１５３は、状態ｊの処理を継続すべく、ステップＳ５５５に移行する。
【０２５５】
一方、状態ｊが合流ノードである場合には（ステップＳ５５３；Ｙｅｓ）、照合部１５３は、状態ｊのε＝遷移元のイベントリストの、状態ｊで指定された指定＠番号の＠番号位置のイベント位置が一致しているイベントリストを探索する。そして、照合部１５３は、探索の結果、＠番号位置のイベント位置が一致しているイベントリストの全ての組み合わせに対して、イベントリストを結合し、結合したイベントリストを状態ｊに追加する（ステップＳ５５９）。
【０２５６】
そして、照合部１５３は、状態ｊの各ε＝遷移元のイベントリストの、状態ｊで指定された指定＠番号の＠番号位置のイベント位置を取り出す。そして、照合部１５３は、取り出したイベント位置が｛「現在のイベント位置」−「状態ｊの各＠番号に対応するタイムアウト長」｝以下の場合、タイムアウトであると判断し、そのイベントリストを削除する（ステップＳ５６０）。
【０２５７】
続いて、照合部１５３は、状態ｊが最終状態であり、且つイベントリストがあるか否かを判定する（ステップＳ５６１）。状態ｊが最終状態であり、且つイベントリストがある場合には（ステップＳ５６１；Ｙｅｓ）、照合部１５３は、現在のイベント位置ｉを照合結果として通知し、状態ｊのイベントリストを削除する（ステップＳ５６２）。すなわち、照合部１５３は、照合が完了した結果として、イベントパターンの終了時刻を通知する。そして、照合部１５３は、状態ｊの処理を継続すべく、ステップＳ５５４に移行する。一方、状態ｊが最終状態でない場合、またはイベントリストがない場合には（ステップＳ５６１；Ｎｏ）、照合部１５３は、状態ｊの処理を継続すべく、ステップＳ５５４に移行する。
【０２５８】
［パターン照合処理の一例］
次に、図を用いて照合部１５３の処理を説明する。図２８Ａ〜図２８Ｎは、照合部の処理を説明するための図である。なお、図２８Ａ〜図２８Ｎの説明では、状態番号によって、各ノードを区別して説明する。以下では、状態番号１〜４９のノードを、状態１〜４９として説明する。また、ＮＦＡ１４２と比較するイベントストリーム１４３を、図３に示すものとし、系列に対応する各ＩＤの各イベントをＳ［ｉ］［ＩＤ］（ｉ＝０〜１０）（ＩＤ＝０〜２）に保持するものとする。
【０２５９】
図２８Ａに示すように、イベントパターン１４３のデータ構造を、符号２０４ｐに示すものとする。イベントパターン１４３は、任意の系列でイベントＡが発生し、その後２以内にＡと同じ系列でイベントＢが発生するパターンを有する。そして、イベントパターン１４３は、任意の系列で発生したイベントＡの発生後４以内に任意の系列でイベントＣが発生するパターンを有する。そして、イベントパターン１４３は、イベントＣの発生後３以内且つイベントＤの発生後５以内且つイベントＢの発生後４以内にイベントＣと同じ系列でイベントＥが発生するパターンを有する。このイベントパターン１４３を入力としてＮＦＡ生成部１５２によって生成されたＮＦＡは、符号２０４ｎに示すものとなる。
【０２６０】
図２８Ａの１段目に示すように、照合部１５３は、現在のイベント位置ｉの値を０に設定し、イベントストリーム１４３からイベント位置０および系列０のイベントＳ［０］［０］、すなわちイベント「Ａ」を読み込む。言い換えれば、照合部１５３は、時刻０のときの系列０のイベント「Ａ」を読み込む。
【０２６１】
図２８Ａの２段目に示すように、照合部１５３は、状態ｊの値と遷移先状態ｋの値を初期化し、状態ｊの値を１に設定し、遷移先状態ｋの値を０に設定する。照合部１５３は、状態ｊの値を１ずつ加算し、状態ｊからイベント「Ａ」に関する通常遷移が出ているか否かを判定する。ここでは、状態２からイベント「Ａ」に関する間隔条件なしの通常遷移が出ている。そこで、照合部１５３は、遷移種別判定テーブルを用いてイベント「Ａ」に対応する遷移種別を判定する。ここでは、照合部１５３は、状態２から出ている通常遷移がＩＤ指定遷移であるので、読み込んだイベントと状態から出ている通常遷移に関して、イベントとＩＤとがそれぞれ一致するか否かを判定する。照合部１５３は、イベントについてともに「Ａ」であり、ＩＤについてともに「０」であるので、イベントとＩＤとがそれぞれ一致すると判定する。そこで、照合部１５３は、出ている間隔条件なしの通常遷移をイベントに対応する遷移種別とする。したがって、照合部１５３は、イベントに対応する遷移種別が間隔条件なしの通常遷移であるので、照合部１５３は、イベントの受理状態を設定する仮リストを空に設定し、状態ｋに状態３の通常遷移先である状態９を設定する。そして、照合部１５３は、状態９に＠番号０が割り当てられているので、仮リストの＠番号位置に現在のイベント位置０を書き込む。照合部１５３は、仮リストの最終受理位置に現在のイベント位置０を設定する。そして、照合部１５３は、仮リストを状態９のイベントリストｒ１として追加する。
【０２６２】
なお、照合部１５３は、状態３、状態４からイベント「Ａ」に関する通常遷移が出ているが、出ている通常遷移がＩＤ指定遷移であり、出ている通常遷移のＩＤと読み込んだイベントのＩＤとが一致していないので、遷移なしとする。
【０２６３】
その後、照合部１５３は、状態３から状態４９まで各状態からイベント「Ａ」に関する通常遷移が出ていないので、照合部１５２は、系列０の現在のイベント位置０（時刻０）のイベント「Ａ」に関する全ての通常遷移の発動を終了する。
【０２６４】
図２８Ｂの３段目に示すように、照合部１５３は、状態ｊの値を１ずつ増やしながら、状態ｊから出ている全てのε遷移とε＝遷移の発動を実行する。照合部１５３は、状態９からε遷移が出ているので、状態９のイベントリストｒ１を遷移先の状態１３、１７、１８、１９のイベントリストｒ１´として追加し、状態９のイベントリストｒ１を削除する。そして、照合部１５３は、状態４９まで処理を完了すると、全てのε遷移とε＝遷移の発動を終了する。
【０２６５】
その後、照合部１５２は、現在のイベント位置０（時刻０）に他の系列のイベントがないので、現在のイベント位置０（時刻０）の照合を終了する。
【０２６６】
図２８Ｃの１段目に示すように、照合部１５３は、現在のイベント位置ｉの値を１に設定し、イベントストリーム１４３からイベント位置１および系列１のイベントＳ［１］［１］、すなわちイベント「Ａ」を読み込む。言い換えれば、照合部１５３は、時刻１のときの系列１のイベント「Ａ」を読み込む。
【０２６７】
図２８Ｃの２段目に示すように、照合部１５３は、状態３からイベント「Ａ」に関する間隔条件なしの通常遷移が出ているので、遷移種別判定テーブルを用いてイベント「Ａ」に対応する遷移種別を判定する。ここでは、照合部１５３は、状態３から出ている通常遷移がＩＤ指定遷移であるので、読み込んだイベントと状態から出ている通常遷移に関して、イベントとＩＤとがそれぞれ一致するか否かを判定する。照合部１５３は、イベントについてともに「Ａ」であり、ＩＤについてともに「１」であるので、イベントとＩＤとがそれぞれ一致すると判定する。そこで、照合部１５３は、出ている間隔条件なしの通常遷移をイベントに対応する遷移種別とする。したがって、照合部１５３は、イベントに対応する遷移種別が間隔条件なしの通常遷移であるので、照合部１５３は、イベントの受理状態を設定する仮リストを空に設定する。そして、照合部１５３は、状態３の通常遷移先である状態１０に＠番号０が割り当てられているので、仮リストの＠番号位置に現在のイベント位置１を書き込む。照合部１５３は、仮リストの最終受理位置に現在のイベント位置１を設定する。そして、照合部１５３は、仮リストを状態１０のイベントリストｒ２として追加する。
【０２６８】
その後、照合部１５２は、状態４から状態４９まで各状態からイベント「Ａ」に関する通常遷移が出ていないので、照合部１５２は、系列１の現在のイベント位置１（時刻１）のイベント「Ａ」に関する全ての通常遷移の発動を終了する。
【０２６９】
図２８Ｃの３段目に示すように、照合部１５３は、状態ｊの値を１ずつ増やしながら、状態ｊから出ている全てのε遷移とε＝遷移の発動を実行する。照合部１５３は、状態１０からε遷移が出ているので、状態１０のイベントリストｒ２を遷移先の状態１４、１７、１８、１９のイベントリストｒ２´として追加し、状態１０のイベントリストｒ２を削除する。そして、照合部１５３は、状態４９まで処理を完了すると、全てのε遷移とε＝遷移の発動を終了する。
【０２７０】
その後、照合部１５２は、現在のイベント位置１（時刻１）に他の系列のイベントがないので、現在のイベント位置１（時刻１）の照合を終了する。
【０２７１】
図２８Ｄの１段目に示すように、照合部１５３は、現在のイベント位置ｉの値を２に設定し、イベントストリーム１４３からイベント位置２および系列０のイベントＳ［２］［０］、すなわちイベント「Ｂ」を読み込む。言い換えれば、照合部１５３は、時刻２のときの系列０のイベント「Ｂ」を読み込む。
【０２７２】
図２８Ｄの２段目に示すように、照合部１５３は、状態１３からイベント「Ｂ」に関する間隔条件付き通常遷移が出ているので、遷移種別判定テーブルを用いてイベント「Ｂ」に対応する遷移種別を判定する。ここでは、照合部１５３は、状態１３から出ている通常遷移がＩＤ指定遷移であるので、読み込んだイベントと状態から出ている通常遷移に関して、イベントとＩＤとがそれぞれ一致するか否かを判定する。照合部１５３は、イベントについてともに「Ｂ」であり、ＩＤについてともに「０」であるので、イベントとＩＤとがそれぞれ一致すると判定する。そこで、照合部１５３は、出ている間隔条件付き通常遷移をイベントに対応する遷移種別とする。したがって、照合部１５３は、イベントに対応する遷移種別が間隔条件付き通常遷移であり、状態１３に未処理のイベントリストがあるので、イベントリストの最終受理位置と現在のイベント位置が間隔条件を満たすか否かを判定する。ここでは、照合部１５３は、イベントリストの最終受理位置が０であり、現在のイベント位置が２であるので、間隔条件付き通常遷移の間隔条件２を満たすと判定する。そして、照合部１５３は、イベントリストの最終受理位置に現在のイベント位置２を設定し、状態１０のイベントリストｒ３として追加する。
【０２７３】
その後、照合部１５２は、状態１４から状態４９まで各状態からイベント「Ｂ」に関する通常遷移が出ていないので、照合部１５２は、系列０の現在のイベント位置２（時刻２）のイベント「Ｂ」に関する全ての通常遷移の発動を終了する。
【０２７４】
図２８Ｄの３段目に示すように、照合部１５３は、状態ｊの値を１ずつ増やしながら、状態ｊから出ている全てのε遷移とε＝遷移の発動を実行する。照合部１５３は、状態２０からε遷移が出ているので、状態２０のイベントリストｒ３を遷移先の状態２４のイベントリストｒ３´として追加し、状態２０のイベントリストｒ３を削除する。そして、照合部１５３は、状態４９まで処理を完了すると、全てのε遷移とε＝遷移の発動を終了する。
【０２７５】
その後、照合部１５２は、現在のイベント位置２（時刻２）に他の系列のイベントがないので、現在のイベント位置２（時刻２）の照合を終了する。
【０２７６】
図２８Ｅの１段目に示すように、照合部１５３は、現在のイベント位置ｉの値を３に設定し、イベントストリーム１４３からイベント位置３および系列０のイベントＳ［３］［０］、すなわちイベント「Ｃ」を読み込む。また、照合部１５３は、イベントストリーム１４３から現在のイベント位置３および系列１のイベントＳ［３］［１］、すなわちイベント「Ｂ」を読み込む。そして、照合部１５３は、系列０のイベント「Ｃ」、系列１のイベント「Ｂ」の順に以下の照合処理を行う。
【０２７７】
図２８Ｅの２段目に示すように、系列０のイベント「Ｃ」について、照合部１５３は、状態１７からイベント「Ｃ」に関する間隔条件付き通常遷移が出ているので、遷移種別判定テーブルを用いてイベント「Ｃ」に対応する遷移種別を判定する。ここでは、照合部１５３は、状態１７から出ている通常遷移がＩＤ指定遷移であり、読み込んだイベントと状態から出ている通常遷移に関して、イベントとＩＤとがそれぞれ一致しているので、出ている間隔条件付き通常遷移をイベントに対応する遷移種別とする。したがって、照合部１５３は、イベントに対応する遷移種別が間隔条件付き通常遷移であり、状態１７に未処理のイベントリストがあるので、イベントリストの最終受理位置と現在のイベント位置が間隔条件を満たすか否かを判定する。ここでは、照合部１５３は、１つのイベントリストの最終受理位置が０であり、現在のイベント位置が３であるので、間隔条件付き通常遷移の間隔条件４を満たすと判定する。また、照合部１５３は、もう１つのイベントリストの最終受理位置が１であり、現在のイベント位置が３であるので、間隔条件付き通常遷移の間隔条件４を満たすと判定する。そして、照合部１５３は、それぞれのイベントリストの最終受理位置に現在のイベント位置３を設定し、それぞれのイベントリストを通常遷移先の状態２９のイベントリストｒ４として追加する。
【０２７８】
系列１のイベント「Ｂ」についても、照合部１５３は、系列０のイベント「Ｃ」の場合と同様に処理し、状態１４のイベントリストの最終受理位置に現在のイベント位置３を設定し、イベントリストを通常遷移先の状態２１のイベントリストｒ５として追加する。
【０２７９】
図２８Ｅの３段目に示すように、系列０のイベント「Ｃ」について、照合部１５３は、状態ｊの値を１ずつ増やしながら、状態ｊから出ている全てのε遷移とε＝遷移の発動を実行する。照合部１５３は、状態２９からε遷移が出ているので、状態２９のイベントリストｒ４を遷移先の状態３２のイベントリストｒ４´として追加し、状態２９のイベントリストｒ４を削除する。
【０２８０】
系列１のイベント「Ｂ」についても、照合部１５３は、系列１のイベント「Ｃ」の場合と同様に処理し、状態２１のイベントリストｒ５を遷移先の状態２４のイベントリストｒ５´として追加し、状態２１のイベントリストｒ５を削除する。そして、照合部１５３は、状態４９まで処理を完了すると、全てのε遷移とε＝遷移の発動を終了する。
【０２８１】
その後、照合部１５２は、現在のイベント位置３（時刻３）に他の系列のイベントがないので、現在のイベント位置３（時刻３）の照合を終了する。
【０２８２】
図２８Ｆの１段目に示すように、照合部１５３は、現在のイベント位置ｉの値を４に設定し、イベントストリーム１４３からイベント位置４および系列０のイベントＳ［４］［０］、すなわちイベント「Ａ」を読み込む。また、照合部１５３は、イベントストリーム１４３から現在のイベント位置４および系列２のイベントＳ［４］［２］、すなわちイベント「Ｄ」を読み込む。そして、照合部１５３は、系列０のイベント「Ａ」、系列２のイベント「Ｄ」の順に以下の照合処理を行う。
【０２８３】
図２８Ｆの２段目に示すように、系列０のイベント「Ａ」について、照合部１５３は、状態２からイベント「Ａ」に関する間隔条件なしの通常遷移が出ているので、遷移種別判定テーブルを用いてイベント「Ｃ」に対応する遷移種別を判定する。ここでは、照合部１５３は、状態２から出ている通常遷移がＩＤ指定遷移であり、読み込んだイベントと状態から出ている通常遷移に関して、イベントとＩＤとがそれぞれ一致しているので、出ている間隔条件なし通常遷移をイベントに対応する遷移種別とする。したがって、照合部１５３は、イベントに対応する遷移種別が間隔条件なしの通常遷移であり、通常遷移先の状態９に＠番号０が割り当てられているので、イベントリストの＠番号位置に現在のイベント位置４を書き込み、最終受理位置に現在のイベント位置４を設定する。そして、照合部１５３は、状態９のイベントリストｒ６として追加する。
【０２８４】
系列２のイベント「Ｄ」については、照合部１５３は、系列０のイベント「Ａ」の場合と同様に処理し、状態８から出ているイベント「Ｄ」に関する間隔条件なしの通常遷移が出ているので、遷移種別判定テーブルを用いてイベント「Ｄ」に対応する遷移種別を判定する。ここでは、照合部１５３は、状態８から出ている間隔条件なし通常遷移をイベントに対応する遷移種別とする。そして、照合部１５３は、イベントに対応する遷移種別が間隔条件なしの通常遷移であり、通常遷移先の状態４０に＠番号が割り当てられていないので、イベントリストの最終受理位置に現在のイベント位置４を設定する。そして、照合部１５３は、状態４０のイベントリストｒ７として追加する。
【０２８５】
図２８Ｆの３段目に示すように、系列０のイベント「Ａ」について、照合部１５３は、状態ｊの値を１ずつ増やしながら、状態ｊから出ている全てのε遷移とε＝遷移の発動を実行する。照合部１５３は、状態９からε遷移が出ているので、状態９のイベントリストｒ６を遷移先の状態１３、１８、１７、１９のイベントリストｒ６´として追加し、状態９のイベントリストｒ６を削除する。
【０２８６】
系列２のイベント「Ｄ」についても、照合部１５３は、系列０のイベント「Ａ」の場合と同様に処理し、状態４０のイベントリストｒ７を遷移先の状態４３のイベントリストｒ７´として追加し、状態４０のイベントリストｒ７を削除する。そして、照合部１５３は、状態４９まで処理を完了すると、全てのε遷移とε＝遷移の発動を終了する。
【０２８７】
その後、照合部１５２は、現在のイベント位置４（時刻４）に他の系列のイベントがないので、現在のイベント位置４（時刻４）の照合を終了する。
【０２８８】
図２８Ｇの１段目に示すように、照合部１５３は、現在のイベント位置ｉの値を５に設定し、イベントストリーム１４３からイベント位置５および系列０のイベントＳ［５］［０］、すなわちイベント「Ｅ」を読み込む。また、照合部１５３は、イベントストリーム１４３から現在のイベント位置５および系列２のイベントＳ［５］［２］、すなわちイベント「Ｃ」を読み込む。そして、照合部１５３は、系列０のイベント「Ｅ」、系列２のイベント「Ｃ」の順に以下の照合処理を行う。
【０２８９】
図２８Ｇの２段目に示すように、系列０のイベント「Ｅ」について、照合部１５３は、状態２４からイベント「Ｅ」に関する間隔条件なしの通常遷移が出ているので、遷移種別判定テーブルを用いてイベント「Ｅ」に対応する遷移種別を判定する。ここでは、照合部１５３は、状態２４から出ている通常遷移がＩＤ指定なし遷移であるので、出ている間隔条件なし通常遷移をイベントに対応する遷移種別とする。したがって、照合部１５３は、イベントに対応する遷移種別が間隔条件なしの通常遷移であり、通常遷移先の状態２５に＠番号１が割り当てられているので、イベントリストの＠番号位置に現在のイベント位置５を書き込み、最終受理位置に現在のイベント位置５を設定する。そして、照合部１５３は、状態２５のイベントリストｒ８として追加する。
【０２９０】
続いて、照合部１５３は、状態３２からイベント「Ｅ」に関する間隔条件付き通常遷移が出ているので、イベント「Ｅ」に対応する遷移種別を判定する。ここでは、照合部１５３は、状態３２から出ている通常遷移がＩＤ指定遷移であり、読み込んだイベントと状態から出ている通常遷移に関して、イベントとＩＤとがそれぞれ一致しているので、出ている間隔条件付き通常遷移をイベントに対応する遷移種別とする。したがって、照合部１５３は、イベントに対応する遷移種別が間隔条件付き通常遷移であり、状態３２に未処理のイベントリストがあるので、イベントリストの最終受理位置と現在のイベント位置が間隔条件を満たすか否かを判定する。ここでは、照合部１５３は、２つのイベントリストとも間隔条件３を満たすと判定する。そして、照合部１５３は、通常遷移先の状態３５に＠番号１が割り当てられているので、イベントリストの＠番号位置に現在のイベント位置５を書き込み、最終受理位置に現在のイベント位置５を設定する。そして、照合部１５３は、状態３５のイベントリストｒ９として追加する。
【０２９１】
系列２のイベント「Ｃ」については、照合部１５３は、系列０のイベント「Ｅ」の場合と同様に処理し、状態１９から出ているイベント「Ｃ」に関する間隔条件付き通常遷移が出ているので、イベント「Ｃ」に対応する遷移種別を判定する。ここでは、照合部１５３は、状態１９から出ている間隔条件付き通常遷移をイベントに対応する遷移種別とする。そして、照合部１５３は、状態１９の未処理のイベントリストｒ１´を選択し、選択したイベントリストｒ１´の最終受理位置と現在のイベント位置５が間隔条件を満たすか否かを判定する。選択したイベントリストｒ１´の最終受理位置が０であり、現在のイベント位置５との間隔が５であり、間隔条件４を超えているので、照合部１５３は、間隔条件４を満たさないと判定する。そして、照合部１５２は、そのイベントリストｒ１´を削除する。
【０２９２】
続いて、照合部１５３は、状態１９の未処理のイベントリストｒ２´を選択し、選択したイベントリストｒ２´の最終受理位置と現在のイベント位置５が間隔条件を満たすか否かを判定する。選択したイベントリストｒ２´の最終受理位置が１であり、現在のイベント位置５との間隔が４であり、間隔条件４を超えていないので、照合部１５３は、間隔条件４を満たすと判定する。そして、照合部１５３は、イベントリストの最終受理位置に現在のイベント位置５を設定する。そして、照合部１５３は、通常遷移先の状態３１のイベントリストｒ１０として追加する。
【０２９３】
図２８Ｇの３段目に示すように、系列０のイベント「Ｅ」について、照合部１５３は、状態ｊの値を１ずつ増やしながら、状態ｊから出ている全てのε遷移とε＝遷移の発動を実行する。照合部１５３は、状態２５からε遷移が出ているので、状態２５のイベントリストｒ８を遷移先の状態２６、２７、２８のイベントリストｒ８´として追加し、状態２５のイベントリストｒ８を削除する。
【０２９４】
系列２のイベント「Ｃ」についても、照合部１５３は、系列０のイベント「Ｅ」の場合と同様に処理し、状態３１のイベントリストｒ１０を遷移先の状態３４のイベントリストｒ１０´として追加し、状態１０のイベントリストｒ１０を削除する。
【０２９５】
図２８Ｈに示すように、照合部１５３は、状態４７のε＝遷移元２６、３５のイベントリストｒ８´、ｒ９の、状態４７で指定された指定＠番号０、１に対応するイベント位置を取り出す。ここでは、指定＠番号０の場合、照合部１５３は、イベントリストｒ８´から０、１、イベントリストｒ９から０、１を取り出す。この場合、照合部１５３は、取り出したイベント位置が｛「現在のイベント位置」−「状態４７の＠番号０に対応するタイムアウト長」｝以下であるか否かを判定する。ここでは、取り出したイベント位置が０（または１）、現在のイベント位置は５、状態４７の＠番号０に対応するタイムアウト長が７であり、「０（または１）＞５−７」となるので、照合部１５０ｃは、これらのイベントリストを削除しないこととなる。一方、指定＠番号１の場合、照合部１５３は、イベントリストｒ８´から５、イベントリストｒ９から５を取り出す。この場合、照合部１５３は、取り出したイベント位置が｛「現在のイベント位置」−「状態４７の＠番号１に対応するタイムアウト長」｝以下であるか否かを判定する。ここでは、取り出したイベント位置が５、現在のイベント位置は５、状態４７の＠番号１に対応するタイムアウト長が０であり、「５＝５−０」となるので、照合部１５２は、タイムアウトであると判断し、イベントリストｒ８´、ｒ９を削除することとなる。
【０２９６】
続いて、照合部１５３は、状態４８のε＝遷移元２７、状態４９のε＝遷移元２８の各イベントリストｒ８´についても、状態４７の場合と同様に、＠番号１に対応するタイムアウトとなるので、各イベントリストｒ８´を削除することとなる。
【０２９７】
図２８Ｉの１段目に示すように、照合部１５３は、現在のイベント位置ｉの値を６に設定し、イベントストリーム１４３からイベント位置６および系列０のイベントＳ［６］［０］、すなわちイベント「Ｂ」を読み込む。また、照合部１５３は、イベントストリーム１４３から現在のイベント位置６および系列１のイベントＳ［６］［１］、すなわちイベント「Ｃ」を読み込む。そして、照合部１５３は、系列０のイベント「Ｂ」、系列１のイベント「Ｃ」の順に以下の照合処理を行う。
【０２９８】
図２８Ｉの２段目に示すように、系列０のイベント「Ｂ」について、照合部１５３は、状態１３から出ているイベント「Ｂ」に関する間隔条件付き通常遷移が出ているので、イベント「Ｂ」に対応する遷移種別を判定する。ここでは、照合部１５３は、状態１３から出ている間隔条件付き通常遷移をイベントに対応する遷移種別とする。そして、照合部１５３は、状態１３の未処理のイベントリストｒ１´を選択し、選択したイベントリストｒ１´の最終受理位置と現在のイベント位置６が間隔条件を満たすか否かを判定する。選択したイベントリストｒ１´の最終受理位置が０であり、現在のイベント位置６との間隔が６であり、間隔条件２を超えているので、照合部１５３は、間隔条件２を満たさないと判定する。そして、照合部１５２は、そのイベントリストｒ１´を削除する。
【０２９９】
続いて、照合部１５３は、状態１３の未処理のイベントリストｒ６´を選択し、選択したイベントリストｒ６´の最終受理位置と現在のイベント位置６が間隔条件を満たすか否かを判定する。選択したイベントリストｒ６´の最終受理位置が４であり、現在のイベント位置６との間隔が２であり、間隔条件２を超えていないので、照合部１５３は、間隔条件２を満たすと判定する。そして、照合部１５３は、イベントリストの最終受理位置に現在のイベント位置６を設定する。そして、照合部１５３は、通常遷移先の状態２０のイベントリストｒ１１として追加する。
【０３００】
系列１のイベント「Ｃ」について、照合部１５３は、状態１８から出ているイベント「Ｃ」に関する間隔条件付き通常遷移が出ているので、イベント「Ｃ」に対応する遷移種別を判定する。ここでは、照合部１５３は、状態１８から出ている間隔条件付き通常遷移をイベントに対応する遷移種別とする。そして、照合部１５３は、状態１８の未処理のイベントリストｒ１´、ｒ２´の各最終受理位置と現在のイベント位置６が間隔条件を満たすか否かを判定する。選択したイベントリストｒ１´、ｒ２´の最終受理位置がそれぞれ０、１であり、現在のイベント位置６との間隔がそれぞれ６、５であり、間隔条件４を超えているので、照合部１５３は、間隔条件４を満たさないと判定する。そして、照合部１５３は、そのイベントリストｒ１´、ｒ２´を削除する。
【０３０１】
続いて、照合部１５３は、状態１８の未処理のイベントリストｒ６´を選択し、選択したイベントリストｒ６´の最終受理位置と現在のイベント位置６が間隔条件を満たすか否かを判定する。選択したイベントリストｒ６´の最終受理位置が４であり、現在のイベント位置６との間隔が２であり、間隔条件４を超えていないので、照合部１５３は、間隔条件４を満たすと判定する。そして、照合部１５３は、イベントリストの最終受理位置に現在のイベント位置６を設定する。そして、照合部１５３は、通常遷移先の状態３０のイベントリストｒ１２として追加する。
【０３０２】
図２８Ｉの３段目に示すように、照合部１５３は、状態ｊの値を１ずつ増やしながら、状態ｊから出ている全てのε遷移とε＝遷移の発動を実行する。照合部１５３は、状態２０からε遷移が出ているので、状態２０のイベントリストｒ１１を遷移先の状態２４のイベントリストｒ１１´として追加し、状態２０のイベントリストｒ１１を削除する。
【０３０３】
続いて、照合部１５３は、状態３０からε遷移が出ているので、状態３０のイベントリストｒ１２を遷移先の状態３３のイベントリストｒ１２´として追加し、状態３０のイベントリストｒ１２を削除する。
【０３０４】
図２８Ｊの１段目に示すように、照合部１５３は、現在のイベント位置ｉの値を７に設定し、イベントストリーム１４３からイベント位置７および系列２のイベントＳ［７］［２］、すなわちイベント「Ｅ」を読み込む。
【０３０５】
図２８Ｊの２段目に示すように、照合部１５３は、状態２４から出ているイベント「Ｅ」に関する間隔条件付き通常遷移が出ているので、イベント「Ｅ」に対応する遷移種別を判定する。ここでは、照合部１５３は、状態２４から出ている間隔条件付き通常遷移をイベントに対応する遷移種別とする。そして、照合部１５３は、状態２４の未処理のイベントリストｒ３´の最終受理位置と現在のイベント位置７が間隔条件を満たすか否かを判定する。選択したイベントリストｒ３´の最終受理位置が２であり、現在のイベント位置７との間隔が５であり、間隔条件４を超えているので、照合部１５３は、間隔条件４を満たさないと判定する。そして、照合部１５３は、そのイベントリストｒ３´を削除する。
【０３０６】
続いて、照合部１５３は、状態２４の未処理のイベントリストｒ５´、ｒ１１´の各最終受理位置と現在のイベント位置７が間隔条件を満たすか否かを判定する。選択したイベントリストｒ５´、ｒ１１´の最終受理位置がそれぞれ３、６であり、現在のイベント位置７との間隔がそれぞれ４、１であり、間隔条件４を超えていないので、照合部１５３は、間隔条件４を満たすと判定する。そして、照合部１５３は、通常遷移先の状態２５に＠番号１が割り当てられているので、イベントリストの＠番号位置に現在のイベント位置７を書き込み、最終受理位置に現在のイベント位置７を設定する。そして、照合部１５３は、状態２５のイベントリストｒ１３、ｒ１４として追加する。
【０３０７】
続いて、照合部１５３は、状態３４から出ているイベント「Ｅ」に関する間隔条件付き通常遷移が出ているので、イベント「Ｅ」に対応する遷移種別を判定する。ここでは、照合部１５３は、状態３４から出ている間隔条件付き通常遷移をイベントに対応する遷移種別とする。そして、照合部１５３は、状態３４の未処理のイベントリストｒ１０´の最終受理位置と現在のイベント位置７が間隔条件を満たすか否かを判定する。選択したイベントリストｒ１０´の最終受理位置が５であり、現在のイベント位置７との間隔が２であり、間隔条件３を超えていないので、照合部１５３は、間隔条件３を満たすと判定する。そして、照合部１５３は、通常遷移先の状態３７に＠番号１が割り当てられているので、イベントリストの＠番号位置に現在のイベント位置７を書き込み、最終受理位置に現在のイベント位置７を設定する。そして、照合部１５３は、状態３７のイベントリストｒ１５として追加する。
【０３０８】
続いて、照合部１５３は、状態４３から出ているイベント「Ｅ」に関する間隔条件付き通常遷移が出ているので、イベント「Ｅ」に対応する遷移種別を判定する。ここでは、照合部１５３は、状態４３から出ている間隔条件付き通常遷移をイベントに対応する遷移種別とする。そして、照合部１５３は、状態４３の未処理のイベントリストｒ７´の最終受理位置と現在のイベント位置７が間隔条件を満たすか否かを判定する。選択したイベントリストｒ７´の最終受理位置が４であり、現在のイベント位置７との間隔が３であり、間隔条件５を超えていないので、照合部１５３は、間隔条件５を満たすと判定する。そして、照合部１５３は、通常遷移先の状態４６に＠番号１が割り当てられているので、イベントリストの＠番号位置に現在のイベント位置７を書き込み、最終受理位置に現在のイベント位置７を設定する。そして、照合部１５３は、状態４６のイベントリストｒ１６として追加する。
【０３０９】
図２８Ｊの３段目に示すように、系列０のイベント「Ｅ」について、照合部１５３は、状態ｊの値を１ずつ増やしながら、状態ｊから出ている全てのε遷移とε＝遷移の発動を実行する。照合部１５３は、状態２５からε遷移が出ているので、状態２５のイベントリストｒ１３、ｒ１４をそれぞれ遷移先の状態２６、２７、２８のイベントリストｒ１３´、ｒ１４´として追加し、状態２５のイベントリストｒ１３、ｒ１４を削除する。
【０３１０】
続いて、照合部１５３は、状態４９が合流ノードであるので、状態４９のε＝遷移元の状態２８、３７、４６のイベントリストの、状態４９で指定された指定＠番号の＠番号位置のイベント位置が一致しているイベントリストを探索する。ここでは、状態２８のイベントリストｒ１３´および状態３７のイベントリストｒ１５の指定＠番号０、１に対応するイベント位置が１、７で共通している。加えて、状態４６のイベントリストｒ１６の指定＠番号０、１に対応するイベント位置が＊（任意のイベント位置）、７であるので、状態２８のイベントリストｒ１３´および状態３７のイベントリストｒ１５のものと一致する。そこで、照合部１５２は、これらイベントリストｒ１３´、ｒ１５、ｒ１６の組み合わせに対して、イベントリストを結合し、結合したイベントリストｒ２０を状態４９に追加する。
【０３１１】
図２８Ｋに示すように、照合部１５３は、状態４７のε＝遷移元２６のイベントリストｒ１３´、ｒ１４´の、状態４７で指定された指定＠番号０、１に対応するイベント位置を取り出す。ここでは、指定＠番号０の場合、照合部１５３は、イベントリストｒ１３´、ｒ１４´から１、４を取り出す。この場合、照合部１５３は、取り出したイベント位置が｛「現在のイベント位置」−「状態４７の＠番号０に対応するタイムアウト長」｝以下であるか否かを判定する。ここでは、取り出したイベント位置が１（または４）、現在のイベント位置は７、状態４７の＠番号０に対応するタイムアウト長が７であり、「１（または４）＞７−７」となるので、照合部１５３は、これらのイベントリストを削除しないこととなる。一方、指定＠番号１の場合、照合部１５３は、イベントリストｒ１３´、ｒ１４´から７を取り出す。この場合、照合部１５３は、取り出したイベント位置が｛「現在のイベント位置」−「状態４７の＠番号１に対応するタイムアウト長」｝以下であるか否かを判定する。ここでは、取り出したイベント位置が７、現在のイベント位置は７、状態４７の＠番号１に対応するタイムアウト長が０であり、「７＝７−０」となるので、照合部１５３は、タイムアウトであると判断し、イベントリストｒ１３´、ｒ１４´を削除することとなる。
【０３１２】
続いて、照合部１５３は、状態４８のε＝遷移元２７のイベントリストｒ１３´、ｒ１４´についても、状態４７の場合と同様に、＠番号１に対応するタイムアウトとなるので、各イベントリストｒ１３´、ｒ１４´を削除することとなる。
【０３１３】
そして、照合部１５３は、状態４９が最終状態で、イベントリストｒ２０があるので、現在のイベント位置７を照合結果として通知し、状態４９のイベントリストｒ２０を削除する。すなわち、照合部１５３は、照合が完了した結果として、イベントパターンの終了時刻を通知する。そして、照合部１５３は、状態４９まで処理を完了したので、全てのε遷移とε＝遷移の発動を終了する。
【０３１４】
そして、続いて、図２８Ｌに示すように、照合部１５３は、現在のイベント位置ｉの値を８に設定し、イベントストリーム１４３からイベント位置８および系列１のイベント「Ｄ」を読み込み、照合を続ける。続いて、図２８Ｍ、図２８Ｎに示すように、照合部１５３は、現在のイベント位置ｉの値を９に設定し、イベントストリーム１４３からイベント位置９および系列１のイベント「Ｅ」を読み込み、照合を続けることとなる。
【０３１５】
照合部１５３は、上述した図２８Ａ〜図２８Ｎに示す処理を実行することにより、ＮＦＡ１４２を利用して、イベントストリーム１４３を照合する。そして、照合部１５３は、照合結果をユーザ端末５０に通知する。なお、照合部１５３は、照合結果を表示部１３０に表示させても良い。上述した図２８Ａ〜図２８Ｎでは、照合結果を、イベントストリーム１４３上のイベントパターン１４１の終了時刻としたが、開始時刻を含んだものとしても良い。
【０３１６】
［実施例の効果］
次に、本実施例にかかる照合装置１００の効果について説明する。照合装置１００は、複数系列のイベントを含むイベントパターンで１４１あってイベント間の発生順序と間隔条件とを伴ったイベントパターン１４１について、イベントパターン１４１に対応する仮ＮＦＡを生成する。そして、照合装置１００は、生成した仮ＮＦＡの中のイベント同士が同系列で接続される同系列部分に対応するＮＦＡ部分を複数系列分複製する。そして、照合装置１００は、複製した各ＮＦＡ部分を各系列のイベントで受理する遷移に置き換え、置き換えた各ＮＦＡ部分をε遷移で結合する。そして、照合装置１００は、イベントストリーム１４３に含まれるイベントについて、複製したそれぞれのＮＦＡ部分のうち、当該イベントが発生した系列に対応したＮＦＡ部分で受理する。そして、照合装置１００は、当該イベントを受理したＮＦＡ部分を動作させる。かかる構成によれば、照合装置１００によれば、ある系列で発生したイベントを、発生した系列に対応したＮＦＡ部分で受理し動作させるようにしたので、当該イベントより前に発生したイベントとの系列の同一性を判定する処理を高速化できる。
【０３１７】
また、照合装置１００は、イベントパターン１４１の中に同系列部分とイベント同士が任意の系列で接続される任意系列部分とが接続されている場合、生成した仮ＮＦＡの中の同系列部分に対応するＮＦＡ部分を切り離する。そして、照合装置１００は、切り離したＮＦＡ部分を複数系列分複製する。そして、照合装置１００は、複製した各ＮＦＡ部分を各系列のイベントで受理する遷移に置き換え、置き換えた各ＮＦＡ部分と切り離す前の元のＮＦＡの接合部分とをε遷移で結合する。そして、照合装置１００は、イベントストリーム１４３に含まれるイベントについて、複製した各ＮＦＡ部分では、各ＮＦＡ部分のうち当該イベントが発生した系列に対応したＮＦＡ部分で受理し当該ＮＦＡ部分を動作させ、前記任意系列部分に対応するＮＦＡ部分では、当該ＮＦＡ部分で受理し当該ＮＦＡ部分を動作させる。かかる構成によれば、照合装置１００によれば、ある系列で発生したイベントを、発生した系列に対応したＮＦＡ部分で受理し動作させるようにしたので、当該イベントより前に発生したイベントとの系列の同一性を判定する処理を高速化できる。
【０３１８】
また、照合装置１００は、同系列部分に対応するＮＦＡ部分と任意系列部分に対応するＮＦＡ部分との接合部分が同系列部分に対応するＮＦＡ部分の途中に存在する場合、同系列部分を複製した各ＮＦＡ部分と任意系列部分との接合部分として接続ノードを生成する。そして、照合装置１００は、生成した接続ノードと同系列部分を複製した各ＮＦＡ部分とをε遷移で接続し、生成した接続ノードと任意系列部分とをε遷移で接合する。かかる構成によれば、照合装置１００によれば、同系列部分に対応するＮＦＡ部分と任意系列部分に対応するＮＦＡ部分との接合部分が同系列部分に対応するＮＦＡ部分の途中に存在する場合であっても、接続ノードを介して同系列部分と任意系列部分とをつなぐことができる。このため、照合装置１００は、ある系列で発生したイベントを、発生した系列に対応したＮＦＡ部分で受理し動作させる処理を容易に実現できる。この結果、照合装置１００は、当該イベントより前に発生したイベントとの系列の同一性を判定する処理を高速化できる。
【０３１９】
［プログラムなど］
なお、照合装置１００は、既知のパーソナルコンピュータ、ワークステーションなどの情報処理装置に、上記したＮＦＡ生成部１５２、照合部１５３などの各機能を搭載することによって実現することができる。
【０３２０】
また、図示した各装置の各構成要素は、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的態様は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、ＮＦＡ生成部１５２と照合部１５３とを１個の部として統合しても良い。一方、ＮＦＡ生成部１５２を、仮ＮＦＡを生成する仮ＮＦＡ生成部と、仮ＮＦＡから同系列のＮＦＡ探索する同系列ＮＦＡ探索部と、同系列のＮＦＡを変換する同系列ＮＦＡ変換部とに分散しても良い。また、ＮＦＡ１４２などの記憶部を照合装置１００の外部装置としてネットワーク経由で接続するようにしても良い。
【０３２１】
また、上記実施例で説明した各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。そこで、以下では、図２に示した照合装置１００と同様の機能を実現する照合プログラムを実行するコンピュータの一例を説明する。図２９は、照合プログラムを実行するコンピュータの一例を示す図である。
【０３２２】
図２９に示すように、コンピュータ２００は、各種演算処理を実行するＣＰＵ２０１と、ユーザからのデータの入力を受け付ける入力装置２０２と、ディスプレイ２０３を有する。また、コンピュータ２００は、記憶媒体からプログラム等を読取る読み取り装置２０４と、ネットワークを介して他のコンピュータとの間でデータの授受を行うインタフェース装置２０５とを有する。また、コンピュータ２００は、各種情報を一時記憶するＲＡＭ２０６と、ハードディスク装置２０７を有する。そして、各装置２０１〜２０７は、バス２０８に接続される。
【０３２３】
ハードディスク装置２０７は、ＮＦＡ生成プログラム２０７ａ、照合プログラム２０７ｂを記憶する。ＣＰＵ２０１は、各プログラム２０７ａ〜２０７ｂを読み出して、ＲＡＭ２０６に展開する。ＮＦＡ生成プログラム２０７ａは、ＮＦＡ生成プロセス２０６ａとして機能する。照合プログラム２０７ｂは、照合プロセス２０６ｂとして機能する。
【０３２４】
例えば、ＮＦＡ生成プロセス２０６ａは、ＮＦＡ生成部１５２に対応する。照合プロセス２０６ｂは、照合部１５３に対応する。
【０３２５】
なお、各プログラム２０７ａ〜２０７ｂについては、必ずしも最初からハードディスク装置２０７に記憶させておかなくてもよい。例えば、コンピュータ２００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に各プログラムを記憶させておく。そして、コンピュータ２００がこれらから各プログラム２０７ａ〜２０７ｂを読み出して実行するようにしても良い。
【０３２６】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０３２７】
（付記１）複数系列のイベントを含むイベントパターンであってイベント間の発生順序と間隔条件とを伴ったイベントパターンについて、前記イベントパターンに対応するオートマトンを生成する処理、生成したオートマトンの中のイベント同士が同系列で接続される同系列部分に対応するオートマトン部分を複数系列分複製し、複製した各オートマトン部分を各系列のイベントで受理する遷移に置き換え、置き換えた各オートマトン部分をε遷移で結合する処理を行うことで、オートマトンを生成するオートマトン生成部と、
複数系列の複数のイベントの発生順序を含むイベントストリームと、前記オートマトンとを順次比較し、前記イベントストリームに含まれるイベントについて、前記複製したそれぞれのオートマトン部分のうち、当該イベントが発生した系列に対応したオートマトン部分で受理し当該オートマトン部分を動作させることで、前記イベントストリームに前記イベントパターンが含まれているか否かを照合する照合部と
を有することを特徴とする照合装置。
【０３２８】
（付記２）前記オートマトン生成部は、イベントパターンの中に前記同系列部分とイベント同士が任意の系列で接続される任意系列部分とが接続されている場合、生成したオートマトンの中の前記同系列部分に対応するオートマトン部分を切り離し、切り離したオートマトン部分を複数系列分複製し、複製した各オートマトン部分を各系列のイベントで受理する遷移に置き換え、置き換えた各オートマトン部分と切り離す前の元のオートマトンの接合部分とをε遷移で結合し、
前記照合部は、前記イベントストリームに含まれるイベントについて、複製した各オートマトン部分では、各オートマトン部分のうち当該イベントが発生した系列に対応したオートマトン部分で受理し当該オートマトン部分を動作させ、前記任意系列部分に対応するオートマトン部分では、当該オートマトン部分で受理し当該オートマトン部分を動作させる
ことを特徴とする付記１に記載の照合装置。
【０３２９】
（付記３）前記オートマトン生成部は、前記同系列部分に対応するオートマトン部分と前記任意系列部分に対応するオートマトン部分との接合部分が前記同系列部分に対応するオートマトン部分の途中に存在する場合、前記同系列部分を複製した各オートマトン部分と前記任意系列部分との接合部分として接続ノードを生成し、生成した接続ノードと前記同系列部分を複製した各オートマトン部分とをε遷移で接続し、生成した接続ノードと前記任意系列部分とをε遷移で接合する
ことを特徴とする付記２に記載の照合装置。
【０３３０】
（付記４）コンピュータに、
複数系列のイベントを含むイベントパターンであってイベント間の発生順序と間隔条件とを伴ったイベントパターンについて、前記イベントパターンに対応するオートマトンを生成する処理、生成したオートマトンの中のイベント同士が同系列で接続される同系列部分に対応するオートマトン部分を複数系列分複製し、複製した各オートマトン部分を各系列のイベントで受理する遷移に置き換え、置き換えた各オートマトン部分をε遷移で結合する処理を行うことで、オートマトンを生成し、
複数系列の複数のイベントの発生順序を含むイベントストリームと、前記オートマトンとを順次比較し、前記イベントストリームに含まれるイベントについて、前記複製したそれぞれのオートマトン部分のうち、当該イベントが発生した系列に対応したオートマトン部分で受理し当該オートマトン部分を動作させることで、前記イベントストリームに前記イベントパターンが含まれているか否かを照合する
各処理を実行させることを特徴とする照合プログラム。
【０３３１】
（付記５）コンピュータが、
複数系列のイベントを含むイベントパターンであってイベント間の発生順序と間隔条件とを伴ったイベントパターンについて、前記イベントパターンに対応するオートマトンを生成する処理、生成したオートマトンの中のイベント同士が同系列で接続される同系列部分に対応するオートマトン部分を複数系列分複製し、複製した各オートマトン部分を各系列のイベントで受理する遷移に置き換え、置き換えた各オートマトン部分をε遷移で結合する処理を行うことで、オートマトンを生成し、
複数系列の複数のイベントの発生順序を含むイベントストリームと、前記オートマトンとを順次比較し、前記イベントストリームに含まれるイベントについて、前記複製したそれぞれのオートマトン部分のうち、当該イベントが発生した系列に対応したオートマトン部分で受理し当該オートマトン部分を動作させることで、前記イベントストリームに前記イベントパターンが含まれているか否かを照合する
各処理を実行することを特徴とする照合方法。
【符号の説明】
【０３３２】
１００    照合装置
１１０    通信部
１２０    入力部
１３０    表示部
１４０    記憶部
１４１    イベントパターン
１４２    ＮＦＡ
１４３    イベントストリーム
１５０    制御部
１５１    データ取得部
１５２    ＮＦＡ生成部
１５３    照合部
【図１】
2013097570.tif 000003
【図２】
2013097570.tif 000004
【図３】
2013097570.tif 000005
【図４】
2013097570.tif 000006
【図５】
2013097570.tif 000007
【図６】
2013097570.tif 000008
【図７】
2013097570.tif 000009
【図８】
2013097570.tif 000010
【図９】
2013097570.tif 000011
【図１０】
2013097570.tif 000012
【図１１】
2013097570.tif 000013
【図１２】
2013097570.tif 000014
【図１３】
2013097570.tif 000015
【図１４】
2013097570.tif 000016
【図１５】
2013097570.tif 000017
【図１６】
2013097570.tif 000018
【図１７】
2013097570.tif 000019
【図１８】
2013097570.tif 000020
【図１９Ａ】
2013097570.tif 000021
【図１９Ｂ】
2013097570.tif 000022
【図１９Ｃ】
2013097570.tif 000023
【図１９Ｄ】
2013097570.tif 000024
【図２０Ａ】
2013097570.tif 000025
【図２０Ｂ】
2013097570.tif 000026
【図２０Ｃ】
2013097570.tif 000027
【図２０Ｄ】
2013097570.tif 000028
【図２０Ｅ】
2013097570.tif 000029
【図２０Ｆ】
2013097570.tif 000030
【図２１Ａ】
2013097570.tif 000031
【図２１Ｂ】
2013097570.tif 000032
【図２１Ｃ】
2013097570.tif 000033
【図２１Ｄ】
2013097570.tif 000034
【図２１Ｅ】
2013097570.tif 000035
【図２１Ｆ】
2013097570.tif 000036
【図２１Ｇ】
2013097570.tif 000037
【図２２Ａ】
2013097570.tif 000038
【図２２Ｂ】
2013097570.tif 000039
【図２２Ｃ】
2013097570.tif 000040
【図２２Ｄ】
2013097570.tif 000041
【図２２Ｅ】
2013097570.tif 000042
【図２２Ｆ】
2013097570.tif 000043
【図２２Ｇ】
2013097570.tif 000044
【図２３Ａ】
2013097570.tif 000045
【図２３Ｂ】
2013097570.tif 000046
【図２３Ｃ】
2013097570.tif 000047
【図２３Ｄ】
2013097570.tif 000048
【図２３Ｅ】
2013097570.tif 000049
【図２３Ｆ】
2013097570.tif 000050
【図２３Ｇ】
2013097570.tif 000051
【図２４Ａ】
2013097570.tif 000052
【図２４Ｂ】
2013097570.tif 000053
【図２４Ｃ】
2013097570.tif 000054
【図２４Ｄ】
2013097570.tif 000055
【図２４Ｅ】
2013097570.tif 000056
【図２４Ｆ】
2013097570.tif 000057
【図２４Ｇ】
2013097570.tif 000058
【図２４Ｈ】
2013097570.tif 000059
【図２４Ｉ】
2013097570.tif 000060
【図２４Ｊ】
2013097570.tif 000061
【図２４Ｋ】
2013097570.tif 000062
【図２４Ｌ】
2013097570.tif 000063
【図２４Ｍ】
2013097570.tif 000064
【図２５】
2013097570.tif 000065
【図２６】
2013097570.tif 000066
【図２７】
2013097570.tif 000067
【図２８Ａ】
2013097570.tif 000068
【図２８Ｂ】
2013097570.tif 000069
【図２８Ｃ】
2013097570.tif 000070
【図２８Ｄ】
2013097570.tif 000071
【図２８Ｅ】
2013097570.tif 000072
【図２８Ｆ】
2013097570.tif 000073
【図２８Ｇ】
2013097570.tif 000074
【図２８Ｈ】
2013097570.tif 000075
【図２８Ｉ】
2013097570.tif 000076
【図２８Ｊ】
2013097570.tif 000077
【図２８Ｋ】
2013097570.tif 000078
【図２８Ｌ】
2013097570.tif 000079
【図２８Ｍ】
2013097570.tif 000080
【図２８Ｎ】
2013097570.tif 000081
【図２９】
2013097570.tif 000082
【図３０】
2013097570.tif 000083
【図３１】
2013097570.tif 000084
【図３２】
2013097570.tif 000085
【図３３】
2013097570.tif 000086
【図３４】
2013097570.tif 000087
【図３５】
2013097570.tif 000088