複数系列のイベントを含むイベントパターンであってイベント間の発生順序と間隔条件とを伴ったイベントパターンについて、前記イベントパターンに対応するオートマトンを生成する処理、生成したオートマトンの中のイベント同士が同系列で接続される同系列部分に対応するオートマトン部分を複数系列分複製し、複製した各オートマトン部分を各系列のイベントで受理する遷移に置き換え、置き換えた各オートマトン部分をε遷移で結合する処理を行うことで、オートマトンを生成するオートマトン生成部と、複数系列の複数のイベントの発生順序を含むイベントストリームと、前記オートマトンとを順次比較し、前記イベントストリームに含まれるイベントについて、前記複製したそれぞれのオートマトン部分のうち、当該イベントが発生した系列に対応したオートマトン部分で受理し当該オートマトン部分を動作させることで、前記イベントストリームに前記イベントパターンが含まれているか否かを照合する照合部とを有することを特徴とする照合装置。前記オートマトン生成部は、イベントパターンの中に前記同系列部分とイベント同士が任意の系列で接続される任意系列部分とが接続されている場合、生成したオートマトンの中の前記同系列部分に対応するオートマトン部分を切り離し、切り離したオートマトン部分を複数系列分複製し、複製した各オートマトン部分を各系列のイベントで受理する遷移に置き換え、置き換えた各オートマトン部分と切り離す前の元のオートマトンの接合部分とをε遷移で結合し、前記照合部は、前記イベントストリームに含まれるイベントについて、複製した各オートマトン部分では、各オートマトン部分のうち当該イベントが発生した系列に対応したオートマトン部分で受理し当該オートマトン部分を動作させ、前記任意系列部分に対応するオートマトン部分では、当該オートマトン部分で受理し当該オートマトン部分を動作させることを特徴とする請求項1に記載の照合装置。コンピュータに、複数系列のイベントを含むイベントパターンであってイベント間の発生順序と間隔条件とを伴ったイベントパターンについて、前記イベントパターンに対応するオートマトンを生成する処理、生成したオートマトンの中のイベント同士が同系列で接続される同系列部分に対応するオートマトン部分を複数系列分複製し、複製した各オートマトン部分を各系列のイベントで受理する遷移に置き換え、置き換えた各オートマトン部分をε遷移で結合する処理を行うことで、オートマトンを生成し、複数系列の複数のイベントの発生順序を含むイベントストリームと、前記オートマトンとを順次比較し、前記イベントストリームに含まれるイベントについて、前記複製したそれぞれのオートマトン部分のうち、当該イベントが発生した系列に対応したオートマトン部分で受理し当該オートマトン部分を動作させることで、前記イベントストリームに前記イベントパターンが含まれているか否かを照合する各処理を実行させることを特徴とする照合プログラム。コンピュータが、複数系列のイベントを含むイベントパターンであってイベント間の発生順序と間隔条件とを伴ったイベントパターンについて、前記イベントパターンに対応するオートマトンを生成する処理、生成したオートマトンの中のイベント同士が同系列で接続される同系列部分に対応するオートマトン部分を複数系列分複製し、複製した各オートマトン部分を各系列のイベントで受理する遷移に置き換え、置き換えた各オートマトン部分をε遷移で結合する処理を行うことで、オートマトンを生成し、複数系列の複数のイベントの発生順序を含むイベントストリームと、前記オートマトンとを順次比較し、前記イベントストリームに含まれるイベントについて、前記複製したそれぞれのオートマトン部分のうち、当該イベントが発生した系列に対応したオートマトン部分で受理し当該オートマトン部分を動作させることで、前記イベントストリームに前記イベントパターンが含まれているか否かを照合する各処理を実行することを特徴とする照合方法。しかしながら、上述した従来技術では、同一系列の2つのイベントを用いた条件を設定した場合、複数系列からのイベントデータに対して、2つのイベント間の系列の同一性を判定する処理が遅くなってしまうという問題がある。例えば、同一系列の2つのイベントを用いたイベントパターンを設定した場合、複数系列からのイベントを含むイベントストリームに対して、イベントパターンの同一系列のイベントを過去の大量のイベントから探索することとなる。この結果、2つのイベント間の系列の同一性を判定する処理が遅くなってしまう。従来のNFAであっても、2つのイベント間の系列の関係を設定できないので、イベントストリームに対して、イベントパターンの同一系列のイベントを探索することとなる。この結果、2つのイベント間の系列の同一性を判定する処理が遅くなってしまう。開示の技術は、上記に鑑みてなされたものであって、同一系列の2つのイベントを用いた条件を設定した場合、複数系列からのイベントデータに対して、2つのイベント間の系列の同一性を判定する処理を高速にする照合装置などを提供することを目的とする。開示の照合装置は、オートマトン生成部および照合部を有する。オートマトン生成部は、複数系列のイベントを含むイベントパターンであってイベント間の発生順序と間隔条件とを伴ったイベントパターンについて、前記イベントパターンに対応するオートマトンを生成する処理、生成したオートマトンの中のイベント同士が同系列で接続される同系列部分に対応するオートマトン部分を複数系列分複製し、複製した各オートマトン部分を各系列のイベントで受理する遷移に置き換え、置き換えた各オートマトン部分をε遷移で結合する処理を行うことで、オートマトンを生成する。照合部は、複数系列の複数のイベントの発生順序を含むイベントストリームと、前記オートマトンとを順次比較し、前記イベントストリームに含まれるイベントについて、前記複製したそれぞれのオートマトン部分のうち、当該イベントが発生した系列に対応したオートマトン部分で受理し当該オートマトン部分を動作させることで、前記イベントストリームに前記イベントパターンが含まれているか否かを照合する。本願の開示する照合装置の一つの態様によれば、同一系列の2つのイベントを用いた条件を設定した場合、複数系列からのイベントデータに対して、2つのイベント間の系列の同一性を判定する処理を高速にできるという効果を奏する。以下に、本願の開示する照合装置、照合プログラムおよび照合方法の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。[実施例に係る照合システムの構成]実施例に係る照合システムの構成の一例について説明する。図1は、本実施例にかかる照合システムの構成を示す図である。図1に示すように、この照合システムは、イベントストリーム発生装置40、ユーザ端末50、照合装置100を有する。照合装置100は、ネットワーク30を介して、イベントストリーム発生装置40、ユーザ端末50に接続される。イベントストリーム発生装置40は、複数系統の複数のイベントの系列を含むイベントストリームを発生する装置である。イベントストリーム発生装置40は、イベントストリームの情報を、照合装置100に送信する。ユーザ端末50は、照合装置100にイベントパターンを送信し、照合装置100から照合結果を受信する装置である。照合装置100は、イベントパターンがイベントストリームに含まれるか否かを照合する装置である。照合装置100は、照合結果をユーザ端末50に送信する。[実施例に係る照合装置の構成]図1に示した照合装置100の構成について説明する。図2は、実施例に係る照合装置の構成を示す機能ブロック図である。図2に示すように、この照合装置100は、通信部110、入力部120、表示部130、記憶部140、制御部150を有する。通信部110は、ネットワーク30を介して、イベントストリーム発生装置40、ユーザ端末50とデータ通信を行う処理部である。後述する制御部150は、通信部110を介して、イベントストリームやイベントパターンの情報を受信する。通信部110は、所定の通信プロトコルを用いてデータ通信を行う通信装置、通信カード等に対応する。入力部120は、ユーザが各種の情報を照合装置100に入力するための入力装置である。例えば、入力部120は、キーボード、マウス、タッチパネルに対応する。表示部130は、各種の情報を表示する表示装置である。例えば、表示部130は、ディスプレイ、タッチパネルに対応する。記憶部140は、イベントパターン141、NFANondeterministicFiniteAutomaton142およびイベントストリーム143を記憶する。記憶部140は、例えば、RAMRandomAccessMemory、ROMReadOnlyMemory、フラッシュメモリFlashMemory等の半導体メモリ素子、またはハードディスク、光ディスク等の記憶装置に対応する。イベントパターン141は、イベントストリーム143の照合に用いられるイベントパターンである。本実施例では、イベントパターンを、同一系統の2つのイベントを間隔条件付きの遷移で接続した間隔条件付きイベントのパターンを含むものとする。1つの例として、イベントパターン141をP={b:2:a}の間隔条件付きイベントのパターンとする。このイベントパターンのa、bは、それぞれ同一系統で発生するイベントa、bに対応する。なお、{b:2:a}とは、イベントaとの差が2以内でイベントaと同一の系統のイベントbを受理することを意味する。また、別の例として、イベントパターン141をP={c:5:b}の同一系統の間隔条件付きイベントのパターンとP2=aの任意の系統のイベントとを間隔条件付きの遷移で接続した間隔条件付きイベントのパターンとする。このイベントパターンのb、cは、それぞれ同一系統で発生するイベントb、cに対応する。このイベントパターンのaは、どの系統でも許可される任意の系統で発生するイベントaに対応する。なお、{c:5:b}とは、イベントbとの差が5以内でイベントbと同一の系統のイベントcを受理することを意味する。NFA142は、イベントパターン141を基にして生成される非決定性有限オートマトンである。イベントストリーム143は、複数系統における複数のイベントの系列を含むデータである。図3は、イベントストリームのデータ構造の一例を示す図である。図3に示すように、イベントストリーム143は、複数のイベントの系列を系統毎に示すイベントストリームと、各イベントが発生した時刻とを対応づけて記憶する。例えば、系列0は、0系統の複数のイベントの系列を示し、時刻0にA、時刻2にB、時刻3にC、時刻4にA、時刻5にE、時刻6にBを記憶する。系列1は、1系統の複数のイベントの系列を示し、時刻1にA、時刻3にB、時刻6にCを記憶する。なお、A、B、C、Eは、それぞれイベントに対応する。制御部150は、データ取得部151、NFA生成部152および照合部153を有する。例えば、制御部150は、ASICApplicationSpecificIntegratedCircuitや、FPGAFieldProgrammableGateArrayなどの集積装置に対応する。また、制御部150は、例えば、CPUやMPUMicroProcessingUnit等の電子回路に対応する。データ取得部151は、イベントストリーム発生装置40から、イベントストリームを取得し、ユーザ端末50からイベントパターンを取得する処理部である。データ取得部151は、イベントパターンおよびイベントストリームを、イベントパターン141、イベントストリーム143として記憶部140に格納する。NFA生成部152は、イベントパターン141を基にして、NFA142を生成する処理部である。なお、NFA生成部152は、ThompsonNFA手法を利用して、NFAを生成するが、これに限定されるものではなく、如何なる従来技術を利用してNFAを生成しても良い。また、NFA生成部152は、生成したNFA142を記憶部140に格納する。ここで、NFA生成部152のNFA構築法について説明する。図4~図9は、NFA生成部のNFA構築法を説明するための図である。図4は、同一系列の2つのイベントにおける間隔条件付きのイベントパターンに対するNFAを示す。なお、図4では、a、bはイベントを指し、yはイベント間隔の間隔条件を指すものとする。図4の上段に示すように、イベントパターン141は、任意の系列でイベントbが発生し、その後y以内にbと同じ系列でイベントcが発生するパターンである。図4の中段に示すように、NFA生成部152は、イベントパターン141を仮のNFAに変換する。かかる仮のNFAを仮NFAとする。ここでは、NFA生成部152は、ノード1aとノード1b、ノード1bとノード1c、ノード1cとノード1d、ノード1dとノード1e、ノード1eとノード1fとをそれぞれ接続する。そして、NFA生成部152は、ノード1aからノード1bへの遷移、ノード1cからノード1dへの遷移およびノード1eからノード1fへの遷移をε遷移とする。例えば、イベントbがノード1aに遷移してきた場合に、ノード1aからノード1bへの遷移が発動される。そして、NFA生成部152は、ノード1dからノード1eへの遷移を、イベント間隔の条件を持つ遷移c:yとする。すなわち、ノード1dがイベントcを受理すると、既にノード1dが受理したイベントbとの間隔条件yを満たすとき、ノード1dからノード1eへの遷移が発動される。このように、間隔条件をチェックしたうえでノードからノードに遷移する通常遷移を間隔条件付きの通常遷移とする。なお、図4の例では、ノード1bからノード1cへの遷移をイベントbに関する間隔条件付きの通常遷移b:xとしている。すなわち、ノード1bがイベントbを受理したとき、既にノード1bが受理したイベントとの間隔条件xを満たすとき、ノード1bからノード1cへの遷移が発動される。図4の下段に示すように、NFA生成部152は、仮NFAの同系列関係のNFA部分を複数系列分複製し、複製した各NFA部分を各系列のイベントで受理する遷移に置き換え、置き換えた各NFA部分をε遷移で結合する。ここでは、NFA生成部152は、仮NFAのノード1bからノード1eまでの同系列関係のNFA部分をN個の複数系列分複製し、複製した各NFA部分の遷移を各系列のイベントで受理する遷移に置き換える。また、NFA生成部152は、複製した各NFA部分をε遷移で結合する。ここでは、NFA生成部152は、1系列の間隔条件付きの通常遷移をb1:xおよびc1:yに置き換え、N系列の間隔条件付きの通常遷移をbN:xおよびcN:yに置き換える。これにより、例えば、c1:yでは、1系列のイベントcでのみ受理され、cN:yでは、N系列のイベントcでのみ受理されることとなる。図5は、同一系列の2つのイベントにおける間隔条件付きイベントのパターンと任意の系列のイベントとを組み合わせたイベントパターンに対するNFAを示す。なお、図5では、a、b、cはイベントを指し、x、yはイベント間隔の間隔条件を指すものとする。図5の上段に示すように、イベントパターン141は、任意の系列でイベントaが発生した後x以内に任意の系列でbが発生し、その後y以内にbと同じ系列でイベントcが発生するパターンである。なお、イベントパターン141において、同系列の遷移関係を実線で表記し、任意系列の遷移関係を破線で表記するものとする。図5の中段に示すように、NFA生成部152は、イベントパターン141を仮NFAに変換する。ここでは、NFA生成部152は、ノード2aとノード2b、ノード2bとノード2c、ノード2cとノード2d、ノード2dとノード2e、ノード2eとノード2f、ノード2fとノード2gとをそれぞれ接続する。また、NFA生成部152は、ノード2aからノード2bへの遷移をaとする。すなわち、ノード2aがイベントaを受理すると、ノード2aからノード2bへの遷移が無条件に発動される。このように、ノードからノードに無条件に遷移する通常遷移を間隔条件なしの通常遷移とする。また、NFA生成部152は、ノード2bからノード2cへの遷移、ノード2dからノード2eへの遷移およびノード2fからノード2gへの遷移をε遷移とする。また、NFA生成部152は、ノード2cからノード2dへの遷移を、イベント間隔の条件を持つ遷移b:xとする。また、NFA生成部152は、ノード2eからノード2fへの遷移を、イベント間隔の条件を持つ遷移c:yとする。そして、NFA生成部152は、仮NFAの中の同系列関係のNFA部分を同系列関係情報として設定する。ここでは、NFA生成部152は、ノード2cからノード2fまでが同系列関係のNFA部分であり、このNFA部分を同系列関係情報として設定する。図5の下段に示すように、NFA生成部152は、仮NFAから同系列関係のNFA部分を探索し、探索できた同系列関係のNFA部分を切り離す。そして、NFA生成部152は、切り離した同系列関係のNFA部分を複数系列分複製し、複製した各NFA部分を各系列のイベントで受理する遷移に置き換える。そして、NFA生成部152は、置き換えた各NFA部分と切り離す前の元の仮NFAの接合部分とをε遷移で結合する。ここでは、NFA生成部152は、ノード2cからノード2fまでの同系列関係のNFA部分をN個の複数系列分複製し、複製したNFA部分の遷移を各系列のイベントで受理する遷移に置き換える。また、NFA生成部152は、複製したNFA部分と切り離す前の元の仮NFAの接合部分であるノード2bとをそれぞれε遷移で結合する。これにより、例えば、c1:yでは、1系列のイベントcでのみ受理され、cN:yでは、N系列のイベントcでのみ受理されることとなる。また、例えば、aでは、全ての系列のイベントaで受理されることとなる。図6は、仮NFAにおいて同系列関係のNFA部分と任意系列関係との接合部分が同系列関係の途中に存在する場合のNFAを示す。なお、図6では、a、b、c、dはイベントを指し、x、yはイベント間隔の間隔条件を指すものとする。図6の上段に示すように、イベントパターン141は、任意の系列でイベントaが発生し、その後x以内にaと同じ系列でイベントbが発生する。そして、イベントパターン141は、任意の系列でイベントaが発生した後y以内に任意の系列でcが発生し、その後z以内にcと同じ系列でイベントdが発生するパターンである。図6の中段に示すように、NFA生成部152は、イベントパターン141を仮NFAに変換する。ここでは、NFA生成部152は、イベントパターン141の中のイベントa、bにおける間隔条件付きイベントのパターンについて、ノード3b~ノード3eで表される同系列Aの仮NFAに変換する。また、NFA生成部152は、イベントパターン141の中のイベントc、dにおける間隔条件付きイベントのパターンについて、ノード3f~ノード3iで表される同系列Bの仮NFAに変換する。そして、NFA生成部152は、分岐の起点となるイベントaの受理時刻を当該イベントaの遷移先を示すノード3cに対応付けて保持させる。すなわち、ノード3cが同系列Aと同系列Bとの接合部分である。ここで、イベントの受理時刻を保持させるノードを受理時刻保持ノード起点ノードに相当というものとする。図6の例では、受理時刻保持ノードをで示している。そして、NFA生成部152は、分岐の起点となるイベントaに対応させて、受理時刻保持ノードに一意の識別子となる番号ここでは0を割り当てる。そして、NFA生成部152は、ノード3cから分岐先のノード3fにε遷移で接続する。また、NFA生成部152は、ノード3eおよびノード3iからノード3jへそれぞれε=遷移で接続する。ここで、複数のノードからε=遷移で接続されたノード、言い換えると複数のノードを結合する結合点を示すノードを合流ノードというものとする。図6の例では、合流ノード3jを=0で示している。すなわち、NFA生成部152は、合流ノード3jにて複数のノード3e、3iから遷移されるイベントaの受理時刻が同じものがあるか否かを判定させるようにする。図6の下段に示すように、NFA生成部152は、仮NFAから同系列関係のNFA部分を探索し、探索できた同系列関係のNFA部分を切り離す。そして、NFA生成部152は、切り離した同系列関係のNFA部分を複数系列分複製し、複製したそれぞれのNFA部分と任意系列関係のNFA部分との接合部分として接続ノードを生成する。そして、NFA生成部152は、生成した接続ノードと複製したそれぞれのNFA部分の接合部分とをすべてε遷移で接合し、生成した接続ノードと任意系列関係のNFA部分とをε遷移で接合する。ここでは、NFA生成部152は、ノード3bからノード3eまでの同系列AのNFA部分をN個の複数系列分複製する。また、NFA生成部152は、ノード3fからノード3iまでの同系列BのNFA部分をN個の複数系列分複製する。そして、NFA生成部152は、複製したNFA部分の遷移を各系列のイベントで受理する遷移に置き換える。また、NFA生成部152は、接合部分として接続ノード3kを生成し、生成した接続ノード3kと複製したNFA部分の接合部分とをそれぞれε遷移で接合する。なお、図6の下段に示した同系列NFA変換に基づくNFAは、図7で示すようなNFAであっても良い。図7は、仮NFAにおいて同系列関係のNFA部分と任意系列関係との接合部分が同系列関係の途中に存在する場合のNFAの変形例である。すなわち、NFA生成部152は、生成した接続ノード3kと複製した同系列AのNFA部分の接合部とをすべてε遷移で接合する。そして、NFA生成部152は、生成した接続ノードと複製した同系列BのNFA部分の接合部とをε遷移で接合する代わりに、生成した接続ノードと複製した同系列BのNFA部分の接合部とを間隔条件付きの遷移で直接接続する。これにより、接続ノードからのε遷移を省略できるので、接続ノードから遷移する数をN個から1個に削減できる。図8は、先頭で2つの接続部分があるイベントパターンに対するNFAを示す。なお、図8では、a、b、c、eはイベントを指し、x、w、zはイベント間隔の間隔条件を指すものとする。図8の上段に示すように、イベントパターン141は、任意の系列でイベントaが発生した後x以内に任意の系列でbが発生するパターンである。そして、イベントパターン141は、その後w以内にbと同じ系列でイベントeが発生するとともに、bと同じ系列でイベントcが発生し、その後z以内にbと同じ系列で先のイベントeと同じイベントeが発生するパターンである。すなわち、イベントeが合流部分となる。図8の中段に示すように、NFA生成部152は、イベントパターン141を仮NFAに変換する。ここでは、NFA生成部152は、イベントパターン141の中のイベントb、c、eのパターンについて、ノード4e~ノード4lで表される同系列の仮NFAに変換する。そして、NFA生成部152は、ノード4kおよびノード4jを受理時刻保持ノードとし、イベントeの受理時刻を、当該イベントeのそれぞれの遷移先を示す受理時刻保持ノードに対応付けて保持させる。そして、NFA生成部152は、ノード4kおよびノード4jから合流ノード4lへそれぞれε=遷移で接続する。図8の下段に示すように、NFA生成部152は、仮NFAから同系列関係のNFA部分を探索し、探索できた同系列関係のNFA部分を切り離す。そして、NFA生成部152は、切り離した同系列関係のNFA部分を複数系列分複製し、複製したそれぞれのNFA部分を各系列のイベントで受理する遷移に置き換える。そして、NFA生成部152は、置き換えたそれぞれのNFA部分をε遷移で結合する。ここでは、NFA生成部152は、仮NFAのノード4eからノード4lまでの同系列関係のNFA部分をN個の複数系列分複製し、複製したNFA部分の遷移を各系列のイベントで受理する遷移に置き換える。また、NFA生成部152は、複製したNFA部分をε遷移で結合する。図9は、同一系列のイベントにおけるパターンと任意系列のイベントにおけるパターンとが同じイベントで合流するイベントパターンに対するNFAを示す。なお、図9では、a、b、c、eはイベントを指し、x、y、zはイベント間隔の間隔条件を指すものとする。図9の上段に示すように、イベントパターン141は、同一系列でイベントaおよびイベントcが発生し、イベントaが発生した後x以内且つイベントcが発生した後z以内にこの系列でイベントeが発生するパターンである。そして、イベントパターン141は、任意の系列でイベントbが発生した後y以内に先のイベントeが発生するパターンである。図9の中段に示すように、NFA生成部152は、イベントパターン141を仮NFAに変換する。ここでは、NFA生成部152は、イベントパターン141の中のイベントa、c、eのパターンについて、ノード5b~ノード5jで表される同系列の仮NFAに変換する。そして、NFA生成部152は、ノード5hおよびノード5iを受理時刻保持ノードとし、イベントeの受理時刻を、当該イベントeのそれぞれの遷移先を示す受理時刻保持ノード5h、5iに対応付けて保持させる。また、NFA生成部152は、イベントパターン141の中のイベントb、eのパターンについて、ノード5a、5k、5l、5m、5nで表される仮NFAに変換する。そして、NFA生成部152は、ノード5nを受理時刻保持ノードとし、イベントeの受理時刻を、当該イベントeの遷移先を示す受理時刻保持ノードに対応付けて保持させる。ここで、NFA生成部152は、同系列関係に隣接する合流部分を同系列関係として扱う。ここでは、NFA生成部152は、同系列関係に隣接する合流部分であるノード5nをイベントa、c、eが発生した系列と同系列関係として生成する。図9の下段に示すように、NFA生成部152は、仮NFAから同系列関係のNFA部分を探索し、探索できた同系列関係のNFA部分を切り離す。そして、NFA生成部152は、切り離した同系列関係のNFA部分を複数系列分複製し、複製したそれぞれのNFA部分を各系列のイベントで受理する遷移に置き換える。そして、NFA生成部152は、置き換えたそれぞれのNFA部分をε遷移で結合する。ここでは、NFA生成部152は、仮NFAのノード5bからノード5jまでの同系列関係のNFA部分をN個の複数系列分複製し、複製したNFA部分の遷移を各系列のイベントで受理する遷移に置き換える。また、NFA生成部152は、同系列関係として扱うノード5nについて、ノード5nとε遷移で接続するノードをN個の複数系列分複製する。そして、NFA生成部152は、複製したNFA部分をε遷移で結合する。図2に戻って、照合部153は、NFA142を利用して、イベントストリーム143を照合する処理部である。例えば、照合部153は、イベントストリーム143に含まれるイベントについて、NFA142内の複製系列分複製された同系列関係のNFA部分では、イベントが発生した系列に対応したNFA部分で受理し、受理したNFA部分を動作させる。また、照合部153は、イベントストリーム143に含まれるイベントについて、NFA142内の任意系列関係のNFA部分では、イベントが発生した系列に関係なく受理し、受理したNFA部分を動作させる。そして、照合部153は、照合結果をユーザ端末50に通知する。図10に示すものは、イベントストリーム143に含まれるイベントがNFA142の各ノードから遷移する、イベントに対応する遷移種別を照合部153が判定する遷移種別判定テーブルのデータ構造である。なお、図10に示すIDとは、系列を一意に表す識別子を指すものとする。遷移種別判定テーブルは、遷移種別と、ID指定あり遷移と、ID指定なし遷移とを対応付けて記憶する。遷移種別には、間隔条件付き遷移と間隔条件なし遷移とがある。ID指定あり遷移は、NFA142の各ノードから出ている遷移であってIDが指定されている遷移を意味し、入力イベントとの関係でイベントとID一致およびイベントとID非一致がある。ここで、イベントとID一致とは、ノードから出ている遷移に係るイベントと入力イベントそのものが一致し、且つノードから出ている遷移に係るIDと入力イベントが発生したIDが一致する場合を意味する。イベントとID非一致とは、どちらか一方でも一致しない場合を意味する。ID指定なし遷移は、NFA142の各ノードから出ている遷移であってIDが指定されていない遷移を意味する。イベントとID一致では、ノードから出ている遷移の遷移種別が間隔条件付き遷移の場合、イベントに対応する遷移種別を当該間隔条件付き遷移と判定させる。また、ノードから出ている遷移の遷移種別が間隔条件なし遷移の場合、イベントに対応する遷移種別を当該間隔条件なし遷移と判定させる。イベントとID非一致では、ノードから出ている遷移の遷移種別が間隔条件付き遷移であっても間隔条件なし遷移であっても遷移なしと判定させる。ID指定なし遷移では、ノードから出ている遷移の遷移種別が間隔条件付き遷移の場合、イベントに対応する遷移種別を当該間隔条件付き遷移と判定させる。また、ノードから出ている遷移の遷移種別が間隔条件なし遷移の場合、イベントに対応する遷移種別を当該間隔条件なし遷移と判定させる。[実施例に係るNFA生成部におけるNFA構築の処理手順]次に、実施例に係るNFA生成部152におけるNFA構築の処理手順を、図11~図18を参照して説明する。図11はNFA生成部におけるNFA構築の主処理の手順を示す。図12~図16はNFA生成部152における仮NFA変換処理の手順を示す。図17はNFA生成部152における同系列NFA探索処理の手順を示す。図18はNFA生成部152における同系列NFA変換処理の手順を示す。[NFA構築の主処理の手順]まず、NFA構築の主処理の手順について、図11を参照して説明する。図11は、実施例に係るNFA生成部におけるNFA構築の主処理の手順を示すフローチャートである。図11に示す処理は、例えば、イベントのパターンPを入力とし、NFAを指すNPを出力とする。まず、NFA生成部152は、イベントパターンPを仮NFA変換し、仮NFAを指すNP ́を生成するステップS10A。続いて、NFA生成部152は、生成した仮NFAに未処理の同系列のNFA部分があるか否かを判定するステップS10B。仮NFAに未処理の同系列のNFA部分があると判定した場合ステップS10B;Yes、NFA生成部152は、未処理の同系列のNFA部分を仮NFAから切り離す。そして、NFA生成部152は、各切り離された側のノードと、生成した接続ノードをε遷移で連結し、切り離した同系列のNFA部分を同系列対応のNFAに変換する。そして、NFA生成部152は、各切り離した先頭ノードと、生成した接続ノードをε遷移で連結するステップS10C。そして、NFA生成部152は、未処理の同系列のNFA部分を処理すべく、ステップS10Bに移行する。ステップS10Bにおいて、仮NFAに未処理の同系列のNFA部分がないと判定した場合ステップS10B;No、NFA生成部152は、NFA構築処理を終了する。[仮NFA変換処理の手順]次に、図11のステップS10Aに示した仮NFA変換処理について、図12~図16を参照して説明する。図12~図16はNFA生成部152における仮NFA変換処理の手順を示すフローチャートである。図12に示す処理は、イベントのパターンPを入力とし、仮NFAを指すNP ́を出力とする。そして、ノード番号を変数iとし、番号を変数jとする。ここで、ノード番号とは、各ノードに割り振られるユニークな番号であり、状態番号と同じ意味を示す。状態の種類には、ノードに応じて、例えば、初期状態、最終状態がある。番号とは、受理時刻保持ノードノードに対応する番号を示す。まず、NFA生成部152は、ノード番号を0とする初期状態のノードを生成し、生成したノードに空のリストを登録する。そして、NFA生成部152は、現ノード番号iの値を0に設定し、現番号jの値を0に設定するステップS11。なお、リストとは、番号とタイムアウトの期間とを対応付けたリストである。そして、NFA生成部152は、入力されたパターンPに示されたイベント以降、イベント受理制約と同義の内、イベントの前に間隔制約がないものを集め、仮のイベント集合仮イベント集合とするステップS12。なお、間隔制約とは、間隔条件と同じ意味であるものとする。そして、NFA生成部152は、初期状態のノードを起点ノードとして、仮イベント集合に集めたイベント受理制約について、サブルーチン処理を行なうステップS13。その後、サブルーチン処理が終了すると、NFA生成部152は、終端ノードリストにノードが2つ以上あるか否かを判定するステップS14。なお、終端ノードリストは、終端となるノードを集めたリストであり、サブルーチン処理で作成される。終端ノードリストにノードが2つ以上あると判定した場合ステップS14;Yes、NFA生成部152は、最終状態のノードを生成し、生成したノードに、現ノード番号iに1を加算した値を割り当てる。そして、NFA生成部152は、終端ノードリストに含まれるそれぞれのノードから、生成した最終状態のノードへε=遷移で接続するステップS15。そして、NFA生成部152は、終端ノードリストに含まれる異なるノードについて、各ノードのリストを取り出す。そして、NFA生成部152は、取り出したリストに存在する共通の番号を指定番号として、タイムアウトの中で一番大きいものをタイムアウト長として最終状態のノードに登録しステップS16、仮NFA変換処理を終了する。一方、終端ノードリストにノードが2つ以上ないと判定した場合ステップS14;No、NFA生成部152は、終端ノードリストのノードを最終状態ノードとしステップS17、仮NFA変換処理を終了する。[サブルーチン処理の手順]次に、図12のステップS13に示したサブルーチン処理について、図13~図16を参照して説明する。図13~図16は、サブルーチン処理の手順を示すフローチャートである。NFA生成部152は、起点ノードが初期状態のノードでない、且つ仮イベント集合に集めたイベント受理制約が2つ以上であるか否かを判定するステップS131。起点ノードが初期状態のノードである場合、又は、起点ノードが初期状態のノードでない、且つ仮イベント集合に集めたイベント受理制約が2つ以上でない場合ステップS131;No、NFA生成部152は、ステップS132に移行する。ステップS132では、NFA生成部152が、集めた各イベント受理制約に対応するイベントを入力するノード以降、イベント入力ノードという。を生成する。そして、NFA生成部152は、現ノード番号iに1を加算しながら、現ノード番号iを生成したノードに割り当てる。そして、NFA生成部152は、起点ノードから、生成したイベント入力ノードへε遷移で接続する。すなわち、NFA生成部152は、起点ノードからイベント入力ノードへの遷移をε遷移とする。さらに、NFA生成部152は、起点ノードのリストを、生成したノードのリストにコピーするステップS132。一方、起点ノードが初期状態のノードでない、且つ仮イベント集合に集めたイベント受理制約が2つ以上である場合ステップS131;Yes、NFA生成部152は、ステップS133に移行する。すなわち、仮イベント集合に集めたイベント受理制約が分岐するようなパターン分岐パターンとなるイベント受理制約である場合である。ステップS133では、NFA生成部152が、起点ノードに現番号jを割り当て、番号jに1を加算するステップS133。すなわち、この起点ノードは、分岐の起点となるイベントの受理時刻を保持する受理時刻保持ノードとなる。そして、NFA生成部152は、起点ノードのリストに、割り当てた番号およびタイムアウト0を設定しステップS134、ステップS132に移行する。ステップS132の処理後、NFA生成部152は、仮イベント集合に集めたイベント受理制約の中で未処理のものがあるか否かを判定するステップS135。集めたイベント受理制約の中で未処理のものがない場合ステップS135;No、NFA生成部152は、サブルーチン処理を終了する。一方、集めたイベント受理制約の中で未処理のものがある場合ステップS135;Yes、NFA生成部152は、集めたイベント受理制約から未処理のイベント受理制約を1つ取り出すステップS136。そして、NFA生成部152は、現在のイベント受理制約に付随する前方間隔制約があるか否かを判定するステップS137。現在のイベント受理制約に付随する前方の間隔制約がない場合ステップS137;No、NFA生成部152は、現ノード番号iに1を加算し、イベント受理完了ノードを生成し、生成したノードに、加算した現ノード番号を割り当てる。そして、NFA生成部152は、指定したイベントの受理によりイベント入力ノードからイベント受理完了ノードに遷移するエッジで接続する。すなわち、NFA生成部152は、イベント入力ノードからイベント受理完了ノードへの遷移を間隔条件なしの通常遷移とする。さらに、NFA生成部152は、イベント入力ノードのリストをイベント受理完了ノードのリストにコピーするステップS138。その後、NFA生成部152は、ステップS143に移行する。一方、現在のイベント受理制約に付随する前方間隔制約がある場合ステップS137;Yes、NFA生成部152は、現ノード番号iに1を加算し、イベント受理完了ノードを生成し、生成したノードに、加算した現ノード番号を割り当てる。そして、NFA生成部152は、前方間隔制約を満たすイベントの受理で、イベント入力ノードからイベント受理完了ノードに遷移するエッジで接続する。すなわち、NFA生成部152は、イベント入力ノードからイベント受理完了ノードへの遷移を間隔条件付きの通常遷移とする。さらに、NFA生成部152は、イベント入力ノードのリストの各タイムアウトに前方間隔制約を加えてから、生成したイベント受理完了ノードのリストにコピーするステップS139。その後、NFA生成部152は、ステップS141に移行する。ステップS141では、NFA生成部152は、現在のイベント受理制約に付随する前方間隔制約の種別が同系列関係であるか否かを判定するステップS141。現在のイベント受理制約に付随する前方間隔制約の種別が同系列関係であると判定した場合ステップS141;Yes、NFA生成部152は、イベント入力ノードに同系列関係情報を付加しステップS142、ステップS143に移行する。一方、現在のイベント受理制約に付随する前方間隔制約の種別が同系列関係でないと判定した場合ステップS141;No、NFA生成部152は、ステップS143に移行する。ステップS143では、NFA生成部152は、現在のイベント受理制約の後方間隔制約の中で同系列関係のものがあるか否かを判定するステップS143。現在のイベント受理制約の後方間隔制約の中で同系列関係のものがあると判定した場合ステップS143;Yes、NFA生成部152は、イベント受理完了ノードに同系列関係情報を付加しステップS144、ステップS151に移行する。一方、現在のイベント受理制約の後方間隔制約の中で同系列関係のものがないと判定した場合ステップS143;No、NFA生成部152は、ステップS151に移行する。続いて、NFA生成部152は、現在のイベント受理制約の前方間隔制約の数をFに設定するステップS151。そして、NFA生成部152は、Fの値が2以上であるか否かを判定するステップS152。Fの値が2以上でない場合ステップS152;No、NFA生成部152は、生成したイベント受理完了ノードを完了ノードとするステップS153。その後、NFA生成部152は、現在のイベント受理制約の後方間隔制約における処理を行うべく、ステップS161に移行する。一方、Fの値が2以上である場合ステップS152;Yes、NFA生成部152は、現在のイベント受理制約に対応する生成済みのイベント受理完了ノードの数がFの値と一致するか否かを判定するステップS154。現在のイベント受理制約に対応する生成済みのイベント受理完了ノードの数がFの値と一致しない場合ステップS154;No、NFA生成部152は、集めたイベント受理制約の中で未処理のイベント受理制約の処理をすべく、ステップS135に移行する。一方、現在のイベント受理制約に対応する生成済みのイベント受理完了の数がFの値と一致する場合ステップS154;Yes、NFA生成部152は、現ノード番号iに1を加算し、現在のイベント受理制約に対応する合流ノードを生成する。そして、NFA生成部152は、現在のイベント受理制約に対応する生成済みの全てのイベント受理完了ノードから、生成した合流ノードへε=遷移で接続するステップS155。すなわち、NFA生成部152は、イベント受理完了ノードから合流ノードへの遷移をε=遷移とする。そして、NFA生成部152は、合流ノードに同系列関係情報を付加するステップS156。続いて、NFA生成部152は、現在の番号jおよびタイムアウト0を現在のイベント受理制約に対応する生成済みの全てのイベント受理完了ノードに割り当て、それぞれのリストに追加する。すなわち、これら生成済みの全てのイベント受理完了ノードは、イベントの受理時刻を保持する受理時刻保持ノードとなる。さらに、NFA生成部152は、は、番号jに1を加算するステップS157。続いて、NFA生成部152は、現在のイベント受理制約に対応する生成済みのイベント受理完了ノードのリストにおいて、複数の生成済みのイベント受理完了ノードが持っている同一の番号を合流ノードの指定番号とする。そして、NFA生成部152は、タイムアウトの中で一番大きい値をタイムアウト長として、番号とともに合流ノードに対応付けて登録するステップS158。続いて、NFA生成部152は、現在のイベント受理制約に対応する生成済みのイベント受理完了ノードのリストに含まれる番号および各番号で最大のタイムアウトを重複なく合流ノードのリストに設定するステップS159。そして、NFA生成部152は、合流ノードを完了ノードとしステップS160、現在のイベント受理制約の後方間隔制約における処理を行うべく、ステップS161に移行する。ステップS161では、NFA生成部152が、ステップS136で取り出したイベント受理制約の後方への間隔制約を持つイベント受理制約を、前方間隔制約と前方間隔制約の種別と共に集め、仮イベント集合とするステップS161。そして、NFA生成部152は、仮イベント集合に集めたイベント受理制約が1つ以上であるか否かを判定するステップS162。集めたイベント受理制約が1つ以上でない場合、すなわち0である場合ステップS162;No、NFA生成部152は、終端ノードリストに完了ノードを追加するステップS163。その後、NFA生成部152は、集めたイベント受理制約の中で未処理のイベント受理制約の処理をすべく、ステップS135に移行する。一方、集めたイベント受理制約が1つ以上である場合ステップS162;Yes、NFA生成部152は、完了ノードを起点ノードとして、仮イベント集合に集めたイベント受理制約について、サブルーチン処理を再帰的に行うステップS164。その後、NFA生成部152は、集めたイベント受理制約の中で未処理のイベント受理制約の処理をすべく、ステップS135に移行する。[同系列NFA探索処理の手順]次に、図11のステップS10Bに示した同系列NFA探索処理について、図17を参照して説明する。図17は、同系列NFA探索処理の手順を示すフローチャートである。図17に示す処理は、仮NFAを指すNP ́を入力とし、仮NFAにおいて同系列関係を有するNFA部分のノードの集合同系列ノード集合の組を出力とする。NFA生成部152は、入力された仮NFAの初期状態のノードを現在のノードとするステップS21。そして、NFA生成部152は、現在のノードと接続する未処理の遷移があるか否かを判定するステップS22。現在ノードと接続する未処理の遷移があると判定した場合ステップS22;Yes、NFA生成部152は、あると判定した未処理の遷移がε遷移であるか否かを判定するステップS23。未処理の遷移がε遷移であると判定した場合ステップS23;Yes、NFA生成部152は、現在のノードと遷移先遷移元ノードがともに同系列関係であるか否かを判定するステップS24。一方、未処理の遷移がε遷移でないと判定した場合ステップS23;No、NFA生成部152は、現在のノードあるいは遷移先遷移元ノードが同系列関係であるか否かを判定するステップS25。現在のノードと遷移先遷移元ノードがともに同系列関係である場合ステップS24;Yes、またはどちらか一方が同系列関係である場合ステップS25;Yes、NFA生成部152は、次の処理を行う。NFA生成部152は、現在のノードと遷移先遷移元ノードを同系列ノード集合に追加するステップS26。一方、現在のノードと遷移先遷移元ノードがともに同系列関係でない場合ステップS24;No、またはどちらも同系列関係でない場合ステップS25:No、NFA生成部152は、遷移先遷移元ノードを未処理ノード集合に追加するステップS27。そして、NFA生成部152は、現在のノードと接続する未処理の遷移について処理すべく、ステップS22に移行する。ステップS22では、現在ノードと接続する未処理の遷移がないと判定した場合ステップS22;No、NFA生成部152は、同系列ノード集合に含まれるノードをすべて処理したか否かを判定するステップS28。同系列ノード集合に含まれるノードをすべて処理していないと判定した場合ステップS28;No、NFA生成部152は、同系列ノード集合の中で未処理のノードの1つを現在のノードとするステップS30。そして、NFA生成部152は、ステップS22に移行する。一方、同系列ノード集合に含まれるノードをすべて処理したと判定した場合ステップS28;Yes、NFA生成部152は、同系列ノード集合を出力し、出力後同系列ノード集合を空にするステップS29。そして、NFA生成部152は、未処理ノード集合の中に最終状態ノードを除く未処理のノードがあるか否かを判定するステップS31。未処理ノード集合に最終状態ノードを除く未処理のノードがある場合ステップS31;Yes、NFA生成部152は、未処理ノード集合の中の最終状態ノードを除く系列IDの一番小さい未処理のノードを現在のノードとするステップS32。そして、NFA生成部152は、ステップS22に移行する。一方、未処理ノード集合に最終状態ノードを除く未処理のノードがない場合ステップS31;No、NFA生成部152は、同系列NFA探索処理を終了する。[同系列NFA変換処理の手順]次に、図11のステップS10Cに示した同系列NFA変換処理について、図18を参照して説明する。図18は、同系列NFA変換処理の手順を示すフローチャートである。図18に示す処理は、仮NFAを指すNP ́および同系列ノード集合の組を入力とし、NFAを指すNPを出力とする。NFA生成部152は、入力された同系列ノード集合の組が空であるか否かを判定するステップS41。同系列ノード集合の組が空でないと判定した場合ステップS41;No、NFA生成部152は、同系列ノード集合の組から同系列ノード集合を1つ取り出すステップS42。そして、NFA生成部152は、同系列ノード集合に未処理のノードがあるか否かを判定するステップS43。同系列ノード集合に未処理のノードがあると判定した場合ステップS43;Yes、NFA生成部152は、同系列ノード集合の未処理の1ノードを現在のノードとするステップS44。そして、NFA生成部152は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがあるか否かを判定するステップS45。現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがあると判定した場合ステップS45;Yes、NFA生成部152は、新しいノードを生成し、現在のノードの代わりに、生成したノードと先の同系列ノード集合にないノードとをそのままの遷移制約等で接続する。そして、NFA生成部152は、現在のノードと生成したノードとこれら2つのノードの遷移方向の組とを、同系列の部分と同系列でない部分とが切り離された境界のノードの組を集めた境界ノード組集合に加えるステップS46。ここで、NFA生成部152は、現在のノードの代わりに生成したノードが現在のノードの前方にある場合には、該生成したノードから現在のノードへの遷移方向とする。一方、NFA生成部152は、現在のノードの代わりに生成したノードが現在のノードの後方にある場合には、現在のノードから該生成したノードへの遷移方向とする。そして、NFA生成部152は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のノードを判定すべく、ステップS45に移行する。一方、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがないと判定した場合ステップS45;No、NFA生成部152は、同系列ノード集合の未処理のノードを判定すべく、ステップS43に移行する。一方、同系列ノード集合に未処理のノードがないと判定した場合ステップS43;No、NFA生成部152は、同系列ノード集合のノードおよびそのノード間の遷移エッジすべてを1セットとして、系列数分だけ複製する。そして、NFA生成部152は、各系列のイベントで受理する遷移に置き換えるステップS47。すなわち、NFA生成部152は、間隔条件付きの通常遷移および間隔条件なしの通常遷移を各系列のイベントでのみ受理されるように置き換える。続いて、NFA生成部152は、境界ノード組集合に未処理の組があるか否かを判定するステップS48。境界ノード組集合に未処理の組があると判定した場合ステップS48;Yes、NFA生成部152は、境界ノード組集合から未処理の1組を取り出すステップS49。そして、NFA生成部152は、取り出した1組の現在のノードと生成ノードと遷移方向とに従い、現在のノードに対応する複製したすべてのノードと生成ノードとを遷移方向どおりにすべてε遷移で接続するステップS50。そして、NFA生成部152は、境界ノード組集合に未処理の組があるか否かを判定すべく、ステップS48に移行する。一方、境界ノード組集合に未処理の組がないと判定した場合ステップS48;No、NFA生成部152は、次の同系列ノード集合の処理をすべく、ステップS41に移行する。ステップS41では、同系列ノード集合の組が空であると判定した場合ステップS41;Yes、NFA生成部152は、以下のようにノード番号を振りなおす。すなわち、NFA生成部152は、系列IDの大小関係を保ちつつ、境界ノード組集合の遷移元が小さいノード番号となるように、一意なノード番号を振りなおすステップS51。そして、NFA生成部152は、同系列NFA変換処理を終了する。[NFAを生成する処理の一例]次に、あるパターンをイベントパターン141とした場合に、図11~図18に示したNFAの構築法を用いて、NFA生成部152が、イベントパターン141からNFA142を生成する処理の一例について説明する。図19A~図19Dは、仮NFAを生成する処理を説明する図である。図20A~図20Fは、同系列のNFAを探索する処理を説明する図である。図21A~図21Gは、同系列のNFAを変換する処理を説明する図である。[仮NFA生成処理の説明]図19Aに示すように、イベントパターン141のデータ構造を、符号201pに示すものとする。イベントパターン141は、任意の系列でイベントAが発生し、その後2以内にAと同じ系列でイベントBが発生する。そして、イベントパターン141は、任意の系列でイベントAが発生した後5以内に任意の系列でCが発生するパターンである。図19Bの1段目に示すように、NFA生成部152は、ノード番号を0とする初期状態のノード6aを生成し、生成したノード6aに空のリストを登録する。そして、NFA生成部152は、現ノード番号iの値を0に設定し、現番号jの値を0に設定する。そして、NFA生成部152は、入力されたイベントパターン141に示されたイベント受理制約の内、前に間隔制約がないものを集め、仮イベント集合とする。ここでは、NFA生成部152は、イベントAのイベント受理制約を仮イベント集合とする。そして、NFA生成部152は、初期状態のノード6aを起点ノードとする。図19Bの2段目に示すように、NFA生成部152は、起点ノードが初期状態のノード6aであるので、仮イベント集合に集められたイベント受理制約Aに対応するイベント入力ノード6bを生成する。そして、NFA生成部152は、生成したノード6bに現ノード番号iに1を加算した値1を割り当てる。そして、NFA生成部152は、起点ノード6aからイベント入力ノード6bへε遷移で接続する。図19Bの3段目に示すように、NFA生成部152は、仮イベント集合に集められたイベント受理制約Aから未処理のイベント受理制約を1つ取り出す。ここでは、NFA生成部152はイベントAを取り出す。そして、NFA生成部152は、イベント受理完了ノード6cを生成し、生成したノード6cに、現ノード番号iに1を加算した値2を割り当てる。そして、NFA生成部152は、イベントAの受理によりイベント入力ノード6bからイベント受理完了ノード6cに遷移するエッジで接続する。すなわち、イベント入力ノード6bからイベント受理完了ノード6cへの遷移が間隔条件なしの通常遷移となる。さらに、NFA生成部152は、イベント入力ノード6bのリストをイベント受理完了ノード6cのリストにコピーする。図19Bの4段目に示すように、NFA生成部152は、現在のイベント受理制約Aの後方間隔制約の中で同系列関係のものBがあるので、イベント受理完了ノード6cに同系列関係情報=を付加する。続いて、NFA生成部152は、現在のイベント受理制約Aの前方の間隔制約の数をFとする。ここでは、NFA生成部152は、イベントAの前方の間隔に制約がないので、Fを0に設定する。そして、NFA生成部152は、Fが2以上でないので、イベント受理完了ノード6cを完了ノードとする。さらに、NFA生成部152は、取り出したイベント受理制約Aの後方への間隔制約を持つイベント受理制約を前方間隔制約と前方間隔制約種別と共に集め、仮イベント集合とする。前方間隔制約種別とは、前方間隔制約に付随する種別であって同系列の遷移関係か任意系列の遷移関係かを区別する種別である。ここでは、NFA生成部152は、イベントAの後方イベントBまでの間隔制約が2であり、同系列の遷移関係であるので、イベント受理制約Bを前方間隔制約2と同系列の遷移関係の制約であることを示す種別と共に仮イベント集合に設定する。また、NFA生成部152は、イベントAの後方イベントCまでの間隔制約が5であり、任意系列の遷移関係であるので、イベント受理制約Cを前方間隔制約5と任意系列の遷移関係の制約であることを示す種別と共に仮イベント集合に設定する。そして、NFA生成部152は、完了ノード6cを起点ノードとする。図19Cの1段目に示すように、NFA生成部152は、起点ノード6cが初期状態のノードでなく、且つ仮イベント集合に集められたイベント受理制約B、Cが2つ以上であるので、起点ノード6cに現番号jの値0を割り当てる。すなわち、この起点ノード6cは、番号00を有する受理時刻保持ノードとなる。そして、NFA生成部152は、現番号jの値を、1加算した値1に設定する。図19Cの2段目に示すように、NFA生成部152は、起点ノード6cのリスト1mに、割り当てた番号0およびタイムアウト0を設定する。図19Cの3段目に示すように、NFA生成部152は、仮イベント集合に集められたイベント受理制約B、Cに対応するイベント入力ノード6d、6eを生成する。そして、NFA生成部152は、生成したノード6dに現ノード番号i2に1を加算した値3を割り当て、生成したノード6eにさらに現ノード番号i3に1を加算した値4を割り当てる。そして、NFA生成部152は、起点ノード6cからイベント入力ノード6dへε遷移で接続し、起点ノード6cからイベント入力ノード6eへε遷移で接続する。そして、NFA生成部152は、起点ノード6cのリストをイベント入力ノード6d、6eのそれぞれのリストにコピーする。図19Cの4段目に示すように、NFA生成部152は、仮イベント集合に集められたイベント受理制約B、Cから未処理のイベント受理制約を1つ取り出す。ここでは、NFA生成部152はイベントBを取り出す。そして、NFA生成部152は、イベント受理完了ノード6fを生成し、生成したノード6fに、現ノード番号iに1を加算した値5を割り当てる。そして、NFA生成部152は、前方間隔制約2を満たすイベントBの受理によりイベント入力ノード6dからイベント受理完了ノード6fに遷移するエッジで接続する。すなわち、イベント入力ノード6dからイベント受理完了ノード6fへの遷移が間隔条件付きの通常遷移となる。さらに、NFA生成部152は、イベント入力ノード6dのリストのタイムアウトに前方間隔制約2を加えてからイベント受理完了ノード6fのリストにコピーする。図19Cの5段目に示すように、NFA生成部152は、現在のイベント受理制約Bに付随する前方間隔制約種別が同系列関係であるので、イベント入力ノード6dに同系列関係情報=を付加する。続いて、NFA生成部152は、現在のイベント受理制約Bの前方の間隔制約の数をFとする。ここでは、イベントBの前方間隔制約は2のものだけであるので、NFA生成部152は、前方の間隔制約の数Fを1に設定する。そして、NFA生成部152は、Fが2以上でないので、イベント受理完了ノード6fを完了ノードとする。さらに、NFA生成部152は、取り出したイベント受理制約Bの後方への間隔制約を持つイベント受理制約を集め、仮イベント集合とする。ここでは、NFA生成部152は、イベントBの後方への間隔制約を持つイベント受理制約がないので、空の仮イベント集合とする。そして、NFA生成部152は、仮イベント集合が空なので、終端ノードリストに完了ノード6fを追加する。ここで、イベント受理制約Bの処理が終了する。図19Dの1段目に示すように、NFA生成部152は、仮イベント集合に集められたイベント受理制約B、Cから未処理のイベント受理制約を1つ取り出す。ここでは、NFA生成部152は、イベントBの処理が終了しているので、未処理のイベントCを取り出す。そして、NFA生成部152は、イベント受理完了ノード6gを生成し、生成したノード6gに、現ノード番号iに1を加算した値6を割り当てる。そして、NFA生成部152は、前方間隔制約5を満たすイベントCの受理によりイベント入力ノード6eからイベント受理完了ノード6gに遷移するエッジで接続する。すなわち、イベント入力ノード6eからイベント受理完了ノード6gへの遷移が間隔条件付きの通常遷移となる。さらに、NFA生成部152は、イベント入力ノード6eのリストのタイムアウトに前方間隔制約5を加えてからイベント受理完了ノード6gのリストにコピーする。続いて、NFA生成部152は、現在のイベント受理制約CもイベントBと同様に、前方の間隔制約の数が1つで、後方の間隔制約がないので、終端ノードリストに完了ノード6gを追加する。すなわち、終端ノードリストには、完了ノード6f、6gがある。ここで、イベント受理制約Cの処理が終了する。この結果、イベント受理制約Aの処理が終了する。続いて、NFA生成部152は、仮イベント集合に集められたイベント受理制約B、Cの処理が終了したので、元の仮イベント集合および元の起点ノードに戻す。すなわち、起点ノードは初期状態のノード6aとなり、仮イベント集合はイベント受理制約Aを含んだものになる。図19Dの2段目に示すように、NFA生成部152は、戻した仮イベント集合に含まれるイベント受理制約Aの処理を終了しているので、最終状態のノード6hを生成し、生成したノード6hに、現ノード番号iに1を加算した値7を割り当てる。そして、NFA生成部152は、終端ノードリストに含まれるそれぞれの完了ノード6f、6gから、生成した最終状態のノード6hへε=遷移で接続する。図19Dの5段目に示すように、NFA生成部152は、終端ノードリストに含まれる異なるノードについて、各ノードのリストを取り出す。ここでは、NFA生成部152は、終端ノードリストに含まれる完了ノード6f、6gのリストを取り出す。そして、NFA生成部152は、取り出したリストに存在する共通の番号を指定番号として、タイムアウトの中で一番大きいものをタイムアウト長として最終状態のノード6hに登録する。ここでは、完了ノード6fのリストには、番号0とタイムアウト長2とが対応付けられ、完了ノード6gのリストには、番号0とタイムアウト長5とが対応付けられている。このため、NFA生成部152は、指定番号を0として、タイムアウト長を5として最終状態のノード6hに登録する。上述したように、NFA生成部152は、図19A~図19Dに示す処理を実行することで、図19Aに示すイベントパターン141から仮NFAを生成する。[同系列NFA探索処理の説明]次に、同系列NFA探索処理について説明する。図20Aの1段目に示すように、NFA生成部152は、生成した仮NFAの初期状態ノード6aを現在のノードとする。また、NFA生成部152は、未処理ノード集合および同系列ノード集合を空にする。ここで、未処理ノード集合とは、各ノードの遷移について同系列関係であるか否かの探索処理が行われていないノードの集合を意味する。同系列ノード集合とは、同系列関係のノードの集合を意味する。図20Aの2段目に示すように、NFA生成部152は、現在のノード6aと接続する未処理の遷移がε遷移であるので、現在のノード6aと遷移先のノード6bがともに同系列関係であるか否かを判定する。ここでは、NFA生成部152は、現在のノード6aと遷移先のノード6bがともに同系列関係情報=が付加されていないので、同系列関係で無いと判定する。そして、NFA生成部152は、遷移先のノード6bを未処理ノード集合に追加する。図20Aの3段目に示すように、NFA生成部152は、現在のノード6aと接続する未処理の遷移がなく、同系列ノード集合に含まれるノードが空であるので、同系列ノード集合を出力しない。図20Bの1段目に示すように、NFA生成部152は、未処理ノード集合の中の最終状態ノードを除くノード番号の一番小さい未処理のノードを現在のノードとする。ここでは、NFA生成部152は、未処理ノード集合の中のノード番号1のノード6bを現在のノードとする。図20Bの2段目に示すように、NFA生成部152は、現在のノード6aと接続する未処理の遷移が間隔条件なしの通常遷移であるので、現在のノード6bあるいは遷移先のノード6cが同系列関係であるか否かを判定する。ここでは、NFA生成部152は、遷移先のノード6cが同系列関係情報=が付加されているので、同系列関係であると判定する。そして、NFA生成部152は、現在のノード6bと遷移先のノード6cを同系列ノード集合に追加する。図20Bの3段目に示すように、NFA生成部152は、現在のノード6aと接続する未処理の遷移がないので、同系列ノード集合に含まれるノードがすべて処理したか否かを判定する。そして、NFA生成部152は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号2のノード6cを現在のノードとする。図20Cの1段目に示すように、NFA生成部152は、現在のノード6cと接続する未処理の遷移がε遷移であるので、現在のノード6cと遷移先のノードがともに同系列関係であるか否かを判定する。ここでは、NFA生成部152は、現在のノード6cと遷移先のノード6dがともに同系列関係情報=が付加されているので、同系列関係であると判定する。そして、NFA生成部152は、現在のノード6cと遷移先のノード6dを同系列ノード集合に追加する。また、NFA生成部152は、現在のノード6cには同系列関係情報=が付加されているが、遷移先のノード6eには付加されていないので、遷移先のノード6eを未処理ノード集合に追加する。図20Cの2段目に示すように、NFA生成部152は、現在のノード6cと接続する未処理の遷移がないので、同系列ノード集合に含まれるノードがすべて処理したか否かを判定する。そして、NFA生成部152は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号3のノード6dを現在のノードとする。図20Cの3段目に示すように、NFA生成部152は、現在のノード6dと接続する未処理の遷移が間隔条件付きの通常遷移であるので、現在のノード6dあるいは遷移先のノード6fが同系列関係であるか否かを判定する。ここでは、NFA生成部152は、現在のノード6dが同系列関係情報=が付加されているので、同系列関係であると判定する。そして、NFA生成部152は、現在のノード6dと遷移先のノード6fを同系列ノード集合に追加する。図20Dの1段目に示すように、NFA生成部152は、現在のノード6dと接続する未処理の遷移がないので、同系列ノード集合に含まれるノードがすべて処理したか否かを判定する。そして、NFA生成部152は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号5のノード6fを現在のノードとする。図20Dの2段目に示すように、NFA生成部152は、現在のノード6fと接続する未処理の遷移がε遷移でないので、現在のノード6fあるいは遷移先のノードが同系列関係であるか否かを判定する。ここでは、NFA生成部152は、現在のノード6fと遷移先のノード6hがどちらにも同系列関係情報=が付加されていない。そこで、NFA生成部152は、同系列関係でないと判定し、遷移先のノード6hを未処理ノード集合に追加する。図20Dの3段目に示すように、NFA生成部152は、現在のノード6fと接続する未処理の遷移がなく、同系列ノード集合に含まれるノードが空であるので、同系列ノード集合を出力する。ここでは、NFA生成部152は、ノード番号1、2、3、5のノードを同系列ノード集合として出力する。そして、NFA生成部152は、出力後、同系列ノード集合を空にする。図20Eの1段目に示すように、NFA生成部152は、未処理ノード集合の中の最終状態ノードを除くノード番号の一番小さい未処理のノードを現在のノードとする。ここでは、NFA生成部152は、未処理ノード集合の中のノード番号4のノード6bを現在のノードとする。図20Eの2段目に示すように、NFA生成部152は、現在のノード6bと接続する未処理の遷移が間隔条件付きの通常遷移であるので、現在のノードあるいは遷移先元ノードが同系列関係であるか否かを判定する。ここでは、NFA生成部152は、現在のノードあるいは遷移先元ノードが同系列関係でないと判定する。そして、NFA生成部152は、遷移先元ノード6c、6gを未処理ノード集合に追加する。図20Eの3段目に示すように、NFA生成部152は、現在のノード6eと接続する未処理の遷移がなく、同系列ノード集合に含まれるノードが空であるので、同系列ノード集合を出力しない。図20Fの1段目に示すように、NFA生成部152は、未処理ノード集合の中の最終状態ノードを除くノード番号の一番小さい未処理のノードを現在のノードとする。ここでは、NFA生成部152は、未処理ノード集合の中のノード番号6のノード6gを現在のノードとする。続いて、NFA生成部152は、現在のノード6gと接続する未処理の遷移がε遷移でないので、現在のノード6gあるいは遷移先のノードが同系列関係であるか否かを判定する。ここでは、NFA生成部152は、現在のノード6gと遷移先のノード6hがどちらにも同系列関係情報=が付加されていない。NFA生成部152は、同系列関係でないと判定し、遷移先のノード6hを未処理ノード集合に追加する。図20Fの2段目に示すように、NFA生成部152は、現在のノード6gと接続する未処理の遷移がなく、同系列ノード集合に含まれるノードが空であるので、同系列ノード集合を出力しない。そして、NFA生成部152は、未処理ノード集合に最終状態ノード6hを除く未処理のノードがあるか否かを判定する。ここでは、NFA生成部153は、未処理ノード集合に含まれる最終状態ノード6hノード番号7を除くノード番号1、4、2、6のノードはすべて処理されているので、未処理のノードがないと判定する。そして、NFA生成部152は、同系列NFA探索処理を終了する。上述したように、NFA生成部152は、図20A~図20Fに示す処理を実行することで、仮NFAから同系列ノード集合を出力する。すなわち、NFA生成部152は、ノード番号1、2、3、5のノードを1組とした同系列ノード集合を出力する[同系列NFA変換処理の説明]次に、同系列NFA変換処理について説明する。図21Aの1段目に示すように、NFA生成部152は、同系列ノード集合の組が空であるか否かを判定する。ここでは、NFA生成部152は、同系列ノード集合の組が存在するので空でないと判定する。そこで、NFA生成部152は、同系列ノード集合の組から1組の同系列ノード集合を取り出す。すなわち、NFA生成部152は、ノード番号1、2、3、5のノードを1組とした同系列ノード集合を取り出す。図21Bの1段目に示すように、NFA生成部152は、取り出した同系列ノード集合の未処理の1ノードを現在のノードとする。ここでは、NFA生成部152は、同系列ノード集合の中から未処理のノードであるノード番号1のノード6bを現在のノードとする。図21Bの2段目に示すように、NFA生成部152は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがあるか否かを判定する。ここでは、NFA生成部152は、現在のノード6bと接続されているノード6a、6bの中にノード番号0のノード6aが同系列ノード集合にない未処理のものであるので、未処理のものがあると判定する。そして、NFA生成部152は、新しいノード6b ́を生成し、現在のノード6bの代わりに生成したノード6b ́と先の同系列ノード集合にないノード6aとをそのままの遷移ε遷移で接続する。そして、NFA生成部152は、現在のノード6bと生成したノード6b ́とこれら2つのノードの遷移方向の組とを境界ノード組集合に加える。かかる場合は、生成したノード6b ́が現在のノード6bの前方にある場合であるので、NFA生成部152は、生成したノード6b ́から現在のノード6bへの遷移方向とする。図21Cの1段目に示すように、NFA生成部152は、同系列ノード集合の未処理の1ノードを現在のノードとする。ここでは、NFA生成部152は、同系列ノード集合の中から未処理のノードであるノード番号2のノード6cを現在のノードとする。図21Cの2段目に示すように、NFA生成部152は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがあるか否かを判定する。ここでは、NFA生成部152は、現在のノード6cと接続されているノード6b、6dの中にノード番号4のノード6eが同系列ノード集合にない未処理のものであるので、未処理のものがあると判定する。そして、NFA生成部152は、新しいノード6c ́を生成し、現在のノード6cの代わりに生成したノード6c ́と先の同系列ノード集合にないノード6eとをそのままの遷移ε遷移で接続する。そして、NFA生成部152は、現在のノード6cと生成したノード6c ́とこれら2つのノードの遷移方向の組とを境界ノード組集合に加える。かかる場合は、生成したノード6b ́が現在のノード6bの後方にある場合であるので、NFA生成部152は、現在のノード6cから、生成したノード6c ́への遷移方向とする。図21Dの1段目に示すように、NFA生成部152は、同系列ノード集合の未処理の1ノードを現在のノードとする。ここでは、NFA生成部152は、同系列ノード集合の中から未処理のノードであるノード番号3のノード6dを現在のノードとする。続いて、NFA生成部152は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがあるか否かを判定する。ここでは、NFA生成部152は、現在のノード6dと接続されているノード6c、6fの中に同系列ノード集合にない未処理のものでないので、未処理のものがないと判定する。図21Dの2段目に示すように、NFA生成部152は、同系列ノード集合の未処理の1ノードを現在のノードとする。ここでは、NFA生成部152は、同系列ノード集合の中から未処理のノードであるノード番号5のノード6fを現在のノードとする。図21Eの1段目に示すように、NFA生成部152は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがあるか否かを判定する。ここでは、NFA生成部152は、現在のノード6fと接続されているノード6d、6hの中にノード番号7のノード6hが同系列ノード集合にない未処理のものであるので、未処理のものがあると判定する。そして、NFA生成部152は、新しいノード6f ́を生成し、現在のノード6fの代わりに生成したノード6f ́と先の同系列ノード集合にないノード6hとをそのままの遷移ε遷移で接続する。そして、NFA生成部152は、現在のノード6fと生成したノード6f ́とこれら2つのノードの遷移方向の組とを境界ノード組集合に加える。かかる場合は、生成したノード6f ́が現在のノード6fの後方にある場合であるので、NFA生成部152は、現在のノード6fから、生成したノード6f ́への遷移方向とする。図21Eの2段目に示すように、NFA生成部152は、同系列ノード集合に未処理のノードがないので、同系列ノード集合のノードおよびそのノード間の遷移エッジすべてを1セットとして、系列数分だけ複製する。ここでは、系列数を3とすると、NFA生成部152は、同系列ノード集合のノード6b、6c、6d、6fおよびそのノード間の遷移エッジすべてを3系列数分複製する。そして、NFA生成部152は、ノード間の遷移を各系列のイベントで受理する遷移に置き換える。すなわち、NFA生成部152は、複製元の一段目の遷移を0系列のイベントで受理する遷移に置き換え、複製した2段目の遷移を1系列のイベントで受理する遷移に置き換え、複製した3段目の遷移を2系列のイベントで受理する遷移に置き換える。図21Fの1段目に示すように、NFA生成部152は、境界ノード組集合から未処理の1組の境界ノードの組を取り出す。ここでは、NFA生成部152は、境界ノード組集合から、ノード番号が1 ́である生成ノード6b ́からノード番号が1である現在のノード6bへの遷移方向の境界ノードの組を取り出す。そして、NFA生成部152は、取り出した1組の現在のノードと生成ノードと遷移方向に従い、現在のノードに対応する複製したすべてのノードと生成ノードを遷移方向どおりにすべてε遷移で接続する。ここでは、NFA生成部152は、現在のノード6bに対応する、複製した3系列のノード6bと生成ノード6b ́を、生成ノード6b ́から現在のノード6bへの遷移方向どおりにすべてε遷移で接続する。図21Fの2段目に示すように、NFA生成部152は、境界ノード組集合から未処理の1組の境界ノードの組を取り出す。ここでは、NFA生成部152は、境界ノード組集合から、ノード番号が2である現在のノード6cからノード番号が2 ́である生成ノード6c ́への遷移方向の境界ノードの組を取り出す。そして、NFA生成部152は、取り出した1組の現在のノードと生成ノードと遷移方向に従い、現在のノードに対応する複製したすべてのノードと生成ノードを遷移方向どおりにすべてε遷移で接続する。ここでは、NFA生成部152は、現在のノード6cに対応する、複製した3系列のノード6cと生成ノード6c ́を、現在のノード6cから生成ノード6c ́への遷移方向どおりにすべてε遷移で接続する。図21Gの1段目に示すように、NFA生成部152は、境界ノード組集合から未処理の1組の境界ノードの組を取り出す。ここでは、NFA生成部152は、境界ノード組集合から、ノード番号が5である現在のノード6fからノード番号が5 ́である生成ノード6f ́への遷移方向の境界ノードの組を取り出す。そして、NFA生成部152は、取り出した1組の現在のノードと生成ノードと遷移方向に従い、現在のノードに対応する複製したすべてのノードと生成ノードを遷移方向どおりにすべてε遷移で接続する。ここでは、NFA生成部152は、現在のノード6fに対応する、複製した3系列のノード6fと生成ノード6f ́を、現在のノード6fから生成ノード6f ́への遷移方向どおりにすべてε遷移で接続する。図21Gの2段目に示すように、NFA生成部152は、同系列ノード集合の組が空なので、系列の値の大小関係を保ち、境界ノード組集合の遷移元が小さいノード番号となるよう、ユニークなノード番号を振りなおす。[別のパターンにおけるNFAを生成する処理の一例]次に、別のパターンをイベントパターン141とした場合に、図11~図18に示したNFAの構築法を用いて、NFA生成部152が、イベントパターン141からNFA142を生成する処理の一例について説明する。図22A~図22Gは、仮NFAを生成する処理を説明する図である。図23A~図23Gは、同系列のNFAを探索する処理を説明する図である。図24A~図24Mは、同系列のNFAを変換する処理を説明する図である。[仮NFA生成処理の説明]図22Aに示すように、イベントパターン141のデータ構造を、符号202pに示すものとする。イベントパターン143は、任意の系列でイベントAが発生し、その後2以内にAと同じ系列でイベントBが発生するパターンを有する。そして、イベントパターン143は、任意の系列で発生したイベントAの発生後4以内に任意の系列でイベントCが発生するパターンを有する。そして、イベントパターン143は、イベントCの発生後3以内且つイベントDの発生後5以内且つイベントBの発生後4以内にイベントCと同じ系列でイベントEが発生するパターンを有する。図22Bの1段目に示すように、NFA生成部152は、ノード番号を0とする初期状態のノード7aを生成し、生成したノード7aに空のリストを登録する。そして、NFA生成部152は、現ノード番号iの値を0に設定し、現番号jの値を0に設定する。そして、NFA生成部152は、入力されたイベントパターン141に示されたイベント受理制約の内、前に間隔制約がないものを集め、仮イベント集合とする。ここでは、NFA生成部152は、イベントAのイベント受理制約およびイベントDのイベント受理制約を仮イベント集合とする。そして、NFA生成部152は、初期状態のノード7aを起点ノードとする。図22Bの2段目に示すように、NFA生成部152は、起点ノードが初期状態のノード7aであるので、仮イベント集合に集められた1つのイベント受理制約Aに対応するイベント入力ノード7bを生成する。そして、NFA生成部152は、生成したノード7bに現ノード番号iに1を加算した値1を割り当てる。そして、NFA生成部152は、起点ノード7aからイベント入力ノード7bへε遷移で接続する。また、NFA生成部152は、仮イベント集合に集められたもう1つのイベント受理制約Dに対応するイベント入力ノード7cを生成する。そして、NFA生成部152は、生成したノード7cに現ノード番号iに1を加算した値2を割り当てる。そして、NFA生成部152は、起点ノード7aからイベント入力ノード7cへε遷移で接続する。図22Bの3段目に示すように、NFA生成部152は、仮イベント集合に集められたイベント受理制約から未処理のイベント受理制約を1つ取り出す。ここでは、NFA生成部152はイベントAを取り出す。そして、NFA生成部152は、取り出したイベントAに付随する前方間隔制約がないので、イベント受理完了ノード7dを生成し、生成したノード7dに、現ノード番号iに1を加算した値3を割り当てる。そして、NFA生成部152は、イベントAの受理によりイベント入力ノード7bからイベント受理完了ノード7dに遷移するエッジで接続する。さらに、NFA生成部152は、イベント入力ノード7bのリストをイベント受理完了ノード7dのリストにコピーする。図22Bの4段目に示すように、NFA生成部152は、現在のイベント受理制約Aの後方間隔制約の中で同系列関係のものBがあるので、イベント受理完了ノード7dに同系列関係情報=を付加する。続いて、NFA生成部152は、現在のイベント受理制約Aの前方の間隔制約の数をFとする。ここでは、NFA生成部152は、イベントAの前方の間隔に制約がないので、Fを0に設定する。そして、NFA生成部152は、Fが2以上でないので、イベント受理完了ノード7dを完了ノードとする。さらに、NFA生成部152は、取り出したイベント受理制約Aの後方への間隔制約を持つイベント受理制約を前方間隔制約と前方間隔制約種別と共に集め、仮イベント集合とする。ここでは、NFA生成部152は、イベントAの後方イベントBまでの間隔制約が2であり、同系列の遷移関係であるので、イベント受理制約Bを前方間隔制約2と同系列の遷移関係の制約であることを示す種別と共に仮イベント集合に設定する。また、NFA生成部152は、イベントAの後方イベントCまでの間隔制約が4であり、任意系列の遷移関係であるので、イベント受理制約Cを前方間隔制約4と任意系列の遷移関係の制約であることを示す種別と共に仮イベント集合に設定する。そして、NFA生成部152は、完了ノード7dを起点ノードとする。図22Cの1段目に示すように、NFA生成部152は、起点ノード7dが初期状態のノードでなく、且つ仮イベント集合に集められたイベント受理制約B、Cが2つ以上であるので、起点ノード7dに現番号jの値0を割り当てる。すなわち、この起点ノード7dは、番号00を有する受理時刻保持ノードとなる。そして、NFA生成部152は、現番号jの値を、1加算した値1に設定する。図22Cの2段目に示すように、NFA生成部152は、起点ノード7dのリスト2mに、割り当てた番号0およびタイムアウト0を設定する。図22Cの3段目に示すように、NFA生成部152は、仮イベント集合に集められたイベント受理制約B、Cに対応するイベント入力ノード7e、7fを生成する。そして、NFA生成部152は、生成したノード7eに現ノード番号i3に1を加算した値4を割り当て、生成したノード7fにさらに現ノード番号i4に1を加算した値5を割り当てる。そして、NFA生成部152は、起点ノード7dからイベント入力ノード7eへε遷移で接続し、起点ノード7dからイベント入力ノード7fへε遷移で接続する。そして、NFA生成部152は、起点ノード7dのリストをイベント入力ノード7e、7fのそれぞれのリストにコピーする。図22Cの4段目に示すように、NFA生成部152は、仮イベント集合に集められたイベント受理制約B、Cから未処理のイベント受理制約を1つ取り出す。ここでは、NFA生成部152はイベントBを取り出す。そして、NFA生成部152は、イベント受理完了ノード7gを生成し、生成したノード7gに、現ノード番号iに1を加算した値6を割り当てる。そして、NFA生成部152は、前方間隔制約2を満たすイベントBの受理によりイベント入力ノード7eからイベント受理完了ノード7gに遷移するエッジで接続する。すなわち、イベント入力ノード7eからイベント受理完了ノード7gへの遷移が間隔条件付きの通常遷移となる。さらに、NFA生成部152は、イベント入力ノード7eのリストのタイムアウトに前方間隔制約2を加えてからイベント受理完了ノード7gのリストにコピーする。図22Cの5段目に示すように、NFA生成部152は、現在のイベント受理制約Bに付随する前方間隔制約種別が同系列関係であるので、イベント入力ノード7eに同系列関係情報=を付加する。続いて、NFA生成部152は、現在のイベント受理制約Bの前方の間隔制約の数をFとする。ここでは、イベントBの前方間隔制約は2のものだけであるので、NFA生成部152は、前方の間隔制約の数Fを1に設定する。そして、NFA生成部152は、Fが2以上でないので、イベント受理完了ノード7gを完了ノードとする。さらに、NFA生成部152は、取り出したイベント受理制約Bの後方への間隔制約を持つイベント受理制約を集め、仮イベント集合とする。ここでは、NFA生成部152は、イベントBの後方イベントEまでの間隔制約が4であり、任意系列の遷移関係であるので、イベント受理制約Eを前方間隔制約4と任意系列の遷移関係の制約であることを示す種別と共に仮イベント集合に設定する。そして、NFA生成部152は、完了ノード7gを起点ノードとする。図22Dの1段目に示すように、NFA生成部152は、仮イベント集合に集められたイベント受理制約Eに対応するイベント入力ノード7hを生成する。そして、NFA生成部152は、生成したノード7hに現ノード番号i6に1を加算した値7を割り当てる。そして、NFA生成部152は、起点ノード7gからイベント入力ノード7hへε遷移で接続する。そして、NFA生成部152は、起点ノード7gのリストをイベント入力ノード7hのリストにコピーする。図22Dの2段目に示すように、NFA生成部152は、仮イベント集合に集められたイベント受理制約から未処理のイベント受理制約を1つ取り出す。ここでは、NFA生成部152はイベントEを取り出す。そして、NFA生成部152は、イベント受理完了ノード7iを生成し、生成したノード7iに、現ノード番号iに1を加算した値8を割り当てる。そして、NFA生成部152は、前方間隔制約4を満たすイベントEの受理によりイベント入力ノード7hからイベント受理完了ノード7iに遷移するエッジで接続する。さらに、NFA生成部152は、イベント入力ノード7hのリストのタイムアウトに前方間隔制約4を加えてからイベント受理完了ノード7iのリストにコピーする。続いて、NFA生成部152は、現在のイベント受理制約Eに付随する前方間隔制約種別が同系列関係でないので、イベント入力ノード7hに同系列関係情報を付加しない。また、NFA生成部152は、現在のイベント受理制約Eの後方間隔制約がないので、イベント受理完了ノード7iに同系列関係情報を付加しない。続いて、NFA生成部152は、現在のイベント受理制約Eの前方の間隔制約の数の数をFとする。ここでは、イベントEの前方間隔制約はイベントBからの4の制約とイベントCからの3の制約とイベントDからの5の制約があるので、NFA生成部152は、前方の間隔制約の数Fを3に設定する。そして、NFA生成部152は、Fが2以上であり、現在のイベント受理制約Eに対応する生成済みのイベント受理完了ノードがノード7iの1個のみであるので、仮イベント集合に集められたイベント受理制約のうち未処理のものがあるか否かを判定する。ここでは、NFA生成部152は、仮イベント集合に集められたイベント受理制約Eの処理が終了したので、元の仮イベント集合および元の起点ノードに戻す。すなわち、起点ノードはノード番号が3であるノード7dとなり、仮イベント集合はイベント受理制約B、Cになる。図22Dの3段目に示すように、NFA生成部152は、仮イベント集合に集められたイベント受理制約B、Cから未処理のイベント受理制約を1つ取り出す。ここでは、NFA生成部152は、イベントBの処理が終了しているので、イベント受理制約Cを取り出す。そして、NFA生成部152は、イベント受理完了ノード7jを生成し、生成したノード7jに、現ノード番号iに1を加算した値9を割り当てる。そして、NFA生成部152は、イベントCの受理によりイベント入力ノード7fからイベント受理完了ノード7jに遷移するエッジで接続し、リストをコピーする。さらに、NFA生成部152は、現在のイベント受理制約Cの後方間隔制約に同系列関係のものがあるので、イベント受理完了ノード7jに同系列関係情報=を付加する。続いて、NFA生成部152は、現在のイベント受理制約Cの前方の間隔制約が1つなので、イベント受理完了ノード7jを完了ノードとする。さらに、NFA生成部152は、取り出したイベント受理制約Cの後方への間隔制約を持つイベント受理制約を前方間隔制約と前方間隔制約種別と共に集め、仮イベント集合とする。ここでは、NFA生成部152は、イベントCの後方イベントEまでの間隔制約が3であり、同系列の遷移関係であるので、イベント受理制約Eを前方間隔制約3と同系列の遷移関係の制約であることを示す種別と共に仮イベント集合に設定する。そして、NFA生成部152は、完了ノード7jを起点ノードとする。図22Dの4段目に示すように、NFA生成部152は、仮イベント集合に集められたイベント受理制約Eに対応するイベント入力ノード7kを生成する。そして、NFA生成部152は、生成したノード7kに現ノード番号i9に1を加算した値10を割り当てる。そして、NFA生成部152は、起点ノード7jからイベント入力ノード7kへε遷移で接続する。そして、NFA生成部152は、起点ノード7jのリストをイベント入力ノード7kのリストにコピーする。図22Dの5段目に示すように、NFA生成部152は、仮イベント集合に集められたイベント受理制約から未処理のイベント受理制約を1つ取り出す。ここでは、NFA生成部152はイベントEを取り出す。そして、NFA生成部152は、イベント受理完了ノード7lを生成し、生成したノード7lに、現ノード番号iに1を加算した値11を割り当てる。そして、NFA生成部152は、前方間隔制約3を満たすイベントEの受理によりイベント入力ノード7kからイベント受理完了ノード7lに遷移するエッジで接続する。さらに、NFA生成部152は、イベント入力ノード7kのリストのタイムアウトに前方間隔制約3を加えてからイベント受理完了ノード7lのリストにコピーする。続いて、NFA生成部152は、現在のイベント受理制約Eに付随する前方間隔制約種別が同系列関係でないので、イベント入力ノード7kに同系列関係情報を付加しない。また、NFA生成部152は、現在のイベント受理制約Eの後方間隔制約がないので、イベント受理完了ノード7lに同系列関係情報を付加しない。続いて、NFA生成部152は、現在のイベント受理制約Eの前方の間隔制約の数の数をFとする。ここでは、イベントEの前方間隔制約はイベントBからの4の制約とイベントCからの3の制約とイベントDからの5の制約があるので、NFA生成部152は、前方の間隔制約の数Fを3に設定する。そして、NFA生成部152は、Fが2以上であり、現在のイベント受理制約Eに対応する生成済みのイベント受理完了ノードがノード7iとノード7lの2個であるので、仮イベント集合に集められたイベント受理制約のうち未処理のものがあるか否かを判定する。ここでは、NFA生成部152は、仮イベント集合に集められたイベント受理制約Eの処理が終了したので、元の仮イベント集合および元の起点ノードに戻す。すなわち、起点ノードは初期状態のノード7aとなり、仮イベント集合はイベント受理制約A、Dになる。図22Eの1段目に示すように、NFA生成部152は、仮イベント集合に集められたイベント受理制約A、Dから未処理のイベント受理制約を1つ取り出す。ここでは、NFA生成部152は、イベントAの処理が終了しているので、イベントDを取り出す。そして、NFA生成部152は、イベント受理完了ノード7mを生成し、生成したノード7mに、現ノード番号iに1を加算した値12を割り当てる。そして、NFA生成部152は、イベントDの受理によりイベント入力ノード7cからイベント受理完了ノード7mに遷移するエッジで接続し、リストをコピーする。さらに、NFA生成部152は、現在のイベント受理制約Dの後方間隔制約に同系列関係のものがあるので、イベント受理完了ノード7mに同系列関係情報=を付加する。続いて、NFA生成部152は、現在のイベント受理制約Dの前方の間隔制約が1つなので、イベント受理完了ノード7mを完了ノードとする。さらに、NFA生成部152は、取り出したイベント受理制約Dの後方への間隔制約を持つイベント受理制約を前方間隔制約と前方間隔制約種別と共に集め、仮イベント集合とする。ここでは、NFA生成部152は、イベントDの後方イベントEまでの間隔制約が5であり、同系列の遷移関係であるので、イベント受理制約Eを前方間隔制約5と同系列の遷移関係の制約であることを示す種別と共に仮イベント集合に設定する。そして、NFA生成部152は、完了ノード7mを起点ノードとする。図22Eの2段目に示すように、NFA生成部152は、仮イベント集合に集められたイベント受理制約Eに対応するイベント入力ノード7nを生成する。そして、NFA生成部152は、生成したノード7nに現ノード番号i12に1を加算した値13を割り当てる。そして、NFA生成部152は、起点ノード7mからイベント入力ノード7nへε遷移で接続する。そして、NFA生成部152は、起点ノード7mのリストをイベント入力ノード7nのリストにコピーする。図22Eの3段目に示すように、NFA生成部152は、仮イベント集合に集められたイベント受理制約から未処理のイベント受理制約を1つ取り出す。ここでは、NFA生成部152はイベントEを取り出す。そして、NFA生成部152は、イベント受理完了ノード7oを生成し、生成したノード7oに、現ノード番号iに1を加算した値14を割り当てる。そして、NFA生成部152は、前方間隔制約5を満たすイベントEの受理によりイベント入力ノード7nからイベント受理完了ノード7oに遷移するエッジで接続する。さらに、NFA生成部152は、イベント入力ノード7nのリストのタイムアウトに前方間隔制約5を加えてからイベント受理完了ノード7oのリストにコピーする。続いて、NFA生成部152は、現在のイベント受理制約Eの前方の間隔制約の数の数をFとする。ここでは、イベントEの前方間隔制約はイベントBからの4の制約とイベントCからの3の制約とイベントDからの5の制約があるので、NFA生成部152は、前方の間隔制約の数Fを3に設定する。そして、NFA生成部152は、Fが2以上であり、現在のイベント受理制約Eに対応する生成済みのイベント受理完了ノードがノード7iとノード7lとノード7oの3個であるので、次の処理を行う。図22Fの1段目に示すように、NFA生成部152は、現在のイベント受理制約Eに対応する合流ノード7pを生成する。そして、NFA生成部152は、生成したノード7pに現ノード番号iに1を加算した値15を割り当てる。そして、NFA生成部152は、生成済みのイベント受理完了ノード7i、7l、7oから合流ノード7pへε=遷移で接続する。図22Fの2段目に示すように、NFA生成部152は、合流ノード7pに同系列関係情報=を付加する。図22Fの3段目に示すように、NFA生成部152は、現在の番号j1およびタイムアウト0を現在のイベント受理制約Eに対応する生成済みの全てのイベント受理完了ノード7i、7l、7oに割り当て、それぞれのリストに追加する。すなわち、このイベント受理完了ノード7i、7l、7oは、番号11を有する受理時刻保持ノードとなる。そして、NFA生成部152は、番号jに1を加算して2を設定する。図22Gの1段目に示すように、NFA生成部152は、現在のイベント受理制約Eに対応する生成済みのイベント受理完了ノード7i、7l、7oのリストにおいて、複数のノードで同一の番号を持っている番号を合流ノードの指定番号とする。そして、NFA生成部152は、番号毎にタイムアウトの中で一番大きい値をタイムアウト長として登録する。ここでは、ノード7iが持っている番号は0、1であり、ノード7lが持っている番号は0、1であり、ノード7oが持っている番号は1である。そこで、NFA生成部152は、0、1を合流ノード7pの指定番号とし、0のタイムアウト長を7、1のタイムアウト長を0として登録する。図22Gの2段目に示すように、NFA生成部152は、現在のイベント受理制約Eに対応する生成済みのイベント受理完了ノード7i、7l、7oの各リストに含まれる番号および各番号で最大のタイムアウト長を合流ノード7pのリストに設定する。ここでは、NFA生成部152は、番号0およびタイムアウト長7を対応付けて設定し、番号1およびタイムアウト長0を対応付けて設定する。そして、NFA生成部152は、合成ノード7pを完了ノードとする。さらに、NFA生成部152は、終端ノードリストに完了ノード7pを追加する。図22Gの3段目に示すように、NFA生成部152は、終端ノードリストにノードが2つ以上あるか否かを判定する。ここでは、NFA生成部152は、終端ノードリストにノード7pが1つあるのみであるので、終端ノードリストのノード7pを最終状態ノードとする。上述したように、NFA生成部152は、図22A~図22Gに示す処理を実行することで、図22Aに示すイベントパターン141から仮NFAを生成する。[別のパターンにおける同系列NFA探索処理の説明]次に、別のパターンにおける同系列NFA探索処理について説明する。まず、NFA生成部152は、生成した仮NFAの初期状態ノード7aを現在のノードとする。また、NFA生成部152は、未処理ノード集合および同系列ノード集合を空にする。そして、NFA生成部152は、現在のノード7aと接続する1つのε遷移について、現在のノード7aと遷移先のノード7bとがともに同系列関係でないので、遷移先のノード7bを未処理ノード集合に追加する。同様に、NFA生成部152は、現在のノード7aと接続するもう1つのε遷移について、現在のノード7aと遷移先のノード7cとがともに同系列関係でないので、遷移先のノード7cを未処理ノード集合に追加する。さらに、NFA生成部152は、現在のノード7aと接続する未処理の遷移がなく、同系列ノード集合に含まれるノードが空であるので、同系列ノード集合を出力しない。そして、NFA生成部152は、未処理ノード集合の中の最終状態ノードを除くノード番号の一番小さい未処理のノードを現在のノードとする。ここでは、NFA生成部152は、未処理ノード集合の中のノード番号1のノード7bを現在のノードとする。図23Aの1段目に示すように、NFA生成部152は、現在のノード7bと接続する未処理の遷移が間隔条件なしの通常遷移であるので、現在のノード7bあるいは遷移先のノード7dが同系列関係であるか否かを判定する。ここでは、NFA生成部152は、遷移先のノード7dが同系列関係情報=が付加されているので、同系列関係であると判定する。そして、NFA生成部152は、現在のノード7bと遷移先のノード7dを同系列ノード集合に追加する。図23Aの2段目に示すように、NFA生成部152は、現在のノード7bと接続する未処理の遷移がないので、同系列ノード集合に含まれるノードがすべて処理したか否かを判定する。そして、NFA生成部152は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号3のノード7dを現在のノードとする。そして、NFA生成部152は、現在のノード7dと接続する未処理の遷移がε遷移であるので、現在のノード7dと遷移先のノードとが同系列関係であるか否かを判定する。ここでは、NFA生成部152は、現在のノード7dと遷移先のノード7eとがともに同系列関係情報=が付加されているので、ともに同系列関係であると判定する。そして、NFA生成部152は、現在のノード7dと遷移先のノード7eを同系列ノード集合に追加する。また、NFA生成部152は、現在のノード7dと遷移先のノード7fとが双方ともに同系列関係情報=が付加されていないので、ともに同系列関係でないと判定する。そして、NFA生成部152は、遷移先のノード7fを未処理ノード集合に追加する。図23Aの3段目に示すように、NFA生成部152は、現在のノード7dと接続する未処理の遷移がないので、同系列ノード集合に含まれるノードがすべて処理したか否かを判定する。そして、NFA生成部152は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号4のノード7eを現在のノードとする。そして、NFA生成部152は、現在のノード7eと接続する未処理の遷移が間隔条件付きの通常遷移であるので、現在のノード7eあるいは遷移先のノード7gが同系列関係であるか否かを判定する。ここでは、NFA生成部152は、現在のノード7eが同系列関係情報=が付加されているので、同系列関係であると判定する。そして、NFA生成部152は、現在のノード7eと遷移先のノード7gを同系列ノード集合に追加する。図23Bの1段目に示すように、NFA生成部152は、現在のノード7eと接続する未処理の遷移がないので、同系列ノード集合に含まれるノードがすべて処理したか否かを判定する。そして、NFA生成部152は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号6のノード7gを現在のノードとする。そして、NFA生成部152は、現在のノード7eと接続する未処理の遷移がε遷移であるので、現在のノード7eと遷移先のノード7hがともに同系列関係であるか否かを判定する。ここでは、NFA生成部152は、現在のノード7eと遷移先のノード7hがともに同系列関係情報=が付加されていないので、同系列関係でないと判定する。そして、NFA生成部152は、遷移先のノード7hを未処理ノード集合に追加する。図23Bの2段目に示すように、NFA生成部152は、現在のノード7gと接続する未処理の遷移がなく、同系列ノード集合に含まれるノードはすべて処理したので、同系列ノード集合を出力する。ここでは、NFA生成部152は、ノード番号1、3、4、6のノードを同系列ノード集合として出力する。そして、NFA生成部152は、出力後、同系列ノード集合を空にする。図23Cの1段目に示すように、NFA生成部152は、未処理ノード集合の中の最終状態ノードを除くノード番号の一番小さい未処理のノードを現在のノードとする。ここでは、NFA生成部152は、未処理ノード集合の中のノード番号2のノード7cを現在のノードとする。図23Cの2段目に示すように、NFA生成部152は、現在のノード7cと接続する未処理の遷移が間隔条件なしの通常遷移であるので、現在のノード7cあるいは遷移先のノード7mが同系列関係であるか否かを判定する。ここでは、NFA生成部152は、遷移先のノード7mが同系列関係情報=が付加されているので、同系列関係であると判定する。そして、NFA生成部152は、現在のノード7cと遷移先のノード7mを同系列ノード集合に追加する。そして、NFA生成部152は、現在のノード7cと接続する未処理の遷移がないので、同系列ノード集合に含まれるノードがすべて処理したか否かを判定する。そして、NFA生成部152は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号12のノード7mを現在のノードとする。図23Cの3段目に示すように、NFA生成部152は、現在のノード7mと接続する未処理の遷移がε遷移であるので、現在のノード7mと遷移先のノードとが同系列関係であるか否かを判定する。ここでは、NFA生成部152は、現在のノード7mと遷移先のノード7nとがともに同系列関係情報=が付加されているので、ともに同系列関係であると判定する。そして、NFA生成部152は、現在のノード7mと遷移先のノード7nを同系列ノード集合に追加する。そして、NFA生成部152は、現在のノード7mと接続する未処理の遷移がないので、同系列ノード集合に含まれるノードがすべて処理したか否かを判定する。そして、NFA生成部152は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号13のノード7nを現在のノードとする。図23Dの1段目に示すように、NFA生成部152は、現在のノード7nと接続する未処理の遷移が間隔条件付きの通常遷移であるので、現在のノード7nあるいは遷移先のノード7oが同系列関係であるか否かを判定する。ここでは、NFA生成部152は、現在のノード7nに同系列関係情報=が付加されているので、同系列関係であると判定する。そして、NFA生成部152は、現在のノード7nと遷移先のノード7oを同系列ノード集合に追加する。そして、NFA生成部152は、現在のノード7nと接続する未処理の遷移がないので、同系列ノード集合に含まれるノードがすべて処理したか否かを判定する。そして、NFA生成部152は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号14のノード7oを現在のノードとする。図23Dの2段目に示すように、NFA生成部152は、現在のノード7oと接続する未処理の遷移がε遷移でないので、現在のノード7oあるいは遷移先元ノードが同系列関係であるか否かを判定する。ここでは、NFA生成部152は、同系列ノード集合に現在のノード7oが含まれ、遷移先ノード7pに同系列関係情報=が付加されているので、同系列関係であると判定する。そして、NFA生成部152は、現在のノード7oと遷移先元ノード7pノード番号15を同系列ノード集合に追加する。そして、NFA生成部152は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号15のノード7pを現在のノードとする。図23Dの3段目に示すように、NFA生成部152は、現在のノード7pと接続する未処理の遷移がε遷移でないので、現在のノード7pあるいは遷移先元ノードが同系列関係であるか否かを判定する。ここでは、NFA生成部152は、現在のノード7pが同系列関係なので、現在のノード7pと遷移先元ノード7iノード番号8を同系列ノード集合に追加する。また、NFA生成部152は、現在のノード7pが同系列関係なので、現在のノード7pと遷移先元ノード7lノード番号11を同系列ノード集合に追加する。図23Eの1段目に示すように、NFA生成部152は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号8のノード7iを現在のノードとする。図23Eの2段目に示すように、NFA生成部152は、現在のノード7iと接続する未処理の遷移がないので、同系列ノード集合に含まれるノードに未処理のノードがあるか否かを判定する。ここでは、NFA生成部152は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号11のノード7lを現在のノードとする。そして、NFA生成部152は、現在のノード7lと接続する未処理の遷移が間隔条件付きの通常遷移であるので、現在のノード7lあるいは遷移先元ノードが同系列関係であるか否かを判定する。ここでは、NFA生成部152は、遷移先元ノード7kが同系列関係であるので、現在のノード7lと遷移先元ノード7kを同系列ノード集合に追加する。図23Eの3段目に示すように、NFA生成部152は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号9のノード7jを現在のノードとする。図23Fの1段目に示すように、NFA生成部152は、現在のノード7jと接続する未処理の遷移が間隔条件付きの通常遷移であるので、現在のノード7jあるいは遷移先元ノードが同系列関係であるか否かを判定する。ここでは、NFA生成部152は、現在のノード7jが同系列関係であるので、現在のノード7jと遷移先元ノード7eを同系列ノード集合に追加する。図23Fの2段目に示すように、NFA生成部152は、同系列ノード集合に含まれるノードに未処理のノードがあるので、未処理のノードであるノード番号5のノード7eを現在のノードとする。そして、NFA生成部152は、現在のノード7eと接続する未処理の遷移がε遷移であるので、現在のノード7eと遷移先元ノードがともに同系列関係であるか否かを判定する。ここでは、NFA生成部152は、ともに同系列関係でないので、遷移先元ノード7cノード番号3を未処理ノード集合に追加する。図23Gの1段目に示すように、NFA生成部152は、現在のノード7fと接続する未処理の遷移がなく、同系列ノード集合に含まれるノードが空であるので、同系列ノード集合を出力する。ここでは、NFA生成部152は、ノード番号2、12、13、14、15、8、11、10、9、5のノードを同系列ノード集合として出力する。そして、NFA生成部152は、出力後、同系列ノード集合を空にする。さらに、NFA生成部152は、未処理ノード集合の中の最終状態ノードを除くノード番号の一番小さい未処理のノードを現在のノードとする。ここでは、NFA生成部152は、未処理ノード集合の中のノード番号5のノード7eを現在のノードとする。ところが、NFA生成部152は、現在のノード7eと接続する未処理の遷移がない。図23Gの2段目に示すように、NFA生成部152は、未処理ノード集合の中の最終状態ノードを除くノード番号の一番小さい未処理のノードを現在のノードとする。ここでは、NFA生成部152は、未処理ノード集合の中のノード番号7のノード7eを現在のノードとする。そして、NFA生成部152は、現在のノード7eと接続する遷移先元ノードが同系列関係でないので、遷移先元ノード7f、7hを未処理ノード集合に追加する。ところが、NFA生成部152は、ノード7fおよびノード7hと接続する未処理の遷移がないので、これらを現在のノードとする処理を終了する。図23Gの3段目に示すように、NFA生成部152は、未処理ノード集合に最終状態ノードを除く未処理のノードがないので、同系列NFA探索処理を終了する。上述したように、NFA生成部152は、図23A~図23Gに示す処理を実行することで、仮NFAから同系列ノード集合を出力する。すなわち、NFA生成部152は、ノード番号1、3、4、6のノードを1組とした同系列ノード集合と、ノード番号2、12、13、14、15、8、11、10、9、5のノードを1組とした同系列ノード集合とを出力する。[別のパターンにおける同系列NFA変換処理の説明]次に、別のパターンにおける同系列NFA変換処理について説明する。図24Aに示すように、NFA生成部152は、同系列ノード集合の組が空であるか否かを判定する。ここでは、NFA生成部152は、同系列ノード集合の組が存在するので空でないと判定する。図24Bに示すように、NFA生成部152は、同系列ノード集合の組から1組の同系列ノード集合を取り出す。すなわち、NFA生成部152は、ノード番号1、3、4、6のノードを1組とした同系列ノード集合を取り出す。図24Cの1段目に示すように、NFA生成部152は、取り出した同系列ノード集合の未処理の1ノードを現在のノードとする。ここでは、NFA生成部152は、同系列ノード集合の中から未処理のノードであるノード番号1のノード7bを現在のノードとする。そして、NFA生成部152は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがあるか否かを判定する。ここでは、NFA生成部152は、現在のノード7bと接続されているノード7aノード番号0が同系列ノード集合にない未処理のものであるので、未処理のものがあると判定する。そして、NFA生成部152は、新しいノード7b ́を生成し、現在のノード7bの代わりに生成したノード7b ́と先の同系列ノード集合にないノード7aとをそのままの遷移ε遷移で接続する。そして、NFA生成部152は、現在のノード7bと生成したノード7b ́とこれら2つのノードの遷移方向の組とを境界ノード組集合に加える。かかる場合は、生成したノード7b ́が現在のノード7bの前方にある場合であるので、NFA生成部152は、生成したノード7b ́から現在のノード7bへの遷移方向とする。図24Cの2段目に示すように、NFA生成部152は、同系列ノード集合の未処理の1ノードを現在のノードとする。ここでは、NFA生成部152は、同系列ノード集合の中から未処理のノードであるノード番号3のノード7dを現在のノードとする。そして、NFA生成部152は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがあるか否かを判定する。ここでは、NFA生成部152は、現在のノード7dと接続されているノード7e、7fの中にノード番号5のノード7fが同系列ノード集合にない未処理のものであるので、未処理のものがあると判定する。そして、NFA生成部152は、新しいノード7d ́を生成し、現在のノード7dの代わりに生成したノード7d ́と先の同系列ノード集合にないノード7dとをそのままの遷移ε遷移で接続する。そして、NFA生成部152は、現在のノード7dと生成したノード7d ́とこれら2つのノードの遷移方向の組とを境界ノード組集合に加える。かかる場合は、生成したノード7d ́が現在のノード7dの後方にある場合であるので、NFA生成部152は、現在のノード7dから、生成したノード7d ́への遷移方向とする。図24Dの1段目に示すように、NFA生成部152は、同系列ノード集合の未処理の1ノードを現在のノードとする。ここでは、NFA生成部152は、同系列ノード集合の中から未処理のノードであるノード番号4のノード7eを現在のノードとする。そして、NFA生成部152は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがあるか否かを判定する。ここでは、NFA生成部152は、現在のノード7eと接続されているノード7g、7dの中に同系列ノード集合にない未処理のものがないので、未処理のものがないと判定する。図24Dの2段目に示すように、NFA生成部152は、同系列ノード集合の未処理の1ノードを現在のノードとする。ここでは、NFA生成部152は、同系列ノード集合の中から未処理のノードであるノード番号6のノード7gを現在のノードとする。そして、NFA生成部152は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のものがあるか否かを判定する。ここでは、NFA生成部152は、現在のノード7gと接続されているノード7e、7hの中にノード番号7のノード7hが同系列ノード集合にない未処理のものであるので、未処理のものがあると判定する。そして、NFA生成部152は、新しいノード7g ́を生成し、現在のノード7gの代わりに生成したノード7g ́と先の同系列ノード集合にないノード7hとをそのままの遷移ε遷移で接続する。そして、NFA生成部152は、現在のノード7gと生成したノード7g ́とこれら2つのノードの遷移方向の組とを境界ノード組集合に加える。かかる場合は、生成したノード7g ́が現在のノード7gの後方にある場合であるので、NFA生成部152は、現在のノード7gから、生成したノード7g ́への遷移方向とする。図24Eの1段目に示すように、NFA生成部152は、同系列ノード集合に未処理のノードがないので、同系列ノード集合のノードおよびそのノード間の遷移エッジすべてを1セットとして、系列数分だけ複製する。ここでは、系列数を3とすると、NFA生成部152は、同系列ノード集合のノード7b、7d、7e、7gおよびそのノード間の遷移エッジすべてを3系列数分複製する。そして、NFA生成部152は、ノード間の遷移を各系列のイベントで受理する遷移に置き換える。すなわち、NFA生成部152は、複製元の一段目の遷移を0系列のイベントで受理する遷移に置き換え、複製した2段目の遷移を1系列のイベントで受理する遷移に置き換え、複製した3段目の遷移を2系列のイベントで受理する遷移に置き換える。図24Eの2段目に示すように、NFA生成部152は、境界ノード組集合から未処理の1組の境界ノードの組を取り出す。ここでは、NFA生成部152は、境界ノード組集合から、ノード番号が1 ́である生成ノード7b ́からノード番号が1である現在のノード7bへの遷移方向の境界ノードの組を取り出す。そして、NFA生成部152は、取り出した1組の現在のノードと生成ノードと遷移方向に従い、現在のノードに対応する複製したすべてのノードと生成ノードを遷移方向どおりにすべてε遷移で接続する。ここでは、NFA生成部152は、現在のノード7bに対応する、複製した3系列のノード7bと生成ノード7b ́を、生成ノード7b ́から現在のノード7bへの遷移方向どおりにすべてε遷移で接続する。図24Fの1段目に示すように、NFA生成部152は、境界ノード組集合から未処理の1組の境界ノードの組を取り出す。ここでは、NFA生成部152は、境界ノード組集合から、ノード番号が3である現在のノード7dからノード番号が3 ́である生成ノード7d ́への遷移方向の境界ノードの組を取り出す。そして、NFA生成部152は、取り出した1組の現在のノードと生成ノードと遷移方向に従い、現在のノードに対応する複製したすべてのノードと生成ノードを遷移方向どおりにすべてε遷移で接続する。ここでは、NFA生成部152は、現在のノード7dに対応する、複製した3系列のノード7dと生成ノード7d ́を、現在のノード7dから生成ノード7d ́への遷移方向どおりにすべてε遷移で接続する。図24Fの2段目に示すように、NFA生成部152は、境界ノード組集合から未処理の1組の境界ノードの組を取り出す。ここでは、NFA生成部152は、境界ノード組集合から、ノード番号が6である現在のノード7gからノード番号が6 ́である生成ノード7g ́への遷移方向の境界ノードの組を取り出す。そして、NFA生成部152は、取り出した1組の現在のノードと生成ノードと遷移方向に従い、現在のノードに対応する複製したすべてのノードと生成ノードを遷移方向どおりにすべてε遷移で接続する。ここでは、NFA生成部152は、現在のノード7gに対応する、複製した3系列のノード7gと生成ノード7g ́を、現在のノード7gから生成ノード7g ́への遷移方向どおりにすべてε遷移で接続する。図24Gの1段目に示すように、さらに、NFA生成部152は、同系列ノード集合の組が空であるか否かを判定する。ここでは、NFA生成部152は、同系列ノード集合の組が存在するので空でないと判定する。そこで、NFA生成部152は、同系列ノード集合の組から1組の同系列ノード集合を取り出す。すなわち、NFA生成部152は、ノード番号2、12、13、14、15、8、11、10、9、5のノードを1組とした同系列ノード集合を取り出す。図24Gの2段目に示すように、NFA生成部152は、取り出した同系列ノード集合の未処理の1ノードであるノード番号2のノード7cを現在のノードとする。そして、NFA生成部152は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のノード7aがあるので、新しいノード7c ́を生成する。そして、NFA生成部152は、現在のノード7cの代わりに生成したノード7c ́と先の同系列ノード集合にないノード7aとをそのままの遷移ε遷移で接続する。そして、NFA生成部152は、現在のノード7cと生成したノード7c ́とこれら2つのノードの遷移方向の組とを境界ノード組集合に加える。かかる場合は、生成したノード7c ́が現在のノード7cの前方にある場合であるので、NFA生成部152は、生成したノード7c ́から現在のノード7cへの遷移方向とする。図24Hの1段目に示すように、NFA生成部152は、取り出した同系列ノード集合の未処理の1ノードであるノード番号8のノード7iを現在のノードとする。そして、NFA生成部152は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のノード7hがあるので、新しいノード7i ́を生成する。そして、NFA生成部152は、現在のノード7iの代わりに生成したノード7i ́と先の同系列ノード集合にないノード7hとをそのままの遷移間隔条件付きの通常遷移で接続する。そして、NFA生成部152は、現在のノード7iと生成したノード7i ́とこれら2つのノードの遷移方向の組とを境界ノード組集合に加える。かかる場合は、生成したノード7i ́が現在のノード7iの前方にある場合であるので、NFA生成部152は、生成したノード7i ́から現在のノード7iへの遷移方向とする。図24Hの2段目に示すように、NFA生成部152は、取り出した同系列ノード集合の未処理の1ノードであるノード番号5のノード7fを現在のノードとする。そして、NFA生成部152は、現在のノードと接続されているノードの中に同系列ノード集合にない未処理のノード7d ́があるので、新しいノード7f ́を生成する。そして、NFA生成部152は、現在のノード7fの代わりに生成したノード7f ́と先の同系列ノード集合にないノード7d ́とをそのままの遷移ε遷移で接続する。そして、NFA生成部152は、現在のノード7fと生成したノード7f ́とこれら2つのノードの遷移方向の組とを境界ノード組集合に加える。かかる場合は、生成したノード7f ́が現在のノード7fの前方にある場合であるので、NFA生成部152は、生成したノード7f ́から現在のノード7fへの遷移方向とする。図24Iの1段目に示すように、NFA生成部152は、同系列ノード集合に未処理のノードがないので、同系列ノード集合のノードおよびそのノード間の遷移エッジすべてを1セットとして、系列数分だけ複製する。ここでは、系列数を3とすると、NFA生成部152は、同系列ノード集合のノード7c、7m、7n、7o、7p、7l、7k、7j、7f、7iおよびそのノード間の遷移エッジすべてを3系列数分複製する。そして、NFA生成部152は、ノード間の遷移を各系列のイベントで受理する遷移に置き換える。図24Jに示すように、NFA生成部152は、境界ノード組集合から未処理の1組である、ノード番号が2 ́である生成ノード7c ́からノード番号が2である現在のノード7cへの遷移方向の境界ノードの組を取り出す。そして、NFA生成部152は、取り出した1組の現在のノードと生成ノードと遷移方向に従い、現在のノードに対応する複製したすべてのノードと生成ノードを遷移方向どおりにすべてε遷移で接続する。図24Kに示すように、NFA生成部152は、境界ノード組集合から未処理の1組である、ノード番号が8 ́である生成ノード7i ́からノード番号が8である現在のノード7iへの遷移方向の境界ノードの組を取り出す。そして、NFA生成部152は、取り出した1組の現在のノードと生成ノードと遷移方向に従い、現在のノードに対応する複製したすべてのノードと生成ノードを遷移方向どおりにすべてε遷移で接続する。図24Lに示すように、NFA生成部152は、境界ノード組集合から未処理の1組である、ノード番号が5 ́である生成ノード7f ́からノード番号が5である現在のノード7fへの遷移方向の境界ノードの組を取り出す。そして、NFA生成部152は、取り出した1組の現在のノードと生成ノードと遷移方向に従い、現在のノードに対応する複製したすべてのノードと生成ノードを遷移方向どおりにすべてε遷移で接続する。図24Mに示すように、NFA生成部152は、同系列ノード集合の組が空なので、系列の値の大小関係を保ち、境界ノード組集合の遷移元が小さいノード番号となるよう、ユニークなノード番号を振りなおす。[実施例に係る照合部におけるパターン照合の処理手順]次に、実施例に係る照合部153におけるパターン照合の処理手順を、図25~図27を参照して説明する。図25は照合部におけるパターン照合の主処理の手順を示し、図26は通常遷移を発動する処理の手順を示し、図27は全てのε遷移とε=遷移を発動する処理の手順を示す。[パターン照合の主処理の手順]まず、パターン照合の主処理の手順について、図25を参照して説明する。図25は、実施例に係る照合部におけるパターン照合の主処理の手順を示すフローチャートである。例えば、図25に示す処理は、イベントパターン141とイベントストリーム143とを取得した後に、NFA142を生成したことを契機にして実行される。なお、イベントストリーム143における系列に対応する各IDの現在のイベントをS[i][ID]とする。ここで、iは現在のイベント位置の値、言い換えると時刻の値を示す。IDは系列の値を示す。まず、照合部153は、現在のイベント位置iの値を0に設定するステップS51。そして、照合部153は、いずれかのIDでイベントS[i][ID]が存在するか否かを判定するステップS52。いずれのIDでもイベントS[i][ID]が存在しない場合ステップS52;No、照合部153は、主処理を終了する。一方、いずれかのIDでイベントS[i][ID]が存在する場合ステップS52;Yes、照合部153は、イベントストリーム143からイベントS[i][ID]を読み込むステップS53。続いて、照合部153は、読み込んだイベントS[i][ID]に関するNFANPの全ての通常遷移を発動するステップS54。ここで、NFANPは、NFA142に対応する。さらに、照合部153は、NFANPの全てのε遷移とε=遷移を発動するステップS55。そして、照合部153は、現在のイベント位置iの値に1を加算しステップS56、ステップS52に移行する。[通常遷移を発動する処理の手順]次に、図25のステップS54に示した通常遷移を発動する処理について、図26を参照して説明する。図26は、通常遷移を発動する処理の手順を示すフローチャートである。図26に示すように、照合部153は、状態jの値を1に設定し、遷移先状態kの値を0に設定するステップS511。ここで、状態jはNFA142のノード番号、すなわち状態番号に対応するものである。また、遷移先状態kは遷移先のノード番号、すなわち遷移先の状態番号に対応するものである。そして、照合部153は、状態jが存在するか否かを判定しステップS512、状態jが存在しない場合にはステップS512;No、処理を終了する。一方、照合部153は、状態jが存在する場合にはステップS512;Yes、状態jからイベントS[i][ID]に関する通常遷移が出ているか否かを判定するステップS513。通常遷移が出ていない場合にはステップS513;No、状態jの値に1を加算しステップS514、ステップS512に移行する。一方、通常遷移が出ている場合にはステップS513;Yes、照合部153は、遷移種別判定テーブルを用いて、イベントS[i][ID]に対応する遷移種別を判定するステップS513A。具体的には、照合部153は、状態jから出ている通常遷移がID指定遷移であるか否かを判定する。そして、照合部153は、ID指定遷移であれば、イベントとIDとがそれぞれ一致するか否かによってイベントS[i][ID]に対応する遷移種別を判定する。すなわち、照合部153は、出ている通常遷移に係るイベントとイベントS[i][ID]が一致し、且つ出ている通常遷移に係るIDと現在のイベントS[i][ID]の発生したIDが一致する場合、出ている通常遷移をイベントに対応する遷移種別とする。かかる遷移種別は、間隔条件付き通常遷移または間隔条件なし通常遷移を示す。また、照合部153は、出ている通常遷移に係るイベントとイベントS[i][ID]が一致しないか、または出ている通常遷移に係るIDと現在のイベントS[i][ID]の発生したIDが一致しない場合、イベントに対応する遷移種別を遷移なしとする。また、照合部153は、状態jから出ている通常遷移がID指定遷移でなければ、出ている通常遷移をイベントに対応する遷移種別とする。そして、照合部153は、イベントに対応する遷移種別が遷移なしであるか否かを判定するステップS513B。イベントに対応する遷移種別が遷移なしであると判定した場合ステップS513B;Yes、照合部153は、ステップS514に移行する。一方、イベントに対応する遷移種別が遷移なしでないと判定した場合ステップS513B;No、照合部153は、イベントに対応する遷移種別が間隔条件付きの通常遷移であるか否かを判定するステップS513C。そして、照合部153は、間隔条件付きの通常遷移でない場合にはステップS513C;No、仮リストを空に設定するステップS515。ここで、仮リストはイベントリストを生成するための一時的に用いられる仮のリストであり、イベントリストと同じ構成を有する。また、イベントリストは、イベントを受理したノード毎に対応付けられ、イベントの受理状態が設定される。受理状態には、例えば番号位置と最終受理位置とが対応付けられる。番号位置には、番号が割り当てられた受理時刻保持ノードで受理したイベントのイベント位置を書き込む領域を指す。また、最終受理位置とは、現段階で最終的に受理したイベントのイベント位置を書き込む領域を指す。そして、照合部153は、状態jの通常遷移先の状態番号を状態kに設定するステップS516。そして、照合部153は、状態kが番号が割り当てられているか否かを判定するステップS517。すなわち、照合部153は、状態kのノード番号に対応するノードが受理時刻保持ノードであるか否かを判定する。状態kが番号が割り当てられている場合にはステップS517;Yes、照合部153は、仮リストの番号位置に現在のイベント位置iを書き込みステップS518、ステップS519に移行する。そして、照合部153は、仮リストの最終受理位置に現在のイベント位置iを書き込み、状態kのイベントリストとして追加するステップS519。そして、照合部153は、ステップS524に移行する。一方、照合部153は、間隔条件付きの通常遷移である場合にはステップS513C;Yes、状態jに未処理のイベントリストがあるか否かを判定するステップS520。状態jに未処理のイベントリストがある場合にはステップS520;Yes、照合部153は、未処理のイベントリストを選択し、選択したイベントリストの最終受理位置と現在のイベント位置iが間隔条件を満たすか否かを判定するステップS521。そして、間隔条件を満たさない場合にはステップS521;No、照合部153は、選択したイベントリストを削除しステップS522、状態jの処理を継続すべく、ステップS520に移行する。一方、間隔条件を満たす場合にはステップS521;Yes、照合部153は、選択したイベントリストを仮リストにコピーしステップS523、ステップS516に移行する。すなわち、照合部153は、状態jの通常遷移先の状態番号を状態kに設定する。そして、照合部153は、状態kが番号が割り当てられている場合には、仮リストの番号位置に現在のイベント位置iを上書きし、仮リストの最終受理位置に現在のイベント位置iを上書きし、状態kのイベントリストとして追加する。一方、照合部153は、状態kが番号が割り当てられていない場合には、仮リストの最終受理位置に現在のイベント位置iを上書きし、状態kのイベントリストとして追加する。続いて、照合部153は、状態kが最終状態であり、且つイベントリストがあるか否かを判定するステップS524。状態kが最終状態であり、且つイベントリストがある場合にはステップS524;Yes、照合部153は、現在のイベント位置iを通知し、状態kのイベントリストを削除するステップS525。すなわち、照合部153は、イベント位置iをイベントパターンの終了時刻として通知する。そして、照合部153は、状態jの処理を継続すべく、ステップS520に移行する。一方、状態kが最終状態でない場合、またはイベントリストがない場合にはステップS524;No、照合部153は、状態jの処理を継続すべく、ステップS520に移行する。[全てのε遷移とε=遷移を発動する処理の手順]次に、図25のステップS55に示した全てのε遷移とε=遷移を発動する処理について、図27を参照して説明する。図27は、全てのε遷移とε=遷移を発動する処理の手順を示すフローチャートである。図27に示すように、照合部153は、状態jの値に1を設定するステップS551。そして、照合部153は、状態jが存在するか否かを判定するステップS552。状態jが存在しない場合にはステップS552;No、照合部153は処理を終了する。一方、状態jが存在する場合にはステップS552;Yes、照合部153は状態jが合流ノードであるか否かを判定するステップS553。状態jが合流ノードでない場合にはステップS553;No、照合部153は状態jからε遷移が出ているか否かを判定するステップS554。状態jからε遷移が出ていない場合にはステップS554;No、照合部153は状態jの値に1を加算しステップS555、ステップS552に移行する。一方、状態jからε遷移が出ている場合にはステップS554;Yes、照合部153は状態jの全てのイベントリストを全ての遷移先の状態のイベントリストとして追加し、状態jのイベントリストを削除するステップS556。続いて、照合部153は、状態kが最終状態であり、且つイベントリストがあるか否かを判定するステップS557。状態kが最終状態であり、且つイベントリストがある場合にはステップS557;Yes、照合部153は、現在のイベント位置iを照合結果として通知し、状態kのイベントリストを削除するステップS558。すなわち、照合部153は、照合が完了した結果として、イベントパターンの終了時刻を通知する。そして、照合部153は、状態jの処理を継続すべく、ステップS555に移行する。一方、状態kが最終状態でない場合、またはイベントリストがない場合にはステップS557;No、照合部153は、状態jの処理を継続すべく、ステップS555に移行する。一方、状態jが合流ノードである場合にはステップS553;Yes、照合部153は、状態jのε=遷移元のイベントリストの、状態jで指定された指定番号の番号位置のイベント位置が一致しているイベントリストを探索する。そして、照合部153は、探索の結果、番号位置のイベント位置が一致しているイベントリストの全ての組み合わせに対して、イベントリストを結合し、結合したイベントリストを状態jに追加するステップS559。そして、照合部153は、状態jの各ε=遷移元のイベントリストの、状態jで指定された指定番号の番号位置のイベント位置を取り出す。そして、照合部153は、取り出したイベント位置が{現在のイベント位置-状態jの各番号に対応するタイムアウト長}以下の場合、タイムアウトであると判断し、そのイベントリストを削除するステップS560。続いて、照合部153は、状態jが最終状態であり、且つイベントリストがあるか否かを判定するステップS561。状態jが最終状態であり、且つイベントリストがある場合にはステップS561;Yes、照合部153は、現在のイベント位置iを照合結果として通知し、状態jのイベントリストを削除するステップS562。すなわち、照合部153は、照合が完了した結果として、イベントパターンの終了時刻を通知する。そして、照合部153は、状態jの処理を継続すべく、ステップS554に移行する。一方、状態jが最終状態でない場合、またはイベントリストがない場合にはステップS561;No、照合部153は、状態jの処理を継続すべく、ステップS554に移行する。[パターン照合処理の一例]次に、図を用いて照合部153の処理を説明する。図28A~図28Nは、照合部の処理を説明するための図である。なお、図28A~図28Nの説明では、状態番号によって、各ノードを区別して説明する。以下では、状態番号1~49のノードを、状態1~49として説明する。また、NFA142と比較するイベントストリーム143を、図3に示すものとし、系列に対応する各IDの各イベントをS[i][ID]i=0~10ID=0~2に保持するものとする。図28Aに示すように、イベントパターン143のデータ構造を、符号204pに示すものとする。イベントパターン143は、任意の系列でイベントAが発生し、その後2以内にAと同じ系列でイベントBが発生するパターンを有する。そして、イベントパターン143は、任意の系列で発生したイベントAの発生後4以内に任意の系列でイベントCが発生するパターンを有する。そして、イベントパターン143は、イベントCの発生後3以内且つイベントDの発生後5以内且つイベントBの発生後4以内にイベントCと同じ系列でイベントEが発生するパターンを有する。このイベントパターン143を入力としてNFA生成部152によって生成されたNFAは、符号204nに示すものとなる。図28Aの1段目に示すように、照合部153は、現在のイベント位置iの値を0に設定し、イベントストリーム143からイベント位置0および系列0のイベントS[0][0]、すなわちイベントAを読み込む。言い換えれば、照合部153は、時刻0のときの系列0のイベントAを読み込む。図28Aの2段目に示すように、照合部153は、状態jの値と遷移先状態kの値を初期化し、状態jの値を1に設定し、遷移先状態kの値を0に設定する。照合部153は、状態jの値を1ずつ加算し、状態jからイベントAに関する通常遷移が出ているか否かを判定する。ここでは、状態2からイベントAに関する間隔条件なしの通常遷移が出ている。そこで、照合部153は、遷移種別判定テーブルを用いてイベントAに対応する遷移種別を判定する。ここでは、照合部153は、状態2から出ている通常遷移がID指定遷移であるので、読み込んだイベントと状態から出ている通常遷移に関して、イベントとIDとがそれぞれ一致するか否かを判定する。照合部153は、イベントについてともにAであり、IDについてともに0であるので、イベントとIDとがそれぞれ一致すると判定する。そこで、照合部153は、出ている間隔条件なしの通常遷移をイベントに対応する遷移種別とする。したがって、照合部153は、イベントに対応する遷移種別が間隔条件なしの通常遷移であるので、照合部153は、イベントの受理状態を設定する仮リストを空に設定し、状態kに状態3の通常遷移先である状態9を設定する。そして、照合部153は、状態9に番号0が割り当てられているので、仮リストの番号位置に現在のイベント位置0を書き込む。照合部153は、仮リストの最終受理位置に現在のイベント位置0を設定する。そして、照合部153は、仮リストを状態9のイベントリストr1として追加する。なお、照合部153は、状態3、状態4からイベントAに関する通常遷移が出ているが、出ている通常遷移がID指定遷移であり、出ている通常遷移のIDと読み込んだイベントのIDとが一致していないので、遷移なしとする。その後、照合部153は、状態3から状態49まで各状態からイベントAに関する通常遷移が出ていないので、照合部152は、系列0の現在のイベント位置0時刻0のイベントAに関する全ての通常遷移の発動を終了する。図28Bの3段目に示すように、照合部153は、状態jの値を1ずつ増やしながら、状態jから出ている全てのε遷移とε=遷移の発動を実行する。照合部153は、状態9からε遷移が出ているので、状態9のイベントリストr1を遷移先の状態13、17、18、19のイベントリストr1 ́として追加し、状態9のイベントリストr1を削除する。そして、照合部153は、状態49まで処理を完了すると、全てのε遷移とε=遷移の発動を終了する。その後、照合部152は、現在のイベント位置0時刻0に他の系列のイベントがないので、現在のイベント位置0時刻0の照合を終了する。図28Cの1段目に示すように、照合部153は、現在のイベント位置iの値を1に設定し、イベントストリーム143からイベント位置1および系列1のイベントS[1][1]、すなわちイベントAを読み込む。言い換えれば、照合部153は、時刻1のときの系列1のイベントAを読み込む。図28Cの2段目に示すように、照合部153は、状態3からイベントAに関する間隔条件なしの通常遷移が出ているので、遷移種別判定テーブルを用いてイベントAに対応する遷移種別を判定する。ここでは、照合部153は、状態3から出ている通常遷移がID指定遷移であるので、読み込んだイベントと状態から出ている通常遷移に関して、イベントとIDとがそれぞれ一致するか否かを判定する。照合部153は、イベントについてともにAであり、IDについてともに1であるので、イベントとIDとがそれぞれ一致すると判定する。そこで、照合部153は、出ている間隔条件なしの通常遷移をイベントに対応する遷移種別とする。したがって、照合部153は、イベントに対応する遷移種別が間隔条件なしの通常遷移であるので、照合部153は、イベントの受理状態を設定する仮リストを空に設定する。そして、照合部153は、状態3の通常遷移先である状態10に番号0が割り当てられているので、仮リストの番号位置に現在のイベント位置1を書き込む。照合部153は、仮リストの最終受理位置に現在のイベント位置1を設定する。そして、照合部153は、仮リストを状態10のイベントリストr2として追加する。その後、照合部152は、状態4から状態49まで各状態からイベントAに関する通常遷移が出ていないので、照合部152は、系列1の現在のイベント位置1時刻1のイベントAに関する全ての通常遷移の発動を終了する。図28Cの3段目に示すように、照合部153は、状態jの値を1ずつ増やしながら、状態jから出ている全てのε遷移とε=遷移の発動を実行する。照合部153は、状態10からε遷移が出ているので、状態10のイベントリストr2を遷移先の状態14、17、18、19のイベントリストr2 ́として追加し、状態10のイベントリストr2を削除する。そして、照合部153は、状態49まで処理を完了すると、全てのε遷移とε=遷移の発動を終了する。その後、照合部152は、現在のイベント位置1時刻1に他の系列のイベントがないので、現在のイベント位置1時刻1の照合を終了する。図28Dの1段目に示すように、照合部153は、現在のイベント位置iの値を2に設定し、イベントストリーム143からイベント位置2および系列0のイベントS[2][0]、すなわちイベントBを読み込む。言い換えれば、照合部153は、時刻2のときの系列0のイベントBを読み込む。図28Dの2段目に示すように、照合部153は、状態13からイベントBに関する間隔条件付き通常遷移が出ているので、遷移種別判定テーブルを用いてイベントBに対応する遷移種別を判定する。ここでは、照合部153は、状態13から出ている通常遷移がID指定遷移であるので、読み込んだイベントと状態から出ている通常遷移に関して、イベントとIDとがそれぞれ一致するか否かを判定する。照合部153は、イベントについてともにBであり、IDについてともに0であるので、イベントとIDとがそれぞれ一致すると判定する。そこで、照合部153は、出ている間隔条件付き通常遷移をイベントに対応する遷移種別とする。したがって、照合部153は、イベントに対応する遷移種別が間隔条件付き通常遷移であり、状態13に未処理のイベントリストがあるので、イベントリストの最終受理位置と現在のイベント位置が間隔条件を満たすか否かを判定する。ここでは、照合部153は、イベントリストの最終受理位置が0であり、現在のイベント位置が2であるので、間隔条件付き通常遷移の間隔条件2を満たすと判定する。そして、照合部153は、イベントリストの最終受理位置に現在のイベント位置2を設定し、状態10のイベントリストr3として追加する。その後、照合部152は、状態14から状態49まで各状態からイベントBに関する通常遷移が出ていないので、照合部152は、系列0の現在のイベント位置2時刻2のイベントBに関する全ての通常遷移の発動を終了する。図28Dの3段目に示すように、照合部153は、状態jの値を1ずつ増やしながら、状態jから出ている全てのε遷移とε=遷移の発動を実行する。照合部153は、状態20からε遷移が出ているので、状態20のイベントリストr3を遷移先の状態24のイベントリストr3 ́として追加し、状態20のイベントリストr3を削除する。そして、照合部153は、状態49まで処理を完了すると、全てのε遷移とε=遷移の発動を終了する。その後、照合部152は、現在のイベント位置2時刻2に他の系列のイベントがないので、現在のイベント位置2時刻2の照合を終了する。図28Eの1段目に示すように、照合部153は、現在のイベント位置iの値を3に設定し、イベントストリーム143からイベント位置3および系列0のイベントS[3][0]、すなわちイベントCを読み込む。また、照合部153は、イベントストリーム143から現在のイベント位置3および系列1のイベントS[3][1]、すなわちイベントBを読み込む。そして、照合部153は、系列0のイベントC、系列1のイベントBの順に以下の照合処理を行う。図28Eの2段目に示すように、系列0のイベントCについて、照合部153は、状態17からイベントCに関する間隔条件付き通常遷移が出ているので、遷移種別判定テーブルを用いてイベントCに対応する遷移種別を判定する。ここでは、照合部153は、状態17から出ている通常遷移がID指定遷移であり、読み込んだイベントと状態から出ている通常遷移に関して、イベントとIDとがそれぞれ一致しているので、出ている間隔条件付き通常遷移をイベントに対応する遷移種別とする。したがって、照合部153は、イベントに対応する遷移種別が間隔条件付き通常遷移であり、状態17に未処理のイベントリストがあるので、イベントリストの最終受理位置と現在のイベント位置が間隔条件を満たすか否かを判定する。ここでは、照合部153は、1つのイベントリストの最終受理位置が0であり、現在のイベント位置が3であるので、間隔条件付き通常遷移の間隔条件4を満たすと判定する。また、照合部153は、もう1つのイベントリストの最終受理位置が1であり、現在のイベント位置が3であるので、間隔条件付き通常遷移の間隔条件4を満たすと判定する。そして、照合部153は、それぞれのイベントリストの最終受理位置に現在のイベント位置3を設定し、それぞれのイベントリストを通常遷移先の状態29のイベントリストr4として追加する。系列1のイベントBについても、照合部153は、系列0のイベントCの場合と同様に処理し、状態14のイベントリストの最終受理位置に現在のイベント位置3を設定し、イベントリストを通常遷移先の状態21のイベントリストr5として追加する。図28Eの3段目に示すように、系列0のイベントCについて、照合部153は、状態jの値を1ずつ増やしながら、状態jから出ている全てのε遷移とε=遷移の発動を実行する。照合部153は、状態29からε遷移が出ているので、状態29のイベントリストr4を遷移先の状態32のイベントリストr4 ́として追加し、状態29のイベントリストr4を削除する。系列1のイベントBについても、照合部153は、系列1のイベントCの場合と同様に処理し、状態21のイベントリストr5を遷移先の状態24のイベントリストr5 ́として追加し、状態21のイベントリストr5を削除する。そして、照合部153は、状態49まで処理を完了すると、全てのε遷移とε=遷移の発動を終了する。その後、照合部152は、現在のイベント位置3時刻3に他の系列のイベントがないので、現在のイベント位置3時刻3の照合を終了する。図28Fの1段目に示すように、照合部153は、現在のイベント位置iの値を4に設定し、イベントストリーム143からイベント位置4および系列0のイベントS[4][0]、すなわちイベントAを読み込む。また、照合部153は、イベントストリーム143から現在のイベント位置4および系列2のイベントS[4][2]、すなわちイベントDを読み込む。そして、照合部153は、系列0のイベントA、系列2のイベントDの順に以下の照合処理を行う。図28Fの2段目に示すように、系列0のイベントAについて、照合部153は、状態2からイベントAに関する間隔条件なしの通常遷移が出ているので、遷移種別判定テーブルを用いてイベントCに対応する遷移種別を判定する。ここでは、照合部153は、状態2から出ている通常遷移がID指定遷移であり、読み込んだイベントと状態から出ている通常遷移に関して、イベントとIDとがそれぞれ一致しているので、出ている間隔条件なし通常遷移をイベントに対応する遷移種別とする。したがって、照合部153は、イベントに対応する遷移種別が間隔条件なしの通常遷移であり、通常遷移先の状態9に番号0が割り当てられているので、イベントリストの番号位置に現在のイベント位置4を書き込み、最終受理位置に現在のイベント位置4を設定する。そして、照合部153は、状態9のイベントリストr6として追加する。系列2のイベントDについては、照合部153は、系列0のイベントAの場合と同様に処理し、状態8から出ているイベントDに関する間隔条件なしの通常遷移が出ているので、遷移種別判定テーブルを用いてイベントDに対応する遷移種別を判定する。ここでは、照合部153は、状態8から出ている間隔条件なし通常遷移をイベントに対応する遷移種別とする。そして、照合部153は、イベントに対応する遷移種別が間隔条件なしの通常遷移であり、通常遷移先の状態40に番号が割り当てられていないので、イベントリストの最終受理位置に現在のイベント位置4を設定する。そして、照合部153は、状態40のイベントリストr7として追加する。図28Fの3段目に示すように、系列0のイベントAについて、照合部153は、状態jの値を1ずつ増やしながら、状態jから出ている全てのε遷移とε=遷移の発動を実行する。照合部153は、状態9からε遷移が出ているので、状態9のイベントリストr6を遷移先の状態13、18、17、19のイベントリストr6 ́として追加し、状態9のイベントリストr6を削除する。系列2のイベントDについても、照合部153は、系列0のイベントAの場合と同様に処理し、状態40のイベントリストr7を遷移先の状態43のイベントリストr7 ́として追加し、状態40のイベントリストr7を削除する。そして、照合部153は、状態49まで処理を完了すると、全てのε遷移とε=遷移の発動を終了する。その後、照合部152は、現在のイベント位置4時刻4に他の系列のイベントがないので、現在のイベント位置4時刻4の照合を終了する。図28Gの1段目に示すように、照合部153は、現在のイベント位置iの値を5に設定し、イベントストリーム143からイベント位置5および系列0のイベントS[5][0]、すなわちイベントEを読み込む。また、照合部153は、イベントストリーム143から現在のイベント位置5および系列2のイベントS[5][2]、すなわちイベントCを読み込む。そして、照合部153は、系列0のイベントE、系列2のイベントCの順に以下の照合処理を行う。図28Gの2段目に示すように、系列0のイベントEについて、照合部153は、状態24からイベントEに関する間隔条件なしの通常遷移が出ているので、遷移種別判定テーブルを用いてイベントEに対応する遷移種別を判定する。ここでは、照合部153は、状態24から出ている通常遷移がID指定なし遷移であるので、出ている間隔条件なし通常遷移をイベントに対応する遷移種別とする。したがって、照合部153は、イベントに対応する遷移種別が間隔条件なしの通常遷移であり、通常遷移先の状態25に番号1が割り当てられているので、イベントリストの番号位置に現在のイベント位置5を書き込み、最終受理位置に現在のイベント位置5を設定する。そして、照合部153は、状態25のイベントリストr8として追加する。続いて、照合部153は、状態32からイベントEに関する間隔条件付き通常遷移が出ているので、イベントEに対応する遷移種別を判定する。ここでは、照合部153は、状態32から出ている通常遷移がID指定遷移であり、読み込んだイベントと状態から出ている通常遷移に関して、イベントとIDとがそれぞれ一致しているので、出ている間隔条件付き通常遷移をイベントに対応する遷移種別とする。したがって、照合部153は、イベントに対応する遷移種別が間隔条件付き通常遷移であり、状態32に未処理のイベントリストがあるので、イベントリストの最終受理位置と現在のイベント位置が間隔条件を満たすか否かを判定する。ここでは、照合部153は、2つのイベントリストとも間隔条件3を満たすと判定する。そして、照合部153は、通常遷移先の状態35に番号1が割り当てられているので、イベントリストの番号位置に現在のイベント位置5を書き込み、最終受理位置に現在のイベント位置5を設定する。そして、照合部153は、状態35のイベントリストr9として追加する。系列2のイベントCについては、照合部153は、系列0のイベントEの場合と同様に処理し、状態19から出ているイベントCに関する間隔条件付き通常遷移が出ているので、イベントCに対応する遷移種別を判定する。ここでは、照合部153は、状態19から出ている間隔条件付き通常遷移をイベントに対応する遷移種別とする。そして、照合部153は、状態19の未処理のイベントリストr1 ́を選択し、選択したイベントリストr1 ́の最終受理位置と現在のイベント位置5が間隔条件を満たすか否かを判定する。選択したイベントリストr1 ́の最終受理位置が0であり、現在のイベント位置5との間隔が5であり、間隔条件4を超えているので、照合部153は、間隔条件4を満たさないと判定する。そして、照合部152は、そのイベントリストr1 ́を削除する。続いて、照合部153は、状態19の未処理のイベントリストr2 ́を選択し、選択したイベントリストr2 ́の最終受理位置と現在のイベント位置5が間隔条件を満たすか否かを判定する。選択したイベントリストr2 ́の最終受理位置が1であり、現在のイベント位置5との間隔が4であり、間隔条件4を超えていないので、照合部153は、間隔条件4を満たすと判定する。そして、照合部153は、イベントリストの最終受理位置に現在のイベント位置5を設定する。そして、照合部153は、通常遷移先の状態31のイベントリストr10として追加する。図28Gの3段目に示すように、系列0のイベントEについて、照合部153は、状態jの値を1ずつ増やしながら、状態jから出ている全てのε遷移とε=遷移の発動を実行する。照合部153は、状態25からε遷移が出ているので、状態25のイベントリストr8を遷移先の状態26、27、28のイベントリストr8 ́として追加し、状態25のイベントリストr8を削除する。系列2のイベントCについても、照合部153は、系列0のイベントEの場合と同様に処理し、状態31のイベントリストr10を遷移先の状態34のイベントリストr10 ́として追加し、状態10のイベントリストr10を削除する。図28Hに示すように、照合部153は、状態47のε=遷移元26、35のイベントリストr8 ́、r9の、状態47で指定された指定番号0、1に対応するイベント位置を取り出す。ここでは、指定番号0の場合、照合部153は、イベントリストr8 ́から0、1、イベントリストr9から0、1を取り出す。この場合、照合部153は、取り出したイベント位置が{現在のイベント位置-状態47の番号0に対応するタイムアウト長}以下であるか否かを判定する。ここでは、取り出したイベント位置が0または1、現在のイベント位置は5、状態47の番号0に対応するタイムアウト長が7であり、0または1>5-7となるので、照合部150cは、これらのイベントリストを削除しないこととなる。一方、指定番号1の場合、照合部153は、イベントリストr8 ́から5、イベントリストr9から5を取り出す。この場合、照合部153は、取り出したイベント位置が{現在のイベント位置-状態47の番号1に対応するタイムアウト長}以下であるか否かを判定する。ここでは、取り出したイベント位置が5、現在のイベント位置は5、状態47の番号1に対応するタイムアウト長が0であり、5=5-0となるので、照合部152は、タイムアウトであると判断し、イベントリストr8 ́、r9を削除することとなる。続いて、照合部153は、状態48のε=遷移元27、状態49のε=遷移元28の各イベントリストr8 ́についても、状態47の場合と同様に、番号1に対応するタイムアウトとなるので、各イベントリストr8 ́を削除することとなる。図28Iの1段目に示すように、照合部153は、現在のイベント位置iの値を6に設定し、イベントストリーム143からイベント位置6および系列0のイベントS[6][0]、すなわちイベントBを読み込む。また、照合部153は、イベントストリーム143から現在のイベント位置6および系列1のイベントS[6][1]、すなわちイベントCを読み込む。そして、照合部153は、系列0のイベントB、系列1のイベントCの順に以下の照合処理を行う。図28Iの2段目に示すように、系列0のイベントBについて、照合部153は、状態13から出ているイベントBに関する間隔条件付き通常遷移が出ているので、イベントBに対応する遷移種別を判定する。ここでは、照合部153は、状態13から出ている間隔条件付き通常遷移をイベントに対応する遷移種別とする。そして、照合部153は、状態13の未処理のイベントリストr1 ́を選択し、選択したイベントリストr1 ́の最終受理位置と現在のイベント位置6が間隔条件を満たすか否かを判定する。選択したイベントリストr1 ́の最終受理位置が0であり、現在のイベント位置6との間隔が6であり、間隔条件2を超えているので、照合部153は、間隔条件2を満たさないと判定する。そして、照合部152は、そのイベントリストr1 ́を削除する。続いて、照合部153は、状態13の未処理のイベントリストr6 ́を選択し、選択したイベントリストr6 ́の最終受理位置と現在のイベント位置6が間隔条件を満たすか否かを判定する。選択したイベントリストr6 ́の最終受理位置が4であり、現在のイベント位置6との間隔が2であり、間隔条件2を超えていないので、照合部153は、間隔条件2を満たすと判定する。そして、照合部153は、イベントリストの最終受理位置に現在のイベント位置6を設定する。そして、照合部153は、通常遷移先の状態20のイベントリストr11として追加する。系列1のイベントCについて、照合部153は、状態18から出ているイベントCに関する間隔条件付き通常遷移が出ているので、イベントCに対応する遷移種別を判定する。ここでは、照合部153は、状態18から出ている間隔条件付き通常遷移をイベントに対応する遷移種別とする。そして、照合部153は、状態18の未処理のイベントリストr1 ́、r2 ́の各最終受理位置と現在のイベント位置6が間隔条件を満たすか否かを判定する。選択したイベントリストr1 ́、r2 ́の最終受理位置がそれぞれ0、1であり、現在のイベント位置6との間隔がそれぞれ6、5であり、間隔条件4を超えているので、照合部153は、間隔条件4を満たさないと判定する。そして、照合部153は、そのイベントリストr1 ́、r2 ́を削除する。続いて、照合部153は、状態18の未処理のイベントリストr6 ́を選択し、選択したイベントリストr6 ́の最終受理位置と現在のイベント位置6が間隔条件を満たすか否かを判定する。選択したイベントリストr6 ́の最終受理位置が4であり、現在のイベント位置6との間隔が2であり、間隔条件4を超えていないので、照合部153は、間隔条件4を満たすと判定する。そして、照合部153は、イベントリストの最終受理位置に現在のイベント位置6を設定する。そして、照合部153は、通常遷移先の状態30のイベントリストr12として追加する。図28Iの3段目に示すように、照合部153は、状態jの値を1ずつ増やしながら、状態jから出ている全てのε遷移とε=遷移の発動を実行する。照合部153は、状態20からε遷移が出ているので、状態20のイベントリストr11を遷移先の状態24のイベントリストr11 ́として追加し、状態20のイベントリストr11を削除する。続いて、照合部153は、状態30からε遷移が出ているので、状態30のイベントリストr12を遷移先の状態33のイベントリストr12 ́として追加し、状態30のイベントリストr12を削除する。図28Jの1段目に示すように、照合部153は、現在のイベント位置iの値を7に設定し、イベントストリーム143からイベント位置7および系列2のイベントS[7][2]、すなわちイベントEを読み込む。図28Jの2段目に示すように、照合部153は、状態24から出ているイベントEに関する間隔条件付き通常遷移が出ているので、イベントEに対応する遷移種別を判定する。ここでは、照合部153は、状態24から出ている間隔条件付き通常遷移をイベントに対応する遷移種別とする。そして、照合部153は、状態24の未処理のイベントリストr3 ́の最終受理位置と現在のイベント位置7が間隔条件を満たすか否かを判定する。選択したイベントリストr3 ́の最終受理位置が2であり、現在のイベント位置7との間隔が5であり、間隔条件4を超えているので、照合部153は、間隔条件4を満たさないと判定する。そして、照合部153は、そのイベントリストr3 ́を削除する。続いて、照合部153は、状態24の未処理のイベントリストr5 ́、r11 ́の各最終受理位置と現在のイベント位置7が間隔条件を満たすか否かを判定する。選択したイベントリストr5 ́、r11 ́の最終受理位置がそれぞれ3、6であり、現在のイベント位置7との間隔がそれぞれ4、1であり、間隔条件4を超えていないので、照合部153は、間隔条件4を満たすと判定する。そして、照合部153は、通常遷移先の状態25に番号1が割り当てられているので、イベントリストの番号位置に現在のイベント位置7を書き込み、最終受理位置に現在のイベント位置7を設定する。そして、照合部153は、状態25のイベントリストr13、r14として追加する。続いて、照合部153は、状態34から出ているイベントEに関する間隔条件付き通常遷移が出ているので、イベントEに対応する遷移種別を判定する。ここでは、照合部153は、状態34から出ている間隔条件付き通常遷移をイベントに対応する遷移種別とする。そして、照合部153は、状態34の未処理のイベントリストr10 ́の最終受理位置と現在のイベント位置7が間隔条件を満たすか否かを判定する。選択したイベントリストr10 ́の最終受理位置が5であり、現在のイベント位置7との間隔が2であり、間隔条件3を超えていないので、照合部153は、間隔条件3を満たすと判定する。そして、照合部153は、通常遷移先の状態37に番号1が割り当てられているので、イベントリストの番号位置に現在のイベント位置7を書き込み、最終受理位置に現在のイベント位置7を設定する。そして、照合部153は、状態37のイベントリストr15として追加する。続いて、照合部153は、状態43から出ているイベントEに関する間隔条件付き通常遷移が出ているので、イベントEに対応する遷移種別を判定する。ここでは、照合部153は、状態43から出ている間隔条件付き通常遷移をイベントに対応する遷移種別とする。そして、照合部153は、状態43の未処理のイベントリストr7 ́の最終受理位置と現在のイベント位置7が間隔条件を満たすか否かを判定する。選択したイベントリストr7 ́の最終受理位置が4であり、現在のイベント位置7との間隔が3であり、間隔条件5を超えていないので、照合部153は、間隔条件5を満たすと判定する。そして、照合部153は、通常遷移先の状態46に番号1が割り当てられているので、イベントリストの番号位置に現在のイベント位置7を書き込み、最終受理位置に現在のイベント位置7を設定する。そして、照合部153は、状態46のイベントリストr16として追加する。図28Jの3段目に示すように、系列0のイベントEについて、照合部153は、状態jの値を1ずつ増やしながら、状態jから出ている全てのε遷移とε=遷移の発動を実行する。照合部153は、状態25からε遷移が出ているので、状態25のイベントリストr13、r14をそれぞれ遷移先の状態26、27、28のイベントリストr13 ́、r14 ́として追加し、状態25のイベントリストr13、r14を削除する。続いて、照合部153は、状態49が合流ノードであるので、状態49のε=遷移元の状態28、37、46のイベントリストの、状態49で指定された指定番号の番号位置のイベント位置が一致しているイベントリストを探索する。ここでは、状態28のイベントリストr13 ́および状態37のイベントリストr15の指定番号0、1に対応するイベント位置が1、7で共通している。加えて、状態46のイベントリストr16の指定番号0、1に対応するイベント位置が任意のイベント位置、7であるので、状態28のイベントリストr13 ́および状態37のイベントリストr15のものと一致する。そこで、照合部152は、これらイベントリストr13 ́、r15、r16の組み合わせに対して、イベントリストを結合し、結合したイベントリストr20を状態49に追加する。図28Kに示すように、照合部153は、状態47のε=遷移元26のイベントリストr13 ́、r14 ́の、状態47で指定された指定番号0、1に対応するイベント位置を取り出す。ここでは、指定番号0の場合、照合部153は、イベントリストr13 ́、r14 ́から1、4を取り出す。この場合、照合部153は、取り出したイベント位置が{現在のイベント位置-状態47の番号0に対応するタイムアウト長}以下であるか否かを判定する。ここでは、取り出したイベント位置が1または4、現在のイベント位置は7、状態47の番号0に対応するタイムアウト長が7であり、1または4>7-7となるので、照合部153は、これらのイベントリストを削除しないこととなる。一方、指定番号1の場合、照合部153は、イベントリストr13 ́、r14 ́から7を取り出す。この場合、照合部153は、取り出したイベント位置が{現在のイベント位置-状態47の番号1に対応するタイムアウト長}以下であるか否かを判定する。ここでは、取り出したイベント位置が7、現在のイベント位置は7、状態47の番号1に対応するタイムアウト長が0であり、7=7-0となるので、照合部153は、タイムアウトであると判断し、イベントリストr13 ́、r14 ́を削除することとなる。続いて、照合部153は、状態48のε=遷移元27のイベントリストr13 ́、r14 ́についても、状態47の場合と同様に、番号1に対応するタイムアウトとなるので、各イベントリストr13 ́、r14 ́を削除することとなる。そして、照合部153は、状態49が最終状態で、イベントリストr20があるので、現在のイベント位置7を照合結果として通知し、状態49のイベントリストr20を削除する。すなわち、照合部153は、照合が完了した結果として、イベントパターンの終了時刻を通知する。そして、照合部153は、状態49まで処理を完了したので、全てのε遷移とε=遷移の発動を終了する。そして、続いて、図28Lに示すように、照合部153は、現在のイベント位置iの値を8に設定し、イベントストリーム143からイベント位置8および系列1のイベントDを読み込み、照合を続ける。続いて、図28M、図28Nに示すように、照合部153は、現在のイベント位置iの値を9に設定し、イベントストリーム143からイベント位置9および系列1のイベントEを読み込み、照合を続けることとなる。照合部153は、上述した図28A~図28Nに示す処理を実行することにより、NFA142を利用して、イベントストリーム143を照合する。そして、照合部153は、照合結果をユーザ端末50に通知する。なお、照合部153は、照合結果を表示部130に表示させても良い。上述した図28A~図28Nでは、照合結果を、イベントストリーム143上のイベントパターン141の終了時刻としたが、開始時刻を含んだものとしても良い。[実施例の効果]次に、本実施例にかかる照合装置100の効果について説明する。照合装置100は、複数系列のイベントを含むイベントパターンで141あってイベント間の発生順序と間隔条件とを伴ったイベントパターン141について、イベントパターン141に対応する仮NFAを生成する。そして、照合装置100は、生成した仮NFAの中のイベント同士が同系列で接続される同系列部分に対応するNFA部分を複数系列分複製する。そして、照合装置100は、複製した各NFA部分を各系列のイベントで受理する遷移に置き換え、置き換えた各NFA部分をε遷移で結合する。そして、照合装置100は、イベントストリーム143に含まれるイベントについて、複製したそれぞれのNFA部分のうち、当該イベントが発生した系列に対応したNFA部分で受理する。そして、照合装置100は、当該イベントを受理したNFA部分を動作させる。かかる構成によれば、照合装置100によれば、ある系列で発生したイベントを、発生した系列に対応したNFA部分で受理し動作させるようにしたので、当該イベントより前に発生したイベントとの系列の同一性を判定する処理を高速化できる。また、照合装置100は、イベントパターン141の中に同系列部分とイベント同士が任意の系列で接続される任意系列部分とが接続されている場合、生成した仮NFAの中の同系列部分に対応するNFA部分を切り離する。そして、照合装置100は、切り離したNFA部分を複数系列分複製する。そして、照合装置100は、複製した各NFA部分を各系列のイベントで受理する遷移に置き換え、置き換えた各NFA部分と切り離す前の元のNFAの接合部分とをε遷移で結合する。そして、照合装置100は、イベントストリーム143に含まれるイベントについて、複製した各NFA部分では、各NFA部分のうち当該イベントが発生した系列に対応したNFA部分で受理し当該NFA部分を動作させ、前記任意系列部分に対応するNFA部分では、当該NFA部分で受理し当該NFA部分を動作させる。かかる構成によれば、照合装置100によれば、ある系列で発生したイベントを、発生した系列に対応したNFA部分で受理し動作させるようにしたので、当該イベントより前に発生したイベントとの系列の同一性を判定する処理を高速化できる。また、照合装置100は、同系列部分に対応するNFA部分と任意系列部分に対応するNFA部分との接合部分が同系列部分に対応するNFA部分の途中に存在する場合、同系列部分を複製した各NFA部分と任意系列部分との接合部分として接続ノードを生成する。そして、照合装置100は、生成した接続ノードと同系列部分を複製した各NFA部分とをε遷移で接続し、生成した接続ノードと任意系列部分とをε遷移で接合する。かかる構成によれば、照合装置100によれば、同系列部分に対応するNFA部分と任意系列部分に対応するNFA部分との接合部分が同系列部分に対応するNFA部分の途中に存在する場合であっても、接続ノードを介して同系列部分と任意系列部分とをつなぐことができる。このため、照合装置100は、ある系列で発生したイベントを、発生した系列に対応したNFA部分で受理し動作させる処理を容易に実現できる。この結果、照合装置100は、当該イベントより前に発生したイベントとの系列の同一性を判定する処理を高速化できる。[プログラムなど]なお、照合装置100は、既知のパーソナルコンピュータ、ワークステーションなどの情報処理装置に、上記したNFA生成部152、照合部153などの各機能を搭載することによって実現することができる。また、図示した各装置の各構成要素は、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散統合の具体的態様は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散統合して構成することができる。例えば、NFA生成部152と照合部153とを1個の部として統合しても良い。一方、NFA生成部152を、仮NFAを生成する仮NFA生成部と、仮NFAから同系列のNFA探索する同系列NFA探索部と、同系列のNFAを変換する同系列NFA変換部とに分散しても良い。また、NFA142などの記憶部を照合装置100の外部装置としてネットワーク経由で接続するようにしても良い。また、上記実施例で説明した各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。そこで、以下では、図2に示した照合装置100と同様の機能を実現する照合プログラムを実行するコンピュータの一例を説明する。図29は、照合プログラムを実行するコンピュータの一例を示す図である。図29に示すように、コンピュータ200は、各種演算処理を実行するCPU201と、ユーザからのデータの入力を受け付ける入力装置202と、ディスプレイ203を有する。また、コンピュータ200は、記憶媒体からプログラム等を読取る読み取り装置204と、ネットワークを介して他のコンピュータとの間でデータの授受を行うインタフェース装置205とを有する。また、コンピュータ200は、各種情報を一時記憶するRAM206と、ハードディスク装置207を有する。そして、各装置201~207は、バス208に接続される。ハードディスク装置207は、NFA生成プログラム207a、照合プログラム207bを記憶する。CPU201は、各プログラム207a~207bを読み出して、RAM206に展開する。NFA生成プログラム207aは、NFA生成プロセス206aとして機能する。照合プログラム207bは、照合プロセス206bとして機能する。例えば、NFA生成プロセス206aは、NFA生成部152に対応する。照合プロセス206bは、照合部153に対応する。なお、各プログラム207a~207bについては、必ずしも最初からハードディスク装置207に記憶させておかなくてもよい。例えば、コンピュータ200に挿入されるフレキシブルディスクFD、CD-ROM、DVDディスク、光磁気ディスク、ICカードなどの可搬用の物理媒体に各プログラムを記憶させておく。そして、コンピュータ200がこれらから各プログラム207a~207bを読み出して実行するようにしても良い。以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。付記1複数系列のイベントを含むイベントパターンであってイベント間の発生順序と間隔条件とを伴ったイベントパターンについて、前記イベントパターンに対応するオートマトンを生成する処理、生成したオートマトンの中のイベント同士が同系列で接続される同系列部分に対応するオートマトン部分を複数系列分複製し、複製した各オートマトン部分を各系列のイベントで受理する遷移に置き換え、置き換えた各オートマトン部分をε遷移で結合する処理を行うことで、オートマトンを生成するオートマトン生成部と、複数系列の複数のイベントの発生順序を含むイベントストリームと、前記オートマトンとを順次比較し、前記イベントストリームに含まれるイベントについて、前記複製したそれぞれのオートマトン部分のうち、当該イベントが発生した系列に対応したオートマトン部分で受理し当該オートマトン部分を動作させることで、前記イベントストリームに前記イベントパターンが含まれているか否かを照合する照合部とを有することを特徴とする照合装置。付記2前記オートマトン生成部は、イベントパターンの中に前記同系列部分とイベント同士が任意の系列で接続される任意系列部分とが接続されている場合、生成したオートマトンの中の前記同系列部分に対応するオートマトン部分を切り離し、切り離したオートマトン部分を複数系列分複製し、複製した各オートマトン部分を各系列のイベントで受理する遷移に置き換え、置き換えた各オートマトン部分と切り離す前の元のオートマトンの接合部分とをε遷移で結合し、前記照合部は、前記イベントストリームに含まれるイベントについて、複製した各オートマトン部分では、各オートマトン部分のうち当該イベントが発生した系列に対応したオートマトン部分で受理し当該オートマトン部分を動作させ、前記任意系列部分に対応するオートマトン部分では、当該オートマトン部分で受理し当該オートマトン部分を動作させることを特徴とする付記1に記載の照合装置。付記3前記オートマトン生成部は、前記同系列部分に対応するオートマトン部分と前記任意系列部分に対応するオートマトン部分との接合部分が前記同系列部分に対応するオートマトン部分の途中に存在する場合、前記同系列部分を複製した各オートマトン部分と前記任意系列部分との接合部分として接続ノードを生成し、生成した接続ノードと前記同系列部分を複製した各オートマトン部分とをε遷移で接続し、生成した接続ノードと前記任意系列部分とをε遷移で接合することを特徴とする付記2に記載の照合装置。付記4コンピュータに、複数系列のイベントを含むイベントパターンであってイベント間の発生順序と間隔条件とを伴ったイベントパターンについて、前記イベントパターンに対応するオートマトンを生成する処理、生成したオートマトンの中のイベント同士が同系列で接続される同系列部分に対応するオートマトン部分を複数系列分複製し、複製した各オートマトン部分を各系列のイベントで受理する遷移に置き換え、置き換えた各オートマトン部分をε遷移で結合する処理を行うことで、オートマトンを生成し、複数系列の複数のイベントの発生順序を含むイベントストリームと、前記オートマトンとを順次比較し、前記イベントストリームに含まれるイベントについて、前記複製したそれぞれのオートマトン部分のうち、当該イベントが発生した系列に対応したオートマトン部分で受理し当該オートマトン部分を動作させることで、前記イベントストリームに前記イベントパターンが含まれているか否かを照合する各処理を実行させることを特徴とする照合プログラム。付記5コンピュータが、複数系列のイベントを含むイベントパターンであってイベント間の発生順序と間隔条件とを伴ったイベントパターンについて、前記イベントパターンに対応するオートマトンを生成する処理、生成したオートマトンの中のイベント同士が同系列で接続される同系列部分に対応するオートマトン部分を複数系列分複製し、複製した各オートマトン部分を各系列のイベントで受理する遷移に置き換え、置き換えた各オートマトン部分をε遷移で結合する処理を行うことで、オートマトンを生成し、複数系列の複数のイベントの発生順序を含むイベントストリームと、前記オートマトンとを順次比較し、前記イベントストリームに含まれるイベントについて、前記複製したそれぞれのオートマトン部分のうち、当該イベントが発生した系列に対応したオートマトン部分で受理し当該オートマトン部分を動作させることで、前記イベントストリームに前記イベントパターンが含まれているか否かを照合する各処理を実行することを特徴とする照合方法。