"単一の状態に対応付けられ、所定のイベントおよび遷移条件によって所定の状態に遷移する複数の第1状態を有する第1状態遷移情報と、遷移元の第1状態および遷移先の第1状態と、前記遷移元の第1状態から前記遷移先の第1状態に遷移する場合の遷移条件およびイベントとを対応付けた遷移条件集合情報とを記憶する記憶部と、前記第1状態遷移情報を基にして、複数の第1状態に対応付けられた第2状態を有する第2状態遷移情報を生成し、前記第2状態と、前記第2状態に対応付けられた第1状態および該第1状態に遷移する前の第1状態とを対応付けた対応マップ情報を生成する対応付け部と、継続的に無制限に入力される可能性がありかつ無視すべきイベントが間に入力され、複数のイベントとプロパティとを対応付けた入力イベント列の先頭のイベントから順に、前記第2状態遷移情報と比較して、前記第2状態遷移情報の初期状態から順に第2状態を遷移させ、遷移する度に、遷移した際のイベントおよびプロパティと遷移先の第2状態とを順にリスト情報に格納し、リスト情報に格納された第2状態が受理状態である場合に、該第2状態から前記リスト情報を逆順に辿って、該リスト情報に格納されたイベントおよびプロパティと、第2状態とを抽出し、前記遷移条件集合情報および前記対応マップを基にして、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定するオートマトン実行部とを有することを特徴とする情報処理装置。前記オートマトン実行部は、受理状態となる複数の第2状態がリスト情報に格納されている場合には、各第2状態を起点として、前記リスト情報を逆順に辿り、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定することを特徴とする請求項1に記載の情報処理装置。前記オートマトン実行部は、前記遷移条件集合情報および前記対応マップを基にして、前記抽出した第2状態を第1状態に戻して、第1状態による状態遷移を受理状態から逆順に辿り、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定することを特徴とする請求項1または2に記載の情報処理装置。コンピュータが実行する情報処理方法であって、前記コンピュータは、単一の状態に対応付けられ、所定のイベントおよび遷移条件によって所定の状態に遷移する複数の第1状態を有する第1状態遷移情報と、遷移元の第1状態および遷移先の第1状態と、前記遷移元の第1状態から前記遷移先の第1状態に遷移する場合の遷移条件およびイベントとを対応付けた遷移条件集合情報とを記憶する記憶装置を有し、前記コンピュータが、前記第1状態遷移情報を基にして、複数の第1状態に対応付けられた第2状態を有する第2状態遷移情報を生成し、前記第2状態と、前記第2状態に対応付けられた第1状態および該第1状態に遷移する前の第1状態とを対応付けた対応マップ情報を生成し、継続的に無制限に入力される可能性がありかつ無視すべきイベントが間に入力され、複数のイベントとプロパティとを対応付けた入力イベント列の先頭のイベントから順に、前記第2状態遷移情報と比較して、前記第2状態遷移情報の初期状態から順に第2状態を遷移させ、遷移する度に、遷移した際のイベントおよびプロパティと遷移先の第2状態とを順にリスト情報に格納し、リスト情報に格納された第2状態が受理状態である場合に、該第2状態から前記リスト情報を逆順に辿って、該リスト情報に格納されたイベントおよびプロパティと、第2状態とを抽出し、前記遷移条件集合情報および前記対応マップを基にして、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定する各処理を実行することを特徴とする情報処理方法。単一の状態に対応付けられ、所定のイベントおよび遷移条件によって所定の状態に遷移する複数の第1状態を有する第1状態遷移情報と、遷移元の第1状態および遷移先の第1状態と、前記遷移元の第1状態から前記遷移先の第1状態に遷移する場合の遷移条件およびイベントとを対応付けた遷移条件集合情報とを記憶する記憶装置を有するコンピュータに、前記第1状態遷移情報を基にして、複数の第1状態に対応付けられた第2状態を有する第2状態遷移情報を生成し、前記第2状態と、前記第2状態に対応付けられた第1状態および該第1状態に遷移する前の第1状態とを対応付けた対応マップ情報を生成し、継続的に無制限に入力される可能性がありかつ無視すべきイベントが間に入力され、複数のイベントとプロパティとを対応付けた入力イベント列の先頭のイベントから順に、前記第2状態遷移情報と比較して、前記第2状態遷移情報の初期状態から順に第2状態を遷移させ、遷移する度に、遷移した際のイベントおよびプロパティと遷移先の第2状態とを順にリスト情報に格納し、リスト情報に格納された第2状態が受理状態である場合に、該第2状態から前記リスト情報を逆順に辿って、該リスト情報に格納されたイベントおよびプロパティと、第2状態とを抽出し、前記遷移条件集合情報および前記対応マップを基にして、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定する各処理を実行させることを特徴とする情報処理プログラム。しかしながら、遷移条件を含む状態遷移機械の状態集合をNFAの状態に対応付けると、パターンの照合精度が低下するという問題があった。例えば、図39に示した状態遷移機械10Eの状態集合を、NFAの状態に対応付け、図40に示した状態遷移機械10Fとした場合の問題点について説明する。状態遷移機械10Eでは、状態1から状態2にイベントbによって遷移する場合に、遷移条件xidyidを充足するか否かを判定していた。しかし、状態遷移機械10Eでは、状態d1から状態d2にイベントbで遷移する場合、状態d2から状態d2にイベントbで遷移する場合のどちらで、遷移条件を充足するか否かを判定すればよいのかが不確定となる。また、遷移条件のxidに対応するイベントaのプロパティidは、状態d0から状態d1の遷移に対応するものか、状態d1から状態d1の遷移に対応するものか、状態d2から状態d1の遷移に対応するものかが不確定となる。なお、上記問題を解消するために、遷移条件の遷移に関連する状態集合の一部を、NFAの状態に対応付けないで利用することも考えられる。しかし、この場合には、イベントの到着ごとに複数の状態遷移を行うため、処理時間やメモリ使用量が増加してしまう。開示の技術は、上記に鑑みてなされたものであって、パターンの照合精度の低下を防止することができる情報処理装置、情報処理方法および情報処理プログラムを提供することを目的とする。開示の情報処理装置は、記憶部と対応付け部とオートマトン実行部とを有する。記憶部は、単一の状態に対応付けられ、所定のイベントおよび遷移条件によって所定の状態に遷移する複数の第1状態を有する第1状態遷移情報を記憶する。また、記憶部は、遷移元の第1状態および遷移先の第1状態と、遷移元の第1状態から前記遷移先の第1状態に遷移する場合の遷移条件およびイベントとを対応付けた遷移条件集合情報とを記憶する。対応付け部は、第1状態遷移情報を基にして、複数の第1状態に対応付けられた第2状態を有する第2状態遷移情報を生成する。また、対応付け部は、第2状態と、第2状態に対応付けられた第1状態および該第1状態に遷移する前の第1状態とを対応付けた対応マップ情報を生成する。オートマトン実行部は、継続的に無制限に入力される可能性がありかつ無視すべきイベントが間に入力される入力イベント列の先頭のイベントから順に、第2状態遷移情報と比較して、第2状態遷移情報の初期状態から順に第2状態を遷移させる。そして、オートマトン実行部は、遷移させる度に、遷移した際のイベントおよびプロパティと遷移先の第2状態とを順にリスト情報に格納する。また、オートマトン実行部は、リスト情報に格納された第2状態が受理状態である場合に、該第2状態からリスト情報を逆順に辿って、該リスト情報に格納されたイベントおよびプロパティと、第2状態とを抽出する。オートマトン実行部は、抽出する過程において、遷移条件集合情報および対応マップを基にして、遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定する。開示の情報処理装置によれば、パターンの照合精度が低下することを防止するという効果を奏する。以下に、本願の開示する情報処理装置、情報処理方法および情報処理プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。本実施例にかかる情報処理装置の構成の一例について説明する。図1は、本実施例にかかる情報処理装置の構成を示す機能ブロック図である。図1に示すように、情報処理装置100は、入力部110、出力部120、記憶部130、制御部140を有する。入力部110は、各種の情報を情報処理装置100に入力する入力装置である。例えば、利用者は、入力部110を操作して、後述する入力イベント列130fを入力する。入力部110は、キーボードやマウス、タッチパネル等に対応する。なお、入力部110は、他の装置から情報を受け付け、受け付けた情報を情報処理装置100に入力する入力装置であってもよい。出力部120は、制御部140の処理結果を出力する装置である。出力部120は、ディスプレイ等の表示装置に対応する。なお、出力部120は、他の装置に情報を出力する出力装置であってもよい。記憶部130は、非決定性状態集合情報130a、遷移条件集合情報130b、決定性状態集合情報130c、対応マップ130d、付加アクション情報130e、入力イベント列130fを記憶する。また、記憶部130は、リスト情報130g、スタック130h、充足判定情報130i、充足判定対象情報130jを記憶する。記憶部130は、例えば、RAMRandomAccessMemory、ROMReadOnlyMemory、フラッシュメモリFlashMemoryなどの半導体メモリ素子、またはハードディスク、光ディスクなどの記憶装置に対応する。非決定性状態集合情報130aは、図36に示した状態遷移機械10Bに対応する非決定性有限オートマトンである。非決定性状態集合情報130aは、非決定的に状態遷移する。非決定性状態集合情報130aは、例えば、第1状態遷移情報に対応する。図2は、非決定性状態集合情報のデータ構造の一例を示す図である。図2に示すように、非決定性状態集合情報130aは、テーブル20A~20Cを有する。テーブル20Aは、遷移元状態と、イベント記号と、遷移先状態と、イベント種別とを対応付ける。このうち、イベント種別は、該当する遷移を引き起こしたイベントと該イベントのプロパティをパターン条件に合致するイベント列検出時に検出結果として出力するか否かを示す情報である。スキップの場合には、イベントと該イベントのプロパティidの検出結果の一部としてそのイベントを出力しない。検出対象の場合には、イベント記号と該イベントのプロパティidの検出結果の一部としてそのイベントを出力する。なお、この実施例ではイベントがidという名前のプロパティのみを持つ場合で説明しているが、一般にはイベントは複数種類のプロパティを持つ。テーブル20Aの1段目では、イベントaによって、状態0から状態0に遷移することを示す。この場合には、イベント種別がスキップであるため、イベントaと、このイベントaのプロパティの出力は行われない。テーブル20Aの4段目では、イベントaによって、状態0から状態1に遷移することを示す。この場合には、イベント種別が検出対象であるため、イベントaと、このイベントaのプロパティidの出力が行われる。テーブル20Bは、初期状態を示す情報を格納する。図2に示す例では、初期状態は状態0となっている。このため、状態0から状態遷移が開始される。テーブル20Cは、受理状態を示す情報を格納する。図2に示す例では、受理状態は状態2となっている。このため、状態2に到達した場合に、所定のパターンが照合されたことになる。なお、受理状態は2つ以上ある場合がある。遷移条件集合情報130aは、遷移元の状態および遷移先の状態と、遷移元の状態から遷移先の状態に遷移する場合の遷移条件およびイベントを対応付けた情報である。図3は、遷移条件集合情報のデータ構造の一例を示す図である。図3に示すように、遷移条件集合情報130bは、遷移元状態と、遷移先状態と、イベント記号と、イベント記号参照名と、遷移条件とを対応付ける。このうち、イベント記号参照名は、イベント記号とイベント記号に対応するプロパティidと対応付ける参照名である。図3の1段目では、イベントaによって、状態0から状態1に遷移した場合に、イベントaとイベントaのプロパティidを、イベント記号参照名xと対応付ける。遷移条件は、ある状態をある状態に遷移する場合の条件である。例えば、図3の2段目では、遷移条件xidyidを満たす場合に、イベントbによって状態1から状態2に遷移することを示す。遷移条件xidyidの意味は、状態0から状態1に遷移したイベントaのプロパティidと、状態1から状態2に遷移したイベントbのプロパティidが等しいというものである。決定性状態集合情報130cは、非決定性状態集合情報130aを、DFAの状態に対応付けた状態集合情報である。本実施例では、非決定性状態集合情報130aの状態と、決定性状態集合情報130cの状態とを区別するために、決定性状態集合情報130cの状態を状態Dとする。状態Dは、非決定性状態集合130aの複数の状態に対応付けられる。決定性状態集合情報130cは、第2状態遷移情報に対応する。図4は、決定性状態集合情報のデータ構造の一例を示す図である。図4に示すように、決定性状態集合情報130cは、状態Dがどのイベントによって、どの状態Dに遷移するのかを示す情報を有する。例えば、図4の1段目では、状態D0は、イベントaにより状態D1に遷移する。状態D0は、イベントbにより状態D2に遷移する。状態D0は、イベントcにより状態D2に遷移する。また、決定性状態集合情報130cには、初期状態がどの状態Dであるのかが登録されている。図4に示す例では初期状態30Bは、状態D0となる。対応マップ130dは、状態Dと、状態Dに対応付けられた状態および該状態に遷移する前の状態とを対応付けた情報である。図5は、対応マップのデータ構造の一例を示す図である。図5に示すように、対応マップ130dは、状態と、対応情報とを対応付ける。対応情報において、矢印の先が、状態Dに対応する状態を示す。また、矢印の前は、遷移前の状態を示す。例えば、状態D1の対応情報は{0→0、0→1}となっている。このため、状態D1に対応する状態は、状態0と状態1である。また、状態0の遷移前の状態は状態0であり、状態1の遷移前の状態は0であることを示す。なお、状態D0の対応情報に含まれるiは、初期状態に遷移する前の状態として付加した状態を示すiはイベントの入力なしで状態0に遷移ε遷移する。状態iは初期状態を含めて同じ手順で処理を行えるよう付加した仮想的な状態である。付加アクション情報130eは、受理状態となる状態Dを記憶し、該状態Dによって付加アクションを実行することを示す情報である。図6は、付加アクション情報のデータ構造の一例を示す図である。付加アクションに関する説明は後述する。入力イベント列130fは、一連のイベントを含む情報である。入力イベント列130fは、イベント記号とプロパティidとを対応付ける。図7は、入力イベント列のデータ構造の一例を示す図である。図7に示すイベント列は、左端のイベントが先頭のイベントであり、左側から右側に向かってイベントが並んでいるものとする。具体的には、イベント列は、イベントa、a、b、bを含み、最初の4つのイベントの各プロパティidはそれぞれ、1、2、2、1となる。リスト情報130gは、入力イベント列130fにより遷移する決定性状態集合情報130cの状態Dと、該状態Dに遷移した際のイベントおよびプロパティidとを順に記憶する情報である。図8は、リスト情報のデータ構造の一例を示す図である。図8に示すように、リスト情報は、位置と状態/イベントを含む。位置は、リスト情報130g上の位置を一意に識別する情報であり、状態/イベントには、状態Dまたはイベントおよびプロパティidが格納される。リスト情報130gが生成される過程の説明は後述する。スタック130hは、状態またはリスト情報の位置を順次記憶するスタックである。図9は、スタックのデータ構造の一例を示す図である。図9に示すように、スタック130hは、状態またはイベントポインタを順次記憶する。イベントポインタは、リスト情報上の位置に対応するものである。スタック130hに情報が格納される過程の説明は後述する。充足判定情報130iは、遷移条件が充足したか否かの情報を含む。図10は、充足判定情報のデータ構造の一例を示す図である。図10に示すように、充足判定情報130iは、遷移条件と判定状況とを対応付ける。判定状況は、遷移条件を充足したか否かの情報を示す。充足判定対象情報130j、遷移条件を判定する場合のイベント記号参照名の場所を指定する情報である。図11は、充足判定対象情報のデータ構造の一例を示す図である。図11に示すように、充足判定対象情報130j、イベント記号参照名と、イベントポインタとを対応付ける。図11に示す例では、イベント記号参照名xの情報は、リスト情報130gの位置1に格納されていることを示す。イベント記号参照名yの情報は、リスト情報130gの位置7に格納されていることを示す。後述の制御部140が、遷移条件xidyidを満たしているか否かを判定する時点で、充足判定対象情報のデータが、図11に示すものであれば、リスト情報130gの位置1の情報と7の情報が比較される。制御部140は、対応付け部140aと、オートマトン実行部140bとを有する。制御部140は、例えば、ASICApplicationSpecificIntegratedCircuitや、FPGAFieldProgrammableGateArrayなどの集積装置に対応する。また、制御部140は、例えば、CPUやMPUMicroProcessingUnit等の電子回路に対応する。対応付け部140aは、非決定性状態集合情報130aを基にして、決定性状態集合情報130cと、対応マップ130dと、付加アクション情報130eを生成する処理部である。対応付け部140aは、非決定性状態集合情報130aの複数の状態を、単一の状態Dに対応付けることで、決定性状態集合情報130cを生成する。対応付け部140aは、状態Dに対応付けられた状態の、所定のイベントによる遷移元と遷移先の関係から、対応マップ130dを生成する。また、対応付け部140aは、受理状態となる状態を含む状態Dに対応して、付加アクション情報130eを生成する。ここで、対応付け部140aの処理手順の一例について説明する。図12は、対応付け部の処理手順を示すフローチャートである。図12に示す処理は、例えば、入力部110から、対応付け指示を受け付けた場合に、処理を開始しても良いし、非決定性状態集合情報130aが記憶部130に格納された場合に、処理を開始してもよい。なお、図12に記載する対処待ち集合、一時格納テーブルは、例えば、対応付け部140aが保持するものとする。図12に示すように、対応付け部140aは、対処待ち集合に初期状態D0をセットし、状態D0を初期状態として、決定性状態集合情報130cの初期状態30Bに登録するステップS101。対応付け部140aは、対応マップ130dにD0と{i→1}とを登録するステップS102。対応付け部140aは、対応待ち集合から一つの状態を取り出すステップS103。対応付け部140aは、状態Dに対応する、対応付け前の遷移の遷移先の状態をリストアップするステップS104。対応付け部140aは、全イベント記号の集合の中から未選択のイベント記号イベント記号eと呼ぶを一つ選択しステップS105、一時格納テーブルを空に設定するステップS106。対応付け部140aは、リストアップした状態の中から未選択の状態sを一つ選択するステップS107。対応付け部140aは、遷移元の状態がsであり、イベント記号eによる遷移を非決定性状態集合情報130aからリストアップするステップS108。対応付け部140aは、リストアップした遷移群を、一時格納テーブルに格納するステップS109。対応付け部140aは、状態sを全て選択したか否かを判定するステップS110。対応付け部140aは、状態sを全て選択していない場合にはステップS110,No、ステップS107に移行する。対応付け部140aは、状態sを全て選択した場合にはステップS110,Yes、一時格納テーブルの遷移群が、状態D’と既に対応付いているか否かを判定するステップS111。ここで、状態D’は、一時格納テーブルの遷移と対応付けられた状態Dに対応するものである。対応付け部140aは、一時格納テーブルの遷移群が、状態D’と既に対応付いている場合にはステップS111,Yes、ステップS115に移行する。一方、対応付け部140aは、一時格納テーブルの遷移群が、状態D’と既に対応付いていない場合にはステップS111,No、新規の状態D’を作成し、リストアップした遷移群と対応付けるステップS112。対応付け部140aは、新規の状態D’を処理待ち集合に追加するステップS113。対応付け部140aは、新規の状態D’が受理状態の場合には、状態D’を付加アクション情報130eに登録するステップS114。対応付け部140aは、イベント記号aをトリガとする状態Dから状態D’への遷移を決定性状態集合情報130cに登録するステップS115。ステップS115のイベント記号aは、ステップS105で選択したイベント記号である。対応付け部140aは、イベント記号を全て選択したか否かを判定する。対応付け部140aは、イベント記号を全て選択していない場合にはステップS116,No、ステップS105に移行する。一方、対応付け部140aは、イベント記号を全て選択した場合にはステップS116,Yes、対処待ち集合か空であるか否かを判定するステップS117。対応付け部140aは、対処待ち集合が空ではない場合にはステップS117,NoステップS103に移行する。一方、対応付け部140aは、対処待ち集合が空の場合にはステップS117,Yes、処理を終了する。次に、対応付け部140aが、図12に示した処理手順に基づいて、決定性状態集合情報130cと、対応マップ130dと、付加アクション情報130eを生成する過程を示す。図13~図19は、対応付け部の処理を説明するための図である。図13について説明する。対応付け部140aは、対応マップ130dの状態にD0を登録し、対応情報に{i→0}を登録する。また、対処待ち集合50Aに状態D0を登録する。なお、対処待ち集合50Aは、対応付け部140aが保持しているものとする。また、状態D0は、状態iから遷移する状態0に対応する。図14について説明する。対応付け部140aは、対応待ち集合50Aから状態D0を取り出す。対応付け部140aは、状態D0に対応する状態0から、イベントaによって遷移する状態を、非決定性状態集合情報130aを基に判定すると、状態0、状態1となる。このため、対応付け部140aは、対応情報に{0→0,0→1}と、新たな状態D1とを対応マップ130dに登録する。対応付け部140aは、状態D1を対処待ち集合50Aに登録する。対応付け部140aは、状態D0が、イベントaによって、状態D1に遷移する旨を、決定性状態集合情報130cに登録する。図14において、対応情報の矢印の先が、状態Dに対応する状態であり、矢印の先の反対側は、遷移前の状態を示す。例えば、状態D0は、状態0、1に対応付けられており、遷移前の状態は、状態0である。対応付け部140aは、状態D0に対応する状態0から、イベントbによって遷移する状態を、非決定性状態集合情報130aを基に判定すると、状態0となる。このため、対応付け部140aは、対応情報に{0→0}と、新たな状態D2とを対応マップ130dに登録する。対応付け部140aは、状態D2を対処待ち集合50Aに登録する。対応付け部140aは、状態D0が、イベントbによって、状態D2に遷移する旨を、決定性状態集合情報130cに登録する。対応付け部140aは、状態D0に対応する状態0から、イベントcによって遷移する状態を、非決定性状態集合情報130aを基に判定すると、状態0となる。この遷移元の状態と遷移先の状態は、状態D2の対応情報に対応するため、対応付け部140aは、新たな情報を、対応マップ130dに登録しない。対応付け部140aは、状態D0が、イベントcによって、状態D2に遷移する旨を、決定性状態集合情報130cに登録する。図15について説明する。対応付け部140aは、対応待ち集合50Aから状態D1を取り出す。対応付け部140aは、状態D1に対応する状態0、状態1から、イベントaによって遷移する状態を、非決定性状態集合情報130aを基に判定する。遷移元を状態0とすると、イベントaにより、状態0と状態1に遷移する。また、遷移元を状態1とすると、イベントaにより、状態1に遷移する。このため、対応付け部140aは、対応情報に{0→0,0→1,1→1}と、新たな状態D3とを対応マップ130dに登録する。対応付け部140aは、状態D3を対処待ち集合50Aに登録する。対応付け部140aは、状態D1が、イベントaによって、状態D3に遷移する旨を、決定性状態集合情報130cに登録する。対応付け部140aは、状態D1に対応する状態0、状態1から、イベントbによって遷移する状態を、非決定性状態集合情報130aを基に判定する。遷移元を状態0とすると、イベントbにより、状態0に遷移する。また、遷移元を状態1とすると、イベントbにより、状態1、状態2に遷移する。このため、対応付け部140aは、対応情報に{0→0,1→1,1→2}と、新たな状態D4とを対応マップ130dに登録する。対応付け部140aは、状態D4を対処待ち集合50Aに登録する。対応付け部140aは、状態D1が、イベントbによって、状態D4に遷移する旨を、決定性状態集合情報130cに登録する。対応付け部140aは、状態D1に対応する状態0、状態1から、イベントcによって遷移する状態を、非決定性状態集合情報130aを基に判定する。遷移元を状態0とすると、イベントcにより、状態0に遷移する。また、遷移元を状態1とすると、イベントcにより、状態1に遷移する。このため、対応付け部140aは、対応情報に{0→0,1→1}と、新たな状態D5とを対応付けマップ130dに登録する。対応付け部140aは、状態D5を対処待ち集合50Aに登録する。対応付け部140aは、状態D1が、イベントcによって、状態D5に遷移する旨を、決定性状態集合情報130cに登録する。図16について説明する。対応付け部140aは、対応待ち集合50Aから状態D2を取り出す。対応付け部140aは、状態D2に対応する状態0から、イベントaによって遷移する状態を、非決定性状態集合情報130aを基に判定する。状態0は、イベントaによって、状態0、状態1に遷移する。この遷移元の状態と遷移先の状態は、状態D1の対応情報に対応するため、対応付け部140aは、新たな情報を、対応マップ130dに登録しない。対応付け部140aは、状態D2が、イベントaによって、状態D1に遷移する旨を、決定性状態集合情報130cに登録する。対応付け部140aは、状態D2に対応する状態0から、イベントbによって遷移する状態を、非決定性状態集合情報130aを基に判定する。状態0は、イベントbによって、状態0に遷移する。この遷移元の状態と遷移先の状態は、状態D2の対応情報に対応するため、対応付け部140aは、新たな情報を、対応マップ130dに登録しない。対応付け部140aは、状態D2が、イベントbによって、状態D2に遷移する旨を、決定性状態集合情報130cに登録する。対応付け部140aは、状態D2に対応する状態0から、イベントcによって遷移する状態を、非決定性状態集合情報130aを基に判定する。状態0は、イベントcによって、状態0に遷移する。この遷移元の状態と遷移先の状態は、状態D2の対応情報に対応するため、対応付け部140aは、新たな情報を、対応マップ130dに登録しない。対応付け部140aは、状態D2が、イベントcによって、状態D2に遷移する旨を、決定性状態集合情報130cに登録する。図17について説明する。対応付け部140aは、対応待ち集合50Aから状態D3を取り出す。対応付け部140aは、状態D3に対応する状態0、状態1から、イベントaによって遷移する状態を、非決定性状態集合情報130aを基に判定する。遷移元を状態0とすると、イベントaにより、状態0と状態1に遷移する。また、遷移元を状態1とすると、イベントaにより、状態1に遷移する。この遷移元の状態と遷移先の状態は、状態D3の対応情報に対応するため、対応付け部140aは、新たな情報を、対応マップ130dに登録しない。対応付け部140aは、状態D3が、イベントaによって、状態D3に遷移する旨を、決定性状態集合情報130cに登録する。対応付け部140aは、状態D3に対応する状態0、状態1から、イベントbによって遷移する状態を、非決定性状態集合情報130aを基に判定する。遷移元を状態0とすると、イベントbにより、状態0に遷移する。また、遷移元を状態1とすると、イベントbにより、状態1、状態2に遷移する。この遷移元の状態と遷移先の状態は、状態D4の対応情報に対応するため、対応付け部140aは、新たな情報を、対応マップ130dに登録しない。対応付け部140aは、状態D3が、イベントbによって、状態D4に遷移する旨を、決定性状態集合情報130cに登録する。対応付け部140aは、状態D3に対応する状態0、状態1から、イベントcによって遷移する状態を、非決定性状態集合情報130aを基に判定する。遷移元を状態0とすると、イベントcにより、状態0に遷移する。また、遷移元を状態1とすると、イベントcにより、状態1に遷移する。この遷移元の状態と遷移先の状態は、状態D5の対応情報に対応するため、対応付け部140aは、新たな情報を、対応マップ130dに登録しない。対応付け部140aは、状態D3が、イベントcによって、状態D5に遷移する旨を、決定性状態集合情報130cに登録する。図18について説明する。対応付け部140aは、対応待ち集合50Aから状態D4を取り出す。この状態D4は、対応マップ130dを参照すると、状態0、1、2に対応付けられている。状態2は、非決定性状態集合情報130aにより受理状態である。対応付け部140aは、状態D4を、付加アクション情報130eに登録する。対応付け部140aは、状態D4に対応する状態0、1、2のうち、状態0、1からイベントaによって遷移する状態を、非決定性状態集合情報130aを基に判定する。状態2は受理状態であるため、スキップする。遷移元を状態0とすると、イベントaにより、状態0、状態1に遷移する。また、遷移元を状態1とすると、イベントaにより、状態1に遷移する。この遷移元の状態と遷移先の状態は、状態D3に対応するため、対応付け部140aは、新たな情報を、対応マップ130dに登録しない。対応付け部140aは、状態D4が、イベントaによって、状態D3に遷移する旨を、決定性状態集合情報130cに登録する。対応付け部140aは、状態D4に対応する状態0、1、2のうち、状態0、1からイベントbによって遷移する状態を、非決定性状態集合情報130aを基に判定する。遷移元を状態0とすると、イベントbにより、状態0に遷移する。また、遷移元を状態1とすると、イベントbにより、状態1、状態2に遷移する。この遷移元の状態と遷移先の状態は、状態D4に対応するため、対応付け部140aは、新たな情報を、対応マップ130dに登録しない。対応付け部140aは、状態D4が、イベントbによって、状態D4に遷移する旨を、決定性状態集合情報130cに登録する。対応付け部140aは、状態D4に対応する状態0、1、2のうち、状態0、1からイベントcによって遷移する状態を、非決定性状態集合情報130aを基に判定する。遷移元を状態0とすると、イベントcにより、状態0に遷移する。また、遷移元を状態1とすると、イベントcにより、状態1に遷移する。この遷移元の状態と遷移先の状態は、状態D5に対応するため、対応付け部140aは、新たな情報を、対応マップ130dに登録しない。対応付け部140aは、状態D4が、イベントcによって、状態D5に遷移する旨を、決定性状態集合情報130cに登録する。図19について説明する。対応付け部140aは、対応待ち集合50Aから状態D5を取り出す。対応付け部140aは、状態D5に対応する状態0、状態1から、イベントaによって遷移する状態を、非決定性状態集合情報130aを基に判定する。遷移元を状態0とすると、イベントaにより、状態0、状態1に遷移する。また、遷移元を状態1とすると、イベントaにより、状態1に遷移する。この遷移元の状態と遷移先の状態は、状態D3に対応するため、対応付け部140aは、新たな情報を、対応マップ130dに登録しない。対応付け部140aは、状態D5が、イベントaによって、状態D3に遷移する旨を、決定性状態集合情報130cに登録する。対応付け部140aは、状態D5に対応する状態0、状態1から、イベントbによって遷移する状態を、非決定性状態集合情報130aを基に判定する。遷移元を状態0とすると、イベントbにより、状態0に遷移する。また、遷移元を状態1とすると、イベントbにより、状態1、状態2に遷移する。この遷移元の状態と遷移先の状態は、状態D4に対応するため、対応付け部140aは、新たな情報を、対応マップ130dに登録しない。対応付け部140aは、状態D5が、イベントaによって、状態D4に遷移する旨を、決定性状態集合情報130cに登録する。対応付け部140aは、状態D5に対応する状態0、状態1から、イベントcによって遷移する状態を、非決定性状態集合情報130aを基に判定する。遷移元を状態0とすると、イベントcにより、状態0に遷移する。また、遷移元を状態1とすると、イベントcにより、状態1に遷移する。この遷移元の状態と遷移先の状態は、状態D5に対応するため、対応付け部140aは、新たな情報を、対応マップ130dに登録しない。対応付け部140aは、状態D5が、イベントcによって、状態D5に遷移する旨を、決定性状態集合情報130cに登録する。図19に示す処理が終わった時点で、処理待ち集合50Aが空になるため、対応付け部140aは、処理を終了する。上記のように、図13~図19に示す処理を、対応付け部140aが実行することで、決定性状態集合情報130c、対応マップ130d、付加アクション情報130eが生成される。図1の説明に戻る。オートマトン実行部140bは、遷移条件を充足しつつ、受理状態に至るイベントの組を判定する処理部である。図20~図22は、オートマトン実行部の処理の概要を説明するための図である。オートマトン実行部140bは、入力イベント列130fの先頭のイベントから順に、決定性状態集合情報130cと比較して、状態Dを遷移させる。一例として、入力イベント列130fを、図7に示すように、a、a、b、b、で始まる無限の列とし、最初の4つの各イベントのプロパティidをそれぞれ1、2、2、1とする。この場合には、図20に示すように、状態Dは、初期状態D0、状態D1、状態D3、状態D4、状態D4の順に遷移する。なお、各状態Dは、対応情報に対応付けられている。対応情報は、図5等に示したものである。オートマトン実行部140bは、受理状態を含む状態Dを特定する。オートマトン実行部140bは、特定した状態Dの受理状態を起点として、遷移前の状態を辿っていく。また、オートマトン実行部140bは、状態を辿っていく際に、非決定性状態集合情報130aを基にして、検出対象となる遷移を特定する。検出対象となる遷移では、遷移を引き起こしたイベント記号と、イベント記号に対応するプロパティidを検出する。図20に示した先頭から4番目のD4は、受理状態を含む状態Dである。オートマトン実行部140bは、4番目の状態D4の受理状態2を起点として、遷移前の状態を辿っていくと、図21の60に示す状態遷移列となる。図20に示した先頭から5番目のD4は、受理状態を含む状態Dである。オートマトン実行部140bは、5番目の状態D4の受理状態2を起点として、遷移前の状態を辿っていくと、図21の70に示す状態遷移列となる。図21の状態遷移列60が生成される過程を説明する。図20において、4番目の状態D4の状態2の遷移前は、状態1である。3番目の状態D3の状態1の遷移前は、状態0または状態1である。2番目の状態D1の状態0の遷移前は、状態0である。また、2番目の状態D1の状態1の遷移前は、状態0である。初期状態D0に状態0の遷移前は、状態iとなる。このため、オートマトン実行部140bは、状態遷移列60を生成する。また、図2に示すとおり、状態0から状態1への遷移、状態1から状態2への遷移が検出対象の遷移となる。図21の状態遷移列60は、状態遷移列60aと状態遷移列60bとを含む。また、遷移61を引き起こすイベント記号とプロパティidの組は、図20を参照すると、イベントa、プロパティid=1となる。遷移62を引き起こすイベント記号とプロパティidの組は、図20を参照すると、イベントa、プロパティid=2となる。遷移63を引き起こすイベント記号とプロパティidの組は、図20を参照すると、イベントb、プロパティid=2となる。ここで、遷移条件を充足する状態遷移列は、状態遷移列60aとなることがわかる。このため、オートマトン実行部140bは、状態遷移列60aを残し、状態遷移列60bを削除する。図21の状態遷移列70が生成される過程を説明する。図20において、5番目の状態D4の状態2の遷移前は、状態1である。4番目の状態D4の状態1の遷移前は、状態1である。3番目の状態D3の状態1の遷移前は、状態0または状態1である。2番目の状態D1の状態0の遷移前は、状態0である。また、2番目の状態D1の状態1の遷移前は、状態0である。初期状態D0に状態0の遷移前は、状態iとなる。このため、オートマトン実行部140bは、状態遷移列70を生成する。また、図2に示すとおり、状態0から状態1への遷移、状態1から状態2への遷移が検出対象の遷移となる。図21の状態遷移列70は、状態遷移列70aと状態遷移列70bとを含む。また、遷移71を引き起こすイベント記号とプロパティidの組は、図20を参照すると、イベントa、プロパティid=1となる。遷移72を引き起こすイベント記号とプロパティidの組は、図20を参照すると、イベントa、プロパティid=2となる。遷移73を引き起こすイベント記号とプロパティidの組は、図20を参照すると、イベントb、プロパティid=1となる。ここで、遷移条件を充足する状態遷移列は、状態遷移列70bとなることがわかる。このため、オートマトン実行部140bは、状態遷移列70bを残し、状態遷移列70aを削除する。上記処理を実行することで、図22に示すように、状態遷移列60aと状態遷移列70bとが残る。状態遷移列60a、70bは、遷移条件を充足しつつ、受理状態に遷移するものである。オートマトン実行部140bは、状態遷移列60a、70bを引き起こしたイベントおよびプロパティidの組を出力する。状態遷移列60aを引き起こしたイベントおよびプロパティidの組は、イベントa、プロパティid=2、イベントb、プロパティid=2となる。状態遷移列70bを引き起こしたイベントおよびプロパティidの組は、イベントa、プロパティid=1、イベントb、プロパティid=1となる。次に、オートマトン実行部140bの処理をより詳細に説明する。オートマトン実行部140bは、入力イベント列130fの先頭のイベントから順に、決定性状態集合情報130cと比較する。オートマトン実行部140bは、比較結果により、初期状態D0から状態Dを遷移させ、遷移する度に、イベント記号およびプロパティと、遷移先の状態Dとを順にリスト情報130gに格納する。また、オートマトン実行部140bは、リスト情報130gに格納された状態Dが受理状態に対応する場合に、リスト情報130gにおいて、該当する状態Dを逆順に辿る。オートマトン実行部140bは、逆順に辿る過程において、イベント記号およびプロパティと、状態Dをリスト情報130gから抽出し、遷移条件集合情報130bおよび対応マップ130dを基にして、遷移条件を充足しつつ、受理状態に至ったイベント列のイベントおよびプロパティの組を判定する。ここで、オートマトン実行部140bが、リスト情報130gを生成する処理の処理手順について説明する。図23は、リスト情報を生成する処理の処理手順を示すフローチャートである。図23に示すように、オートマトン実行部140bは、現在の状態として、状態D0をセットしステップS201、リスト情報130gに状態D0を追加するステップS202。オートマトン実行部140bは、入力イベント列130fからイベント1つおよびそのプロパティを取り出すステップS203。オートマトン実行部140bは、取り出したイベントおよびプロパティをリスト情報130gに追加するステップS204。オートマトン実行部140bは、決定性状態集合情報130cを参照して、現在の状態Dと、取り出したイベントに基づき遷移後の状態Dを決定しステップS205、リスト情報130gに遷移後の状態Dを追加するステップS206。オートマトン実行部140bは、遷移後の状態Dが、付加アクション情報130eに登録されているか否かを判定するステップS207。オートマトン実行部140bは、遷移後の状態Dが、付加アクション情報130eに登録されていない場合にはステップS207,No、ステップS209に移行する。オートマトン実行部140bは、遷移後の状態Dが、付加アクション情報130eに登録されている場合にはステップS207,Yes、付加アクションを実行するステップS208。オートマトン実行部140bは、入力イベント列終了ではない場合にはステップS209,No、ステップS203に移行する。オートマトン実行部140bは、入力イベント列終了の場合にはステップS209,Yes、リスト情報130gを生成する処理を終了する。オートマトン実行部140bが、図23に示した処理手順に基づいて、リスト情報130gを生成する処理の過程を示す。図24は、オートマトン実行部がリスト情報を生成する処理を説明するための図である。オートマトン実行部140bは、リスト情報130fの位置0に、状態D0を登録する。リスト情報130gのデータ構造は、図24のリスト情報130g1に示すものとなる。オートマトン実行部140bは、入力イベント列130fの先頭のイベントaと、プロパティid=1とを取り出す。オートマトン実行部140bは、状態D0から、イベントaによる遷移先を、決定性状態集合情報130cから判定する。状態D0は、イベントaによって状態D1に遷移する。このため、オートマトン実行部140bは、リスト情報130fの位置1にaid=1を登録する。オートマトン実行部140bは、リスト情報130fの位置2に状態D1を登録する。リスト情報130gのデータ構造は、図24のリスト情報130g2に示すものとなる。オートマトン実行部140bは、入力イベント列130fの2番目のイベントaと、プロパティid=2を取り出す。オートマトン実行部140bは、状態D1から、イベントaによる遷移先を、決定性状態集合情報130cから判定する。状態D1は、イベントaによって状態D3に遷移する。このため、オートマトン実行部140bは、位置3にaid=2を登録する。オートマトン実行部140bは、位置4に状態D3を登録する。リスト情報130gのデータ構造は、図24のリスト情報130g3に示すものとなる。オートマトン実行部140bは、入力イベント列130fの3番目のイベントbと、プロパティid=2を取り出す。オートマトン実行部140bは、状態D3から、イベントbによる遷移先を、決定性状態集合情報130cから判定する。状態D3は、イベントbによって、状態D4に遷移する。このため、オートマトン実行部140bは、位置5にbid=2を登録する。オートマトン実行部140bは、位置6に状態D4を登録する。リスト情報130gのデータ構造は、図24のリスト情報130g4に対応するものとなる。リスト情報130gに登録された状態D4は、付加アクション情報130eに登録された状態である。この場合には、オートマトン実行部140bは、他のスレッドとして、付加アクションを実行する。オートマトン実行部140bが実行する付加アクションについては後述する。オートマトン実行部140bは、付加アクションを他のスレッドで実行しつつ、リスト情報130gを生成する処理を継続して実行する。オートマトン実行部140bは、入力イベント列130fの4番目のイベントbと、プロパティid=1を取り出す。オートマトン実行部140bは、状態D4から、イベントbによる遷移を、決定性状態集合情報130cから判定する。状態D4は、イベントbによって、状態D4に遷移する。このため、オートマトン実行部140bは、位置7にbid=1を登録する。オートマトン実行部140bは、位置8に状態D4を登録する。リスト情報130gのデータ構造は、図24のリスト情報130g5に示すものとなる。リスト情報130gに登録された状態D4は、付加アクション情報130eに登録された状態である。この場合には、オートマトン実行部140bは、他のスレッドとして、付加アクションを実行する。オートマトン実行部140bが実行する付加アクションについては後述する。オートマトン実行部140bは、付加アクションを他のスレッドで実行しつつ、リスト情報130gを生成する処理を継続して実行する。この後、オートマトン実行部140bは、入力イベント列130fから例示しないイベントを無限に受けとる。ここでは説明を省略するが、オートマトン実行部140bは、図23のステップS203に移行し、リスト情報を生成する。次に、リスト情報130gに格納された状態Dが受理状態である場合の処理について説明する。ここで、状態Dが受理状態であることと、状態Dが付加アクション情報130eに登録されていることは、同じことである。以下に示す処理は、上記の付加アクションに対応する処理である。なお参照ポインタ、スタック130h、充足判定情報130i、充足判定対象情報130jは新規作成されるスレッドごとにその格納領域がある。図25は、付加アクションの処理手順を示すフローチャートである。図25に示すように、オートマトン実行部140bは、スタック130h、充足判定情報130i、充足判定対象情報130jを空に設定するステップS301。オートマトン実行部140bは、新規スレッドを作成し、リスト情報130gの末尾を参照ポインタに設定するステップS302。ステップS302において、末尾は、リスト情報130gにおいて、受理状態となる状態Dから最も離れた位置に対応する。オートマトン実行部140bは、参照ポインタの状態Dに対応し、遷移先が受理状態となる非決定性状態集合情報130aの遷移の集合を対応マップ130dから検索するステップS303。オートマトン実行部140bは、検索結果に複数の要素すなわち非決定性状態集合情報130aの遷移が存在する場合には、2要素目以降を処理するためのスレッドを要素毎に作成する。このとき参照ポインタ、スタック130h、充足判定情報130i、充足判定対象情報130jの内容を元のスレッドから新しいスレッドにコピーするステップS304。以降の処理は各スレッドに対してそれぞれ行う処理である。オートマトン実行部140bは、該当要素の遷移先の非決定性状態集合情報130aの状態をスタック130hにプッシュするステップS305。オートマトン実行部140bは、参照ポインタをリスト情報130gの一つ前の状態に移動させステップS306、参照ポインタが指し示す位置を、スタック130hにプッシュするステップS307。オートマトン実行部140bは、状態遷移が遷移条件を伴う場合、すなわち状態遷移の遷移前後の非決定性状態集合情報130aの状態と参照ポインタが指し示す位置のイベント記号の両方がマッチし遷移条件が書かれた行が遷移条件集合情報130bに現れる場合に、その遷移条件を充足判定情報130iに格納し、判定状況を未判定に設定するステップS308。オートマトン実行部140bは、状態遷移が遷移条件に対応する場合、すなわち状態遷移の遷移前後の非決定性状態集合130aの状態と参照ポインタが指し示す位置のイベント記号の両方がマッチしイベント参照記号名が書かれた行が遷移条件集合情報130bに現れる場合に、そのイベント参照記号名と参照ポインタが指し示す位置との組を、充足判定対象情報130jに登録するステップS309。オートマトン実行部140bは、充足判定情報130iに格納された遷移条件を一つ選択し、遷移条件に現れるイベント記号参照名すべてが充足判定対象情報130jに格納されているなら、イベント記号参照名に対応づいたイベントポインタのポイント先を参照してイベントのプロパティの値を取得しそれを遷移条件に代入したうえで遷移条件を充足判定するステップS310。オートマトン実行部140bは、遷移条件の充足判定が行われた結果充足しないことが判明した場合にはステップS311,No、この処理を実行しているスレッドを終了する。なお他のスレッドの処理は継続する。300Aに示す処理ステップS304~318および300Bに示す処理ステップS302~318は、スレッド毎に実行されるものとする。オートマトン実行部140bは、遷移条件を充足するもしくは遷移条件充足判定が行われなかった場合にはステップS311,Yes、充足判定情報130iに格納された遷移条件を全て選択したか否かを判定するステップS312。オートマトン実行部140bは、遷移条件を全て選択していない場合にはステップS312,No、ステップS310に移行する。オートマトン実行部140bは、充足判定情報130iに格納された遷移条件を全て選択した場合にはステップS312,Yes、参照ポインタをリスト情報130gの一つ前の位置に移動するステップS313。オートマトン実行部140bは、参照ポインタの状態Dは初期状態であるか否かを判定するステップS314。オートマトン実行部140bは、参照ポインタの状態Dが初期状態ではない場合にはステップS314,No、状態Dに対応し、かつ、遷移先の状態が、ステップS305の遷移元となる非決定性状態集合情報130aの遷移の集合を対応マップ130dから検索するステップS315。オートマトン実行部140bは、ステップS304に移行する。一方、オートマトン実行部140bは、参照ポインタの状態Dが初期状態の場合にはステップS314,Yes、非決定性状態集合情報130aの初期状態0をスタック130hにプッシュするステップS316。オートマトン実行部140bは、スタック130hに格納されたイベントの内容をスタックボトム側から順にコピーする。ただしスタック130h上でイベント前後の非決定性状態集合情報130aの状態について、スタックボトム側の状態が非決定性状態集合情報130aの20Aの遷移元状態となり逆側の状態が遷移先状態となりかつイベント記号が合致する行が存在してそのイベント種別が検出対象であるイベントのみをコピーする。またスタック130hにはリスト情報130gへのポインタのみが格納されているが、コピーするのはポインタではなくポインタが指し示す先のイベント記号および付随するプロパティの内容であるステップS317。リストを検出したイベント列の一つとして出力し、この処理スレッドを終了するステップS318。ステップS317において、スタックボトムは最初にプッシュされた内容が格納されている側である。なお他のスレッドの処理は継続する。300Aに示す処理ステップS304~318および300Bに示す処理ステップS302~318は、スレッド毎に実行されるものとする。オートマトン実行部140bが、図25に示した処理手順に基づいて、付加アクションを実行する処理について説明する。図26~図32は、オートマトン実行部が付加アクションを実行する処理を説明するための図である。ここでは、オートマトン実行部140bは、リスト情報130gの位置6にて、付加アクションを実行する場合について説明する。図26について説明する。オートマトン実行部140bは、新規スレッドを作成し、参照ポインタを位置6に設定する。参照ポインタ6の状態D4に対応し、遷移先が受理状態となる対応付け前の遷移の集合は{1→2}となる。オートマトン実行部140bは、遷移の集合を、対応マップ130dを基に判定する。オートマトン実行部140bは、遷移先の状態2をスタック130hにプッシュする。また、オートマトン実行部140bは、遷移の集合{1→2}の各要素について個々のスレッドで以降の処理を行うが今回は要素が一つであるためスレッド分岐せずに要素である非決定性状態集合情報130aの遷移1→2についての処理を行う。遷移1→2に対してその遷移先である状態2をスタック130hにプッシュする。オートマトン実行部140bは、参照ポインタをリスト情報130gの一つ前の位置5に移動する。オートマトン実行部140bは、参照ポインタが指し示す位置5をスタック130hにプッシュする。図26のスタック130hでは位置5のイベント内容が何であるか追いやすいように括弧書きでイベント記号とプロパティ値を記してあるが、ここに実際に格納するのは位置5のみである。これは以降の図27から図32でも同様である。また、遷移条件集合情報130bを参照すると、イベントbによる状態1から状態2への遷移は、遷移条件xidyidを伴う。また、遷移条件集合情報130bを参照すると、該当遷移は、遷移条件の充足判定のために記憶しておく必要があり、イベント記号参照名はyとなる。このため、オートマトン実行部140bは、充足判定情報130iに遷移条件xidyidを登録し、判定状況を未判定に設定する。また、オートマトン実行部140bは、充足判定対象情報130jのイベント記号参照名にyを登録し、イベントポインタを位置5に設定する。図26の充足判定対象情報130jでは位置5のイベント内容が何であるか追いやすいように括弧書きでイベント記号とプロパティ値を記してあるが、ここに実際に格納するのは位置5のみである。これは以降の図27から図32でも同様である。オートマトン実行部140bは、参照ポインタをリスト情報130gの一つ前の位置4に移動する。オートマトン実行部140bは、参照ポインタ4の状態D3に対応し、遷移後の状態が状態1となる対応付け前の遷移の集合を判定すると、{0→1、1→1}となる。図27について説明する。ここでは、状態遷移集合{0→1、1→1}の一つの要素である状態遷移0→1に着目する。状態遷移1→1に関しては、別のスレッドにより実行される。オートマトン実行部140bは、遷移先の状態1をスタック130hにプッシュする。また、オートマトン実行部140bは、状態遷移0→1に対してその遷移先である状態1をスタック130hにプッシュする。オートマトン実行部140bは、参照ポインタをリスト情報130gの一つ前の位置3に移動する。オートマトン実行部140bは、参照ポインタが指し示す位置3をスタック130hにプッシュする。また、遷移条件集合情報130bを参照すると、イベントaによる状態0から状態1への遷移は、遷移条件の充足判定のために記憶しておく必要があり、イベント記号参照名はxとなる。このため、オートマトン実行部140bは、充足判定対象情報130jのイベント記号参照名にxを登録し、イベントポインタを位置3に設定する。充足判定に必要な情報が全て充足判定対象情報130jに格納されているので、オートマトン実行部140bは、遷移条件xidyidを充足するか否かを判定する。オートマトン実行部140bは、xidとyidとが等しいので、判定状況を判定済み充足に設定する。オートマトン実行部140bは、参照ポインタをリスト情報130gの一つ前の位置2に移動する。オートマトン実行部140bは、参照ポインタ2の状態D1に対応し、遷移後の状態が状態0となる対応付け前の遷移の集合を判定すると、{0→0}となる。図28について説明する。ここでは、状態遷移集合{0→0}の唯一の要素である状態遷移0→0に着目する。オートマトン実行部140bは、遷移先の状態0をスタック130hにプッシュする。また、オートマトン実行部140bは、状態遷移0→0に対してその遷移先である状態0をスタック130hにプッシュする。オートマトン実行部140bは、参照ポインタをリスト情報130gの一つ前の位置1に移動する。オートマトン実行部140bは、参照ポインタが指し示す位置1をスタック130hにプッシュする。図29について説明する。オートマトン実行部140bは、参照ポインタをリスト情報130gの一つ前の位置0に移動する。オートマトン実行部140bは、参照ポインタ0の状態D0に対応し、遷移後の状態が状態0となる対応付け前の遷移の集合を判定すると{i→0}となる。遷移集合{i→0}の唯一の要素である状態遷移i→0に着目する。オートマトン実行部140bは、遷移先の状態0をスタック130hにプッシュする。オートマトン実行部140bは、非決定性状態集合情報130aのの初期状態0まで達したので、スタック130hに格納されたイベント列を参照し、図2の非決定性状態集合130aで表されるパターンに合致し図3の遷移条件集合情報130bで表される遷移条件を充足したイベント列aid=2、bid=1を出力する。図26~図29に示した処理は、図22に示した状態遷移列60aを検出することに対応する。上記図27以降では、状態遷移集合{0→1、1→1}の一つの要素である状態遷移0→1に着目して、イベント列を抽出する場合について説明した。ここでは、状態遷移0→1に着目したスレッドとは別のスレッドで行われる、もう一つの要素である状態遷移1→1に着目した処理について説明する。なお、参照ポインタ、スタック130h、充足判定情報130i、充足判定対象情報130jは、スレッド毎に格納領域が存在する。これらの情報はスレッド分岐が行われる際に内容がコピーされる。図30について説明する。ここでは、状態遷移1→1に着目する。オートマトン実行部140bは、状態遷移1→1に対してその遷移先である状態1をスタック130hにプッシュする。オートマトン実行部140bは、参照ポインタをリスト情報130gの一つ前の位置3に移動する。オートマトン実行部140bは、参照ポインタが指し示す位置3をスタック130hにプッシュする。オートマトン実行部140bは、参照ポインタをリスト情報130gの一つ前の位置2に移動する。オートマトン実行部140bは、参照ポインタ2の状態D1に対応し、遷移後の状態が状態1となる対応付け前の遷移の集合を判定すると、{0→1}となる。図31について説明する。ここでは状態遷移集合{0→1}の唯一の要素である遷移0→1に着目する。オートマトン実行部140bは、遷移先の状態1をスタック130hにプッシュする。オートマトン実行部140bは、参照ポインタをリスト情報130gの一つ前の位置1に移動する。オートマトン実行部140bは、参照ポインタが指し示す位置1のイベントaとプロパティid=1をスタック130hにプッシュする。また、遷移条件集合情報130bを参照すると、イベントaによる状態0から状態1への遷移は、遷移条件の充足判定のために記憶しておく必要があり、イベント記号参照名はxとなる。このため、オートマトン実行部140bは、充足判定対象情報130jのイベント記号参照名にxを登録し、イベントポインタを位置1に設定する。充足判定に必要な情報が全て充足判定対象情報130jに格納されているので、オートマトン実行部140bは、遷移条件xidyidを充足するか否かを判定する。オートマトン実行部140bは、xidとyidとが異なるので、判定状況を判定済み充足せずに設定する。遷移条件を充足しないので、オートマトン実行部140bは、該当スレッドを終了する。ところで、オートマトン実行部140bは、リスト情報130gの位置8にて、付加アクションを実行すると、非決定性状態集合情報130aのの初期状態0に至るまでの過程において、図32に示すリスト情報130gが生成する。また、充足判定情報130i、充足判定対象情報130jは、図32に示すものとなる。オートマトン実行部140bは、遷移条件xidyidを充足するか否かを判定する。オートマトン実行部140bは、xidとyidとが等しいので、判定状況を判定済み充足に設定する。オートマトン実行部140bは、初期状態0まで達した後、スタック130hに格納されたイベント列を参照し、遷移条件を充足したイベント列aid=1、bid=1を出力する。図32に示した処理は、図22に示した状態遷移列70bを検出することに対応する。オートマトン実行部140bは、上記の処理を実行することで、入力イベント列130fから、図2の非決定性状態集合130aで表されるパターンに合致し図3の遷移条件集合情報130bで表される遷移条件を満たすイベント列aid=2、bid=1、aid=1、bid=1を検出する。オートマトン実行部140bは、検出したイベント列を、出力部120に出力する。オートマトン実行部140bは、図23のステップS207に示したように、リスト情報130gにおいて、遷移後の状態Dが付加アクション情報に登録されていることを検出する度に、新規のスレッドを立てて、並列的に付加アクションを実行する。また、オートマトン実行部140bは、付加アクションを実行する場合に、図25のステップS304に示したように、検索結果に複数の要素が存在する場合には、各要素を処理するためのスレッドを立てて、付加アクションを並列的に実行する。なお、スレッド毎に、参照ポインタ、スタック130h、充足判定情報130i、充足判定対象情報130jの領域がそれぞれ確保されているものとする。次に、本実施例にかかる情報処理装置100の処理手順について説明する。図33は、本実施例にかかる情報処理装置の処理手順を示すフローチャートである。図33に示す処理は、例えば、入力部110から、対応付け指示を受け付けた場合に、処理を開始しても良いし、非決定性状態集合情報130aが記憶部130に格納された場合に、処理を開始してもよい。図33に示すように、情報処理装置100は、対応付け処理を実行しステップS401、オートマトン実行処理を実行するステップS402。ここで、ステップS401に示した対応付け処理は、図12において説明した処理に対応する。また、ステップS402に示したオートマトン実行処理は、図23、図25に示した処理に対応する。次に、本実施例にかかる情報処理装置100の効果について説明する。情報処理装置100は、入力イベント列130fの先頭のイベントから順に、決定性状態集合情報130cと比較して、状態Dを遷移させて、リスト情報130gを生成する。情報処理装置100は、リスト情報130gに、受理状態の状態Dが格納された場合に、各状態Dに対応付けられた状態および遷移前の状態の対応関係から、該当状態Dを起点として、スタック130hを利用し、遷移前の状態を順に辿っていく。情報処理装置100は、状態Dを遷移前の状態に辿っていく過程において、遷移を引き起こしたイベント記号と、イベント記号に対応するプロパティを検出して、遷移条件を充足するか否かを判定し、遷移条件を満たすイベント列を検出する。このような処理を情報処理装置100が実行することで、イベントパターンの照合精度の低下を防止することができる。また、情報処理装置100は、受理状態となる状態Dが複数リスト情報130gに格納されている場合には、状態Dを起点として、並列的に、リスト情報130gを逆順に辿り、遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定する。このように、並列的に処理を実行するので、処理効率を向上させることができる。また、並列的に処理を実行する際に、一般に大きな格納領域を必要とするイベントの記号とプロパティ内容をコピーするのではなく、リスト情報130gに格納された唯一の内容を全ての並列的処理で参照するので、並列的処理にともなう格納領域使用量の増大を抑制することができる。また、情報処理装置100は、状態Dを遷移前の状態に辿っていく過程において、状態Dを、対応付ける前の状態に戻して、遷移状態を逆順に辿り、受理状態に至ったイベント列のイベントの組を判定する。このため、対応付けによる情報損失を無くし、照合精度を向上させることができる。次に、実施例に示した情報処理装置100と同様の機能を実現する情報処理プログラムを実行するコンピュータの一例を説明する。図34は、情報処理プログラムを実行するコンピュータの一例を示す図である。図34に示すように、コンピュータ200は、各種演算処理を実行するCPU201と、ユーザからのデータの入力を受け付ける入力装置202と、ディスプレイ203を有する。また、コンピュータ200は、記憶媒体からプログラム等を読取る読み取り装置204と、ネットワークを介して他のコンピュータとの間でデータの授受を行うインターフェース装置205とを有する。また、コンピュータ200は、各種情報を一時記憶するRAM206と、ハードディスク装置207を有する。そして、各装置201~207は、バス208に接続される。ハードディスク装置207は、例えば、対応付けプログラム207a、オートマトン実行プログラム207bを有する。CPU201は、各プログラム207a、207bを読み出して、RAM206に展開する。対応付けプログラム207aは、対応付けプロセス206aとして機能する。オートマトン実行プログラム207bは、オートマトン実行プロセス206bとして機能する。例えば、対応付けプロセス206aは、図1の対応付け部140aに対応する。オートマトン実行プロセス206bは、図1のオートマトン実行部140bに対応する。なお、各プログラム207a、207dについては、必ずしも最初からハードディスク装置207に記憶させておかなくてもよい。例えば、コンピュータ200に挿入されるフレキシブルディスクFD、CD-ROM、DVDディスク、光磁気ディスク、ICカードなどの可搬用の物理媒体に各プログラムを記憶させておく。そして、コンピュータ500がこれらから各プログラム207a、207bを読み出して実行するようにしてもよい。以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。付記1単一の状態に対応付けられ、所定のイベントおよび遷移条件によって所定の状態に遷移する複数の第1状態を有する第1状態遷移情報と、遷移元の第1状態および遷移先の第1状態と、前記遷移元の第1状態から前記遷移先の第1状態に遷移する場合の遷移条件およびイベントとを対応付けた遷移条件集合情報とを記憶する記憶部と、前記第1状態遷移情報を基にして、複数の第1状態に対応付けられた第2状態を有する第2状態遷移情報を生成し、前記第2状態と、前記第2状態に対応付けられた第1状態および該第1状態に遷移する前の第1状態とを対応付けた対応マップ情報を生成する対応付け部と、継続的に無制限に入力される可能性がありかつ無視すべきイベントが間に入力され、複数のイベントとプロパティとを対応付けた入力イベント列の先頭のイベントから順に、前記第2状態遷移情報と比較して、前記第2状態遷移情報の初期状態から順に第2状態を遷移させ、遷移する度に、遷移した際のイベントおよびプロパティと遷移先の第2状態とを順にリスト情報に格納し、リスト情報に格納された第2状態が受理状態である場合に、該第2状態から前記リスト情報を逆順に辿って、該リスト情報に格納されたイベントおよびプロパティと、第2状態とを抽出し、前記遷移条件集合情報および前記対応マップを基にして、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定するオートマトン実行部とを有することを特徴とする情報処理装置。付記2前記オートマトン実行部は、受理状態となる複数の第2状態がリスト情報に格納されている場合には、各第2状態を起点として、前記リスト情報を逆順に辿り、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定することを特徴とする付記1に記載の情報処理装置。付記3前記オートマトン実行部は、前記遷移条件集合情報および前記対応マップを基にして、前記抽出した第2状態を第1状態に戻して、第1状態による状態遷移を受理状態から逆順に辿り、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定することを特徴とする付記1または2に記載の情報処理装置。付記4コンピュータが実行する情報処理方法であって、前記コンピュータは、単一の状態に対応付けられ、所定のイベントおよび遷移条件によって所定の状態に遷移する複数の第1状態を有する第1状態遷移情報と、遷移元の第1状態および遷移先の第1状態と、前記遷移元の第1状態から前記遷移先の第1状態に遷移する場合の遷移条件およびイベントとを対応付けた遷移条件集合情報とを記憶する記憶装置を有し、前記コンピュータが、前記第1状態遷移情報を基にして、複数の第1状態に対応付けられた第2状態を有する第2状態遷移情報を生成し、前記第2状態と、前記第2状態に対応付けられた第1状態および該第1状態に遷移する前の第1状態とを対応付けた対応マップ情報を生成し、継続的に無制限に入力される可能性がありかつ無視すべきイベントが間に入力され、複数のイベントとプロパティとを対応付けた入力イベント列の先頭のイベントから順に、前記第2状態遷移情報と比較して、前記第2状態遷移情報の初期状態から順に第2状態を遷移させ、遷移する度に、遷移した際のイベントおよびプロパティと遷移先の第2状態とを順にリスト情報に格納し、リスト情報に格納された第2状態が受理状態である場合に、該第2状態から前記リスト情報を逆順に辿って、該リスト情報に格納されたイベントおよびプロパティと、第2状態とを抽出し、前記遷移条件集合情報および前記対応マップを基にして、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定する各処理を実行することを特徴とする情報処理方法。付記5前記イベントの組を判定する処理は、受理状態となる複数の第2状態がリスト情報に格納されている場合には、各第2状態を起点として、前記リスト情報を逆順に辿り、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定することを特徴とする付記4に記載の情報処理方法。付記6前記イベントの組を判定する処理は、前記遷移条件集合情報および前記対応マップを基にして、前記抽出した第2状態を第1状態に戻して、第1状態による状態遷移を受理状態から逆順に辿り、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定することを特徴とする付記4または5に記載の情報処理方法。付記7単一の状態に対応付けられ、所定のイベントおよび遷移条件によって所定の状態に遷移する複数の第1状態を有する第1状態遷移情報と、遷移元の第1状態および遷移先の第1状態と、前記遷移元の第1状態から前記遷移先の第1状態に遷移する場合の遷移条件およびイベントとを対応付けた遷移条件集合情報とを記憶する記憶装置を有するコンピュータに、前記第1状態遷移情報を基にして、複数の第1状態に対応付けられた第2状態を有する第2状態遷移情報を生成し、前記第2状態と、前記第2状態に対応付けられた第1状態および該第1状態に遷移する前の第1状態とを対応付けた対応マップ情報を生成し、継続的に無制限に入力される可能性がありかつ無視すべきイベントが間に入力され、複数のイベントとプロパティとを対応付けた入力イベント列の先頭のイベントから順に、前記第2状態遷移情報と比較して、前記第2状態遷移情報の初期状態から順に第2状態を遷移させ、遷移する度に、遷移した際のイベントおよびプロパティと遷移先の第2状態とを順にリスト情報に格納し、リスト情報に格納された第2状態が受理状態である場合に、該第2状態から前記リスト情報を逆順に辿って、該リスト情報に格納されたイベントおよびプロパティと、第2状態とを抽出し、前記遷移条件集合情報および前記対応マップを基にして、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定する各処理を実行させることを特徴とする情報処理プログラム。付記8前記イベントの組を判定する処理は、受理状態となる複数の第2状態がリスト情報に格納されている場合には、各第2状態を起点として、前記リスト情報を逆順に辿り、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定することを特徴とする付記7に記載の情報処理プログラム。付記9前記イベントの組を判定する処理は、前記遷移条件集合情報および前記対応マップを基にして、前記抽出した第2状態を第1状態に戻して、第1状態による状態遷移を受理状態から逆順に辿り、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定することを特徴とする付記7または8に記載の情報処理プログラム。"