(57)【要約】【課題】パターンの照合精度の低下を防止すること。【解決手段】情報処理装置１００は、入力イベント列１３０ｆの先頭のイベントから順に、決定性状態集合情報１３０ｃと比較して、状態Ｄを遷移させて、リスト情報１３０ｇを生成する。情報処理装置１００は、リスト情報１３０ｇに、受理状態の状態Ｄが格納された場合に、各状態Ｄに対応付けられた状態および遷移前の状態の対応関係から、該当状態Ｄを起点として、スタック１３０ｈを利用し、遷移前の状態を順に辿っていく。情報処理装置１００は、状態Ｄを遷移前の状態に辿っていく過程において、遷移を引き起こしたイベント記号と、イベント記号に対応するプロパティを検出して、遷移条件を充足するか否かを判定し、遷移条件を満たすイベント列を検出する。【選択図】図１
2013092904.tif 000002
【特許請求の範囲】
【請求項１】
単一の状態に対応付けられ、所定のイベントおよび遷移条件によって所定の状態に遷移する複数の第１状態を有する第１状態遷移情報と、遷移元の第１状態および遷移先の第１状態と、前記遷移元の第１状態から前記遷移先の第１状態に遷移する場合の遷移条件およびイベントとを対応付けた遷移条件集合情報とを記憶する記憶部と、
前記第１状態遷移情報を基にして、複数の第１状態に対応付けられた第２状態を有する第２状態遷移情報を生成し、前記第２状態と、前記第２状態に対応付けられた第１状態および該第１状態に遷移する前の第１状態とを対応付けた対応マップ情報を生成する対応付け部と、
継続的に無制限に入力される可能性がありかつ無視すべきイベントが間に入力され、複数のイベントとプロパティとを対応付けた入力イベント列の先頭のイベントから順に、前記第２状態遷移情報と比較して、前記第２状態遷移情報の初期状態から順に第２状態を遷移させ、遷移する度に、遷移した際のイベントおよびプロパティと遷移先の第２状態とを順にリスト情報に格納し、
リスト情報に格納された第２状態が受理状態である場合に、該第２状態から前記リスト情報を逆順に辿って、該リスト情報に格納されたイベントおよびプロパティと、第２状態とを抽出し、前記遷移条件集合情報および前記対応マップを基にして、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定するオートマトン実行部と
を有することを特徴とする情報処理装置。
【請求項２】
前記オートマトン実行部は、受理状態となる複数の第２状態がリスト情報に格納されている場合には、各第２状態を起点として、前記リスト情報を逆順に辿り、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記オートマトン実行部は、前記遷移条件集合情報および前記対応マップを基にして、前記抽出した第２状態を第１状態に戻して、第１状態による状態遷移を受理状態から逆順に辿り、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定することを特徴とする請求項１または２に記載の情報処理装置。
【請求項４】
コンピュータが実行する情報処理方法であって、
前記コンピュータは、単一の状態に対応付けられ、所定のイベントおよび遷移条件によって所定の状態に遷移する複数の第１状態を有する第１状態遷移情報と、遷移元の第１状態および遷移先の第１状態と、前記遷移元の第１状態から前記遷移先の第１状態に遷移する場合の遷移条件およびイベントとを対応付けた遷移条件集合情報とを記憶する記憶装置を有し、
前記コンピュータが、
前記第１状態遷移情報を基にして、複数の第１状態に対応付けられた第２状態を有する第２状態遷移情報を生成し、前記第２状態と、前記第２状態に対応付けられた第１状態および該第１状態に遷移する前の第１状態とを対応付けた対応マップ情報を生成し、
継続的に無制限に入力される可能性がありかつ無視すべきイベントが間に入力され、複数のイベントとプロパティとを対応付けた入力イベント列の先頭のイベントから順に、前記第２状態遷移情報と比較して、前記第２状態遷移情報の初期状態から順に第２状態を遷移させ、遷移する度に、遷移した際のイベントおよびプロパティと遷移先の第２状態とを順にリスト情報に格納し、
リスト情報に格納された第２状態が受理状態である場合に、該第２状態から前記リスト情報を逆順に辿って、該リスト情報に格納されたイベントおよびプロパティと、第２状態とを抽出し、前記遷移条件集合情報および前記対応マップを基にして、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定する
各処理を実行することを特徴とする情報処理方法。
【請求項５】
単一の状態に対応付けられ、所定のイベントおよび遷移条件によって所定の状態に遷移する複数の第１状態を有する第１状態遷移情報と、遷移元の第１状態および遷移先の第１状態と、前記遷移元の第１状態から前記遷移先の第１状態に遷移する場合の遷移条件およびイベントとを対応付けた遷移条件集合情報とを記憶する記憶装置を有するコンピュータに、
前記第１状態遷移情報を基にして、複数の第１状態に対応付けられた第２状態を有する第２状態遷移情報を生成し、前記第２状態と、前記第２状態に対応付けられた第１状態および該第１状態に遷移する前の第１状態とを対応付けた対応マップ情報を生成し、
継続的に無制限に入力される可能性がありかつ無視すべきイベントが間に入力され、複数のイベントとプロパティとを対応付けた入力イベント列の先頭のイベントから順に、前記第２状態遷移情報と比較して、前記第２状態遷移情報の初期状態から順に第２状態を遷移させ、遷移する度に、遷移した際のイベントおよびプロパティと遷移先の第２状態とを順にリスト情報に格納し、
リスト情報に格納された第２状態が受理状態である場合に、該第２状態から前記リスト情報を逆順に辿って、該リスト情報に格納されたイベントおよびプロパティと、第２状態とを抽出し、前記遷移条件集合情報および前記対応マップを基にして、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定する
各処理を実行させることを特徴とする情報処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置等に関する。
【背景技術】
【０００２】
複数種類のイベントが一般には無限に並んだイベント列、例えば「電車駅の改札口をある乗客が通過した」というイベントを全乗客について扱うイベント列に、所定のパターン、例えば「ａというイベントに引き続いてｂというイベントが発生」が含まれ、かつ条件、例えばイベントａ，ｂがともに乗客ＩＤを持つとして「ａ，ｂ両イベントの乗客ＩＤが一致すること」を満足しているか否かを判定する場合に、状態遷移機械が利用される。この状態遷移機械には様々なものが存在する。図３５〜図４０は、従来の状態遷移機械の処理の一例を示す図である。
【０００３】
図３５について説明する。状態遷移機械１０Ａは、所定のパターン、ここでは「ａというイベントに引き続いてｂというイベントが発生」というパターンを受理できるオートマトンである。状態遷移機械１０Ａは、状態０〜２を有する。状態０を初期状態とする。状態２を受理状態とする。状態０はイベントａで状態１に遷移する。状態１はイベントｂで状態２に遷移する。状態遷移機械１０Ａは、イベント列を先頭から順次抽出し、イベントの種別によって状態を遷移させる。状態遷移機械１０Ａは、状態０から状態２まで遷移した場合に、イベント列にイベントａ，ｂのパターンが含まれていると判定する。オートマトンは遷移先の状態が一意に定まる決定性有限オートマトン（DFA：Deterministic  Finite  Automaton）と一意に定まらない非決定性有限オートマトン（NFA：Nondeterministic  Finite  Automaton）に分類でき、後者は前者に変換可能である（非特許文献１などを参照）。状態遷移機械１０Ａはたまたま既にＤＦＡである。
【０００４】
図３６について説明する。状態遷移機械１０Ｂは、状態遷移機械１０Ａを拡張して受理したいパターン中のイベントとは無関係のイベントが前後や間にさしはさまった場合も受理できるように変更したオートマトンである。これはＮＦＡとなっており、非決定的に状態遷移する。状態遷移機械１０Ｂは、状態０〜２を有する。状態０を初期状態とする。状態２を受理状態とする。ここで新たに現れたイベントｃは「ａ、ｂ以外の任意の１イベント」を表すとする。状態０は、イベントｂまたはイベントｃで、再度状態０に遷移する。状態０は、イベントａで状態１に遷移する場合もあれば、状態０に遷移する場合もある。状態１は、イベントａまたはイベントｃで、再度状態１に遷移する。状態１は、イベントｂで状態２に遷移する場合もあれば、状態１に遷移する場合もある。
【０００５】
状態遷移機械１０Ｂには、どんなイベントが到着しても同一の状態にとどまる遷移が加えられている。このような遷移が加えられると一般に遷移先が非決定的となり状態遷移機械は処理効率が悪くなる。このため、状態遷移機械１０Ｂの状態集合を、ＤＦＡの状態に対応付けることで、決定的に遷移させる技術がある。状態遷移機械１０Ｂの状態集合を、ＤＦＡの状態に対応付けると、図３７に示すものとなる。
【０００６】
図３７について説明する。状態遷移機械１０Ｃは、決定的に状態遷移する。状態遷移機械１０Ｃは、状態ｄ０〜ｄ２を有する。状態ｄ０は、図３６の状態０に対応する。状態ｄ１は、図３６の状態０、１に対応する。状態ｄ２は、図３６の状態０、１、２に対応する。状態ｄ０を初期状態とする。状態ｄ２を受理状態とする。状態ｄ０は、イベントａで状態ｄ１に遷移する。状態ｄ０は、イベントｂまたはイベントｃで、状態ｄ０に遷移する。状態ｄ１は、イベントｂで状態ｄ２に遷移する。状態ｄ１は、イベントａまたはイベントｃで、状態ｄ１に遷移する。状態ｄ２は、イベントｂで状態ｄ２に遷移する。状態ｄ２は、イベントａまたはイベントｃで状態ｄ１に遷移する。状態遷移機械１０Ｃは、状態遷移機械１０Ｂと比較して、決定的に状態が遷移するため、処理効率を改善することができる。
【０００７】
図３８について説明する。状態遷移機械１０Ｄは、決定的に状態遷移する。状態遷移機械１０Ｄは、図３５に示した状態遷移機械１０Ａに加えて、遷移条件「x.id==y.id」を有している。図３８に示す例では、「x.id」は、状態０から状態１にイベントａで遷移する場合の、イベントａの「ｉｄ」という名前のプロパティを示す。「y.id」は、状態１から状態２にイベントｂで遷移する場合の、イベントｂのプロパティ「ｉｄ」を示す。イベント列の各イベントには、それぞれプロパティ「ｉｄ」が対応付けられているものとする。
【０００８】
状態遷移機械１０Ｄは、遷移条件によって、状態１から状態２への遷移を制限する。例えば、状態遷移機械１０Ｄは、状態１においてイベントｂが発生し、「x.id」と「y.id」とが一致するならば、状態１を状態２に遷移する。
【０００９】
図３９について説明する。状態遷移機械１０Ｅは、状態遷移機械１０Ｄを拡張して受理したいパターン中のイベントとは無関係のイベントが前後や間にさしはさまった場合も受理できるように変更したオートマトンである。これはＮＦＡとなっており、非決定的に状態遷移する。状態遷移機械１０Ｅは、図３６に示した状態遷移機械１０Ｂに加えて、遷移条件「x.id==y.id」を有している。状態遷移機械１０Ｅは、遷移条件によって、状態１から状態２への遷移を制限する。遷移条件「x.id==y.id」に関する説明は、図３８で説明したものと同様である。
【００１０】
状態遷移機械１０Ｅは、どんなイベントが到着しても同一の状態にとどまる遷移が加えられている。このような遷移が加えられると状態遷移機械は処理効率が悪くなる。上記状態遷移機械１０Ｂの場合と同様にして、状態遷移機械１０Ｅの状態集合を、ＮＦＡの状態に対応付けると、図４０に示すものとなる。
【００１１】
図４０について説明する。状態遷移機械１０Ｆは、決定的に状態遷移する。状態遷移機械１０Ｆは、状態ｄ０〜ｄ２を有する。状態ｄ０は、図３９の状態０に対応する。状態ｄ１は、図３９の状態０、１に対応する。状態ｄ２は、図３９の状態０、１、２に対応する。状態ｄ０を初期状態とする。状態ｄ２を受理状態とする。状態ｄ０は、イベントａで状態ｄ１に遷移する。状態ｄ０は、イベントｂまたはイベントｃで状態ｄ０に遷移する。状態ｄ１は、イベントｂで状態ｄ２に遷移する。状態ｄ１は、イベントａまたはイベントｃで状態ｄ１に遷移する。状態ｄ２は、イベントａまたはイベントｃで状態ｄ１に遷移する。状態ｄ２は、イベントｂで状態ｄ２に遷移する。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特許第４０４７０５３号公報
【非特許文献】
【００１３】
【非特許文献１】A.V.  Aho,  R.  Sethi,  J.D.  Ullman,  “Compilers.  Principles,  Techniques,  and  Tools”,  Addison-Wesley,  1986.  Section  3.6
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかしながら、遷移条件を含む状態遷移機械の状態集合をＮＦＡの状態に対応付けると、パターンの照合精度が低下するという問題があった。
【００１５】
例えば、図３９に示した状態遷移機械１０Ｅの状態集合を、ＮＦＡの状態に対応付け、図４０に示した状態遷移機械１０Ｆとした場合の問題点について説明する。状態遷移機械１０Ｅでは、状態１から状態２にイベントｂによって遷移する場合に、遷移条件「x.id==y.id」を充足するか否かを判定していた。しかし、状態遷移機械１０Ｅでは、状態ｄ１から状態ｄ２にイベントｂで遷移する場合、状態ｄ２から状態ｄ２にイベントｂで遷移する場合のどちらで、遷移条件を充足するか否かを判定すればよいのかが不確定となる。
【００１６】
また、遷移条件の「x.id」に対応するイベントａのプロパティｉｄは、状態ｄ０から状態ｄ１の遷移に対応するものか、状態ｄ１から状態ｄ１の遷移に対応するものか、状態ｄ２から状態ｄ１の遷移に対応するものかが不確定となる。
【００１７】
なお、上記問題を解消するために、遷移条件の遷移に関連する状態集合の一部を、ＮＦＡの状態に対応付けないで利用することも考えられる。しかし、この場合には、イベントの到着ごとに複数の状態遷移を行うため、処理時間やメモリ使用量が増加してしまう。
【００１８】
開示の技術は、上記に鑑みてなされたものであって、パターンの照合精度の低下を防止することができる情報処理装置、情報処理方法および情報処理プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１９】
開示の情報処理装置は、記憶部と対応付け部とオートマトン実行部とを有する。記憶部は、単一の状態に対応付けられ、所定のイベントおよび遷移条件によって所定の状態に遷移する複数の第１状態を有する第１状態遷移情報を記憶する。また、記憶部は、遷移元の第１状態および遷移先の第１状態と、遷移元の第１状態から前記遷移先の第１状態に遷移する場合の遷移条件およびイベントとを対応付けた遷移条件集合情報とを記憶する。対応付け部は、第１状態遷移情報を基にして、複数の第１状態に対応付けられた第２状態を有する第２状態遷移情報を生成する。また、対応付け部は、第２状態と、第２状態に対応付けられた第１状態および該第１状態に遷移する前の第１状態とを対応付けた対応マップ情報を生成する。オートマトン実行部は、継続的に無制限に入力される可能性がありかつ無視すべきイベントが間に入力される入力イベント列の先頭のイベントから順に、第２状態遷移情報と比較して、第２状態遷移情報の初期状態から順に第２状態を遷移させる。そして、オートマトン実行部は、遷移させる度に、遷移した際のイベントおよびプロパティと遷移先の第２状態とを順にリスト情報に格納する。また、オートマトン実行部は、リスト情報に格納された第２状態が受理状態である場合に、該第２状態からリスト情報を逆順に辿って、該リスト情報に格納されたイベントおよびプロパティと、第２状態とを抽出
する。オートマトン実行部は、抽出する過程において、遷移条件集合情報および対応マップを基にして、遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定する。
【発明の効果】
【００２０】
開示の情報処理装置によれば、パターンの照合精度が低下することを防止するという効果を奏する。
【図面の簡単な説明】
【００２１】
【図１】図１は、本実施例にかかる情報処理装置の構成を示す機能ブロック図である。
【図２】図２は、非決定性状態集合情報のデータ構造の一例を示す図である。
【図３】図３は、遷移条件集合情報のデータ構造の一例を示す図である。
【図４】図４は、決定性状態集合情報のデータ構造の一例を示す図である。
【図５】図５は、対応マップのデータ構造の一例を示す図である。
【図６】図６は、付加アクション情報のデータ構造の一例を示す図である。
【図７】図７は、入力イベント列のデータ構造の一例を示す図である。
【図８】図８は、リスト情報のデータ構造の一例を示す図である。
【図９】図９は、スタックのデータ構造の一例を示す図である。
【図１０】図１０は、充足判定情報のデータ構造の一例を示す図である。
【図１１】図１１は、充足判定対象情報のデータ構造の一例を示す図である。
【図１２】図１２は、対応付け部の処理手順を示すフローチャートである。
【図１３】図１３は、対応付け部の処理を説明するための図（１）である。
【図１４】図１４は、対応付け部の処理を説明するための図（２）である。
【図１５】図１５は、対応付け部の処理を説明するための図（３）である。
【図１６】図１６は、対応付け部の処理を説明するための図（４）である。
【図１７】図１７は、対応付け部の処理を説明するための図（５）である。
【図１８】図１８は、対応付け部の処理を説明するための図（６）である。
【図１９】図１９は、対応付け部の処理を説明するための図（７）である。
【図２０】図２０は、オートマトン実行部の処理の概要を説明するための図（１）である。
【図２１】図２１は、オートマトン実行部の処理の概要を説明するための図（２）である。
【図２２】図２２は、オートマトン実行部の処理の概要を説明するための図（３）である。
【図２３】図２３は、リスト情報を生成する処理の処理手順を示すフローチャートである。
【図２４】図２４は、オートマトン実行部がリスト情報を生成する処理を説明するための図である。
【図２５】図２５は、付加アクションの処理手順を示すフローチャートである。
【図２６】図２６は、オートマトン実行部が付加アクションを実行する処理を説明するための図（１）である。
【図２７】図２７は、オートマトン実行部が付加アクションを実行する処理を説明するための図（２）である。
【図２８】図２８は、オートマトン実行部が付加アクションを実行する処理を説明するための図（３）である。
【図２９】図２９は、オートマトン実行部が付加アクションを実行する処理を説明するための図（４）である。
【図３０】図３０は、オートマトン実行部が付加アクションを実行する処理を説明するための図（５）である。
【図３１】図３１は、オートマトン実行部が付加アクションを実行する処理を説明するための図（６）である。
【図３２】図３２は、オートマトン実行部が付加アクションを実行する処理を説明するための図（７）である。
【図３３】図３３は、本実施例にかかる情報処理装置の処理手順を示すフローチャートである。
【図３４】図３４は、情報処理プログラムを実行するコンピュータの一例を示す図である。
【図３５】図３５は、従来の状態遷移機械の処理の一例を示す図（１）である。
【図３６】図３６は、従来の状態遷移機械の処理の一例を示す図（２）である。
【図３７】図３７は、従来の状態遷移機械の処理の一例を示す図（３）である。
【図３８】図３８は、従来の状態遷移機械の処理の一例を示す図（４）である。
【図３９】図３９は、従来の状態遷移機械の処理の一例を示す図（５）である。
【図４０】図４０は、従来の状態遷移機械の処理の一例を示す図（６）である。
【発明を実施するための形態】
【００２２】
以下に、本願の開示する情報処理装置、情報処理方法および情報処理プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例】
【００２３】
本実施例にかかる情報処理装置の構成の一例について説明する。図１は、本実施例にかかる情報処理装置の構成を示す機能ブロック図である。図１に示すように、情報処理装置１００は、入力部１１０、出力部１２０、記憶部１３０、制御部１４０を有する。
【００２４】
入力部１１０は、各種の情報を情報処理装置１００に入力する入力装置である。例えば、利用者は、入力部１１０を操作して、後述する入力イベント列１３０ｆを入力する。入力部１１０は、キーボードやマウス、タッチパネル等に対応する。なお、入力部１１０は、他の装置から情報を受け付け、受け付けた情報を情報処理装置１００に入力する入力装置であってもよい。
【００２５】
出力部１２０は、制御部１４０の処理結果を出力する装置である。出力部１２０は、ディスプレイ等の表示装置に対応する。なお、出力部１２０は、他の装置に情報を出力する出力装置であってもよい。
【００２６】
記憶部１３０は、非決定性状態集合情報１３０ａ、遷移条件集合情報１３０ｂ、決定性状態集合情報１３０ｃ、対応マップ１３０ｄ、付加アクション情報１３０ｅ、入力イベント列１３０ｆを記憶する。また、記憶部１３０は、リスト情報１３０ｇ、スタック１３０ｈ、充足判定情報１３０ｉ、充足判定対象情報１３０ｊを記憶する。記憶部１３０は、例えば、ＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read  Only  Memory）、フラッシュメモリ（Flash  Memory）などの半導体メモリ素子、またはハードディスク、光ディスクなどの記憶装置に対応する。
【００２７】
非決定性状態集合情報１３０ａは、図３６に示した状態遷移機械１０Ｂに対応する非決定性有限オートマトンである。非決定性状態集合情報１３０ａは、非決定的に状態遷移する。非決定性状態集合情報１３０ａは、例えば、第１状態遷移情報に対応する。
【００２８】
図２は、非決定性状態集合情報のデータ構造の一例を示す図である。図２に示すように、非決定性状態集合情報１３０ａは、テーブル２０Ａ〜２０Ｃを有する。テーブル２０Ａは、遷移元状態と、イベント記号と、遷移先状態と、イベント種別とを対応付ける。このうち、イベント種別は、該当する遷移を引き起こしたイベントと該イベントのプロパティをパターン・条件に合致するイベント列検出時に検出結果として出力するか否かを示す情報である。スキップの場合には、イベントと該イベントのプロパティｉｄの検出結果の一部としてそのイベントを出力しない。検出対象の場合には、イベント記号と該イベントのプロパティｉｄの検出結果の一部としてそのイベントを出力する。なお、この実施例ではイベントがｉｄという名前のプロパティのみを持つ場合で説明しているが、一般にはイベントは複数種類のプロパティを持つ。
【００２９】
テーブル２０Ａの１段目では、イベント「ａ」によって、状態０から状態０に遷移することを示す。この場合には、イベント種別が「スキップ」であるため、イベントａと、このイベントａのプロパティの出力は行われない。
【００３０】
テーブル２０Ａの４段目では、イベント「ａ」によって、状態０から状態１に遷移することを示す。この場合には、イベント種別が「検出対象」であるため、イベントａと、このイベントａのプロパティｉｄの出力が行われる。
【００３１】
テーブル２０Ｂは、初期状態を示す情報を格納する。図２に示す例では、初期状態は状態「０」となっている。このため、状態０から状態遷移が開始される。
【００３２】
テーブル２０Ｃは、受理状態を示す情報を格納する。図２に示す例では、受理状態は状態「２」となっている。このため、状態２に到達した場合に、所定のパターンが照合されたことになる。なお、受理状態は２つ以上ある場合がある。
【００３３】
遷移条件集合情報１３０ａは、遷移元の状態および遷移先の状態と、遷移元の状態から遷移先の状態に遷移する場合の遷移条件およびイベントを対応付けた情報である。図３は、遷移条件集合情報のデータ構造の一例を示す図である。
【００３４】
図３に示すように、遷移条件集合情報１３０ｂは、遷移元状態と、遷移先状態と、イベント記号と、イベント記号参照名と、遷移条件とを対応付ける。
【００３５】
このうち、イベント記号参照名は、イベント記号とイベント記号に対応するプロパティｉｄと対応付ける参照名である。図３の１段目では、イベント「ａ」によって、状態０から状態１に遷移した場合に、イベント「ａ」とイベント「ａ」のプロパティｉｄを、イベント記号参照名「x」と対応付ける。
【００３６】
遷移条件は、ある状態をある状態に遷移する場合の条件である。例えば、図３の２段目では、遷移条件「x.id==y.id」を満たす場合に、イベント「ｂ」によって状態１から状態２に遷移することを示す。遷移条件「x.id==y.id」の意味は、状態０から状態１に遷移したイベント「ａ」のプロパティｉｄと、状態１から状態２に遷移したイベント「ｂ」のプロパティｉｄが等しいというものである。
【００３７】
決定性状態集合情報１３０ｃは、非決定性状態集合情報１３０ａを、ＤＦＡの状態に対応付けた状態集合情報である。本実施例では、非決定性状態集合情報１３０ａの状態と、決定性状態集合情報１３０ｃの状態とを区別するために、決定性状態集合情報１３０ｃの状態を状態Ｄとする。状態Ｄは、非決定性状態集合１３０ａの複数の状態に対応付けられる。決定性状態集合情報１３０ｃは、第２状態遷移情報に対応する。
【００３８】
図４は、決定性状態集合情報のデータ構造の一例を示す図である。図４に示すように、決定性状態集合情報１３０ｃは、状態Ｄがどのイベントによって、どの状態Ｄに遷移するのかを示す情報を有する。例えば、図４の１段目では、状態Ｄ０は、イベントａにより状態Ｄ１に遷移する。状態Ｄ０は、イベントｂにより状態Ｄ２に遷移する。状態Ｄ０は、イベントｃにより状態Ｄ２に遷移する。また、決定性状態集合情報１３０ｃには、初期状態がどの状態Ｄであるのかが登録されている。図４に示す例では初期状態３０Ｂは、「状態Ｄ０」となる。
【００３９】
対応マップ１３０ｄは、状態Ｄと、状態Ｄに対応付けられた状態および該状態に遷移する前の状態とを対応付けた情報である。図５は、対応マップのデータ構造の一例を示す図である。
【００４０】
図５に示すように、対応マップ１３０ｄは、状態と、対応情報とを対応付ける。対応情報において、矢印の先が、状態Ｄに対応する状態を示す。また、矢印の前は、遷移前の状態を示す。例えば、状態Ｄ１の対応情報は｛０→０、０→１｝となっている。このため、状態Ｄ１に対応する状態は、状態０と状態１である。また、状態０の遷移前の状態は状態０であり、状態１の遷移前の状態は０であることを示す。なお、状態Ｄ０の対応情報に含まれる「ｉ」は、初期状態に遷移する前の状態として付加した状態を示す（ｉはイベントの入力なしで状態０に遷移（ε遷移）する）。状態「ｉ」は初期状態を含めて同じ手順で処理を行えるよう付加した仮想的な状態である。
【００４１】
付加アクション情報１３０ｅは、受理状態となる状態Ｄを記憶し、該状態Ｄによって付加アクションを実行することを示す情報である。図６は、付加アクション情報のデータ構造の一例を示す図である。付加アクションに関する説明は後述する。
【００４２】
入力イベント列１３０ｆは、一連のイベントを含む情報である。入力イベント列１３０ｆは、イベント記号とプロパティｉｄとを対応付ける。図７は、入力イベント列のデータ構造の一例を示す図である。図７に示すイベント列は、左端のイベントが先頭のイベントであり、左側から右側に向かってイベントが並んでいるものとする。具体的には、イベント列は、イベントａ、ａ、ｂ、ｂを含み、最初の４つのイベントの各プロパティｉｄはそれぞれ、１、２、２、１となる。
【００４３】
リスト情報１３０ｇは、入力イベント列１３０ｆにより遷移する決定性状態集合情報１３０ｃの状態Ｄと、該状態Ｄに遷移した際のイベントおよびプロパティｉｄとを順に記憶する情報である。図８は、リスト情報のデータ構造の一例を示す図である。図８に示すように、リスト情報は、位置と状態／イベントを含む。位置は、リスト情報１３０ｇ上の位置を一意に識別する情報であり、状態／イベントには、状態Ｄまたはイベントおよびプロパティｉｄが格納される。リスト情報１３０ｇが生成される過程の説明は後述する。
【００４４】
スタック１３０ｈは、状態またはリスト情報の位置を順次記憶するスタックである。図９は、スタックのデータ構造の一例を示す図である。図９に示すように、スタック１３０ｈは、状態またはイベントポインタを順次記憶する。イベントポインタは、リスト情報上の位置に対応するものである。スタック１３０ｈに情報が格納される過程の説明は後述する。
【００４５】
充足判定情報１３０ｉは、遷移条件が充足したか否かの情報を含む。図１０は、充足判定情報のデータ構造の一例を示す図である。図１０に示すように、充足判定情報１３０ｉは、遷移条件と判定状況とを対応付ける。判定状況は、遷移条件を充足したか否かの情報を示す。
【００４６】
充足判定対象情報１３０ｊ、遷移条件を判定する場合のイベント記号参照名の場所を指定する情報である。図１１は、充足判定対象情報のデータ構造の一例を示す図である。図１１に示すように、充足判定対象情報１３０ｊ、イベント記号参照名と、イベントポインタとを対応付ける。図１１に示す例では、イベント記号参照名「x」の情報は、リスト情報１３０ｇの位置「＠１」に格納されていることを示す。イベント記号参照名「y」の情報は、リスト情報１３０ｇの位置「＠７」に格納されていることを示す。
【００４７】
後述の制御部１４０が、遷移条件「x.id==y.id」を満たしているか否かを判定する時点で、充足判定対象情報のデータが、図１１に示すものであれば、リスト情報１３０ｇの位置「＠１」の情報と「＠７」の情報が比較される。
【００４８】
制御部１４０は、対応付け部１４０ａと、オートマトン実行部１４０ｂとを有する。制御部１４０は、例えば、ＡＳＩＣ（Application  Specific  Integrated  Circuit）や、ＦＰＧＡ（Field  Programmable  Gate  Array）などの集積装置に対応する。また、制御部１４０は、例えば、ＣＰＵやＭＰＵ（Micro  Processing  Unit）等の電子回路に対応する。
【００４９】
対応付け部１４０ａは、非決定性状態集合情報１３０ａを基にして、決定性状態集合情報１３０ｃと、対応マップ１３０ｄと、付加アクション情報１３０ｅを生成する処理部である。
【００５０】
対応付け部１４０ａは、非決定性状態集合情報１３０ａの複数の状態を、単一の状態Ｄに対応付けることで、決定性状態集合情報１３０ｃを生成する。対応付け部１４０ａは、状態Ｄに対応付けられた状態の、所定のイベントによる遷移元と遷移先の関係から、対応マップ１３０ｄを生成する。また、対応付け部１４０ａは、受理状態となる状態を含む状態Ｄに対応して、付加アクション情報１３０ｅを生成する。
【００５１】
ここで、対応付け部１４０ａの処理手順の一例について説明する。図１２は、対応付け部の処理手順を示すフローチャートである。図１２に示す処理は、例えば、入力部１１０から、対応付け指示を受け付けた場合に、処理を開始しても良いし、非決定性状態集合情報１３０ａが記憶部１３０に格納された場合に、処理を開始してもよい。なお、図１２に記載する対処待ち集合、一時格納テーブルは、例えば、対応付け部１４０ａが保持するものとする。
【００５２】
図１２に示すように、対応付け部１４０ａは、対処待ち集合に初期状態Ｄ０をセットし、状態Ｄ０を初期状態として、決定性状態集合情報１３０ｃの初期状態３０Ｂに登録する（ステップＳ１０１）。対応付け部１４０ａは、対応マップ１３０ｄにＤ０と｛ｉ→１｝とを登録する（ステップＳ１０２）。
【００５３】
対応付け部１４０ａは、対応待ち集合から一つの状態を取り出す（ステップＳ１０３）。対応付け部１４０ａは、状態Ｄに対応する、対応付け前の遷移の遷移先の状態をリストアップする（ステップＳ１０４）。対応付け部１４０ａは、全イベント記号の集合の中から未選択のイベント記号（イベント記号ｅと呼ぶ）を一つ選択し（ステップＳ１０５）、一時格納テーブルを空に設定する（ステップＳ１０６）。
【００５４】
対応付け部１４０ａは、リストアップした状態の中から未選択の状態ｓを一つ選択する（ステップＳ１０７）。対応付け部１４０ａは、遷移元の状態がｓであり、イベント記号ｅによる遷移を非決定性状態集合情報１３０ａからリストアップする（ステップＳ１０８）。
【００５５】
対応付け部１４０ａは、リストアップした遷移群を、一時格納テーブルに格納する（ステップＳ１０９）。対応付け部１４０ａは、状態ｓを全て選択したか否かを判定する（ステップＳ１１０）。対応付け部１４０ａは、状態ｓを全て選択していない場合には（ステップＳ１１０，Ｎｏ）、ステップＳ１０７に移行する。
【００５６】
対応付け部１４０ａは、状態ｓを全て選択した場合には（ステップＳ１１０，Ｙｅｓ）、一時格納テーブルの遷移群が、状態Ｄ’と既に対応付いているか否かを判定する（ステップＳ１１１）。ここで、状態Ｄ’は、一時格納テーブルの遷移と対応付けられた状態Ｄに対応するものである。
【００５７】
対応付け部１４０ａは、一時格納テーブルの遷移群が、状態Ｄ’と既に対応付いている場合には（ステップＳ１１１，Ｙｅｓ）、ステップＳ１１５に移行する。一方、対応付け部１４０ａは、一時格納テーブルの遷移群が、状態Ｄ’と既に対応付いていない場合には（ステップＳ１１１，Ｎｏ）、新規の状態Ｄ’を作成し、リストアップした遷移群と対応付ける（ステップＳ１１２）。
【００５８】
対応付け部１４０ａは、新規の状態Ｄ’を処理待ち集合に追加する（ステップＳ１１３）。対応付け部１４０ａは、新規の状態Ｄ’が受理状態の場合には、状態Ｄ’を付加アクション情報１３０ｅに登録する（ステップＳ１１４）。
【００５９】
対応付け部１４０ａは、イベント記号ａをトリガとする状態Ｄから状態Ｄ’への遷移を決定性状態集合情報１３０ｃに登録する（ステップＳ１１５）。ステップＳ１１５のイベント記号ａは、ステップＳ１０５で選択したイベント記号である。
【００６０】
対応付け部１４０ａは、イベント記号を全て選択したか否かを判定する。対応付け部１４０ａは、イベント記号を全て選択していない場合には（ステップＳ１１６，Ｎｏ）、ステップＳ１０５に移行する。一方、対応付け部１４０ａは、イベント記号を全て選択した場合には（ステップＳ１１６，Ｙｅｓ）、対処待ち集合か空であるか否かを判定する（ステップＳ１１７）。
【００６１】
対応付け部１４０ａは、対処待ち集合が空ではない場合には（ステップＳ１１７，Ｎｏ）ステップＳ１０３に移行する。一方、対応付け部１４０ａは、対処待ち集合が空の場合には（ステップＳ１１７，Ｙｅｓ）、処理を終了する。
【００６２】
次に、対応付け部１４０ａが、図１２に示した処理手順に基づいて、決定性状態集合情報１３０ｃと、対応マップ１３０ｄと、付加アクション情報１３０ｅを生成する過程を示す。図１３〜図１９は、対応付け部の処理を説明するための図である。
【００６３】
図１３について説明する。対応付け部１４０ａは、対応マップ１３０ｄの状態にＤ０を登録し、対応情報に｛ｉ→０｝を登録する。また、対処待ち集合５０Ａに状態Ｄ０を登録する。なお、対処待ち集合５０Ａは、対応付け部１４０ａが保持しているものとする。また、状態Ｄ０は、状態ｉから遷移する状態０に対応する。
【００６４】
図１４について説明する。対応付け部１４０ａは、対応待ち集合５０Ａから状態Ｄ０を取り出す。対応付け部１４０ａは、状態Ｄ０に対応する状態０から、イベントａによって遷移する状態を、非決定性状態集合情報１３０ａを基に判定すると、状態０、状態１となる。このため、対応付け部１４０ａは、対応情報に｛０→０，０→１｝と、新たな状態Ｄ１とを対応マップ１３０ｄに登録する。対応付け部１４０ａは、状態Ｄ１を対処待ち集合５０Ａに登録する。対応付け部１４０ａは、状態Ｄ０が、イベントａによって、状態Ｄ１に遷移する旨を、決定性状態集合情報１３０ｃに登録する。
【００６５】
図１４において、対応情報の矢印の先が、状態Ｄに対応する状態であり、矢印の先の反対側は、遷移前の状態を示す。例えば、状態Ｄ０は、状態０、１に対応付けられており、遷移前の状態は、状態０である。
【００６６】
対応付け部１４０ａは、状態Ｄ０に対応する状態０から、イベントｂによって遷移する状態を、非決定性状態集合情報１３０ａを基に判定すると、状態０となる。このため、対応付け部１４０ａは、対応情報に｛０→０｝と、新たな状態Ｄ２とを対応マップ１３０ｄに登録する。対応付け部１４０ａは、状態Ｄ２を対処待ち集合５０Ａに登録する。対応付け部１４０ａは、状態Ｄ０が、イベントｂによって、状態Ｄ２に遷移する旨を、決定性状態集合情報１３０ｃに登録する。
【００６７】
対応付け部１４０ａは、状態Ｄ０に対応する状態０から、イベントｃによって遷移する状態を、非決定性状態集合情報１３０ａを基に判定すると、状態０となる。この遷移元の状態と遷移先の状態は、状態Ｄ２の対応情報に対応するため、対応付け部１４０ａは、新たな情報を、対応マップ１３０ｄに登録しない。対応付け部１４０ａは、状態Ｄ０が、イベントｃによって、状態Ｄ２に遷移する旨を、決定性状態集合情報１３０ｃに登録する。
【００６８】
図１５について説明する。対応付け部１４０ａは、対応待ち集合５０Ａから状態Ｄ１を取り出す。対応付け部１４０ａは、状態Ｄ１に対応する状態０、状態１から、イベントａによって遷移する状態を、非決定性状態集合情報１３０ａを基に判定する。遷移元を状態０とすると、イベントａにより、状態０と状態１に遷移する。また、遷移元を状態１とすると、イベントａにより、状態１に遷移する。このため、対応付け部１４０ａは、対応情報に｛０→０，０→１，１→１｝と、新たな状態Ｄ３とを対応マップ１３０ｄに登録する。対応付け部１４０ａは、状態Ｄ３を対処待ち集合５０Ａに登録する。対応付け部１４０ａは、状態Ｄ１が、イベントａによって、状態Ｄ３に遷移する旨を、決定性状態集合情報１３０ｃに登録する。
【００６９】
対応付け部１４０ａは、状態Ｄ１に対応する状態０、状態１から、イベントｂによって遷移する状態を、非決定性状態集合情報１３０ａを基に判定する。遷移元を状態０とすると、イベントｂにより、状態０に遷移する。また、遷移元を状態１とすると、イベントｂにより、状態１、状態２に遷移する。このため、対応付け部１４０ａは、対応情報に｛０→０，１→１，１→２｝と、新たな状態Ｄ４とを対応マップ１３０ｄに登録する。対応付け部１４０ａは、状態Ｄ４を対処待ち集合５０Ａに登録する。対応付け部１４０ａは、状態Ｄ１が、イベントｂによって、状態Ｄ４に遷移する旨を、決定性状態集合情報１３０ｃに登録する。
【００７０】
対応付け部１４０ａは、状態Ｄ１に対応する状態０、状態１から、イベントｃによって遷移する状態を、非決定性状態集合情報１３０ａを基に判定する。遷移元を状態０とすると、イベントｃにより、状態０に遷移する。また、遷移元を状態１とすると、イベントｃにより、状態１に遷移する。このため、対応付け部１４０ａは、対応情報に｛０→０，１→１｝と、新たな状態Ｄ５とを対応付けマップ１３０ｄに登録する。対応付け部１４０ａは、状態Ｄ５を対処待ち集合５０Ａに登録する。対応付け部１４０ａは、状態Ｄ１が、イベントｃによって、状態Ｄ５に遷移する旨を、決定性状態集合情報１３０ｃに登録する。
【００７１】
図１６について説明する。対応付け部１４０ａは、対応待ち集合５０Ａから状態Ｄ２を取り出す。対応付け部１４０ａは、状態Ｄ２に対応する状態０から、イベントａによって遷移する状態を、非決定性状態集合情報１３０ａを基に判定する。状態０は、イベントａによって、状態０、状態１に遷移する。この遷移元の状態と遷移先の状態は、状態Ｄ１の対応情報に対応するため、対応付け部１４０ａは、新たな情報を、対応マップ１３０ｄに登録しない。対応付け部１４０ａは、状態Ｄ２が、イベントａによって、状態Ｄ１に遷移する旨を、決定性状態集合情報１３０ｃに登録する。
【００７２】
対応付け部１４０ａは、状態Ｄ２に対応する状態０から、イベントｂによって遷移する状態を、非決定性状態集合情報１３０ａを基に判定する。状態０は、イベントｂによって、状態０に遷移する。この遷移元の状態と遷移先の状態は、状態Ｄ２の対応情報に対応するため、対応付け部１４０ａは、新たな情報を、対応マップ１３０ｄに登録しない。対応付け部１４０ａは、状態Ｄ２が、イベントｂによって、状態Ｄ２に遷移する旨を、決定性状態集合情報１３０ｃに登録する。
【００７３】
対応付け部１４０ａは、状態Ｄ２に対応する状態０から、イベントｃによって遷移する状態を、非決定性状態集合情報１３０ａを基に判定する。状態０は、イベントｃによって、状態０に遷移する。この遷移元の状態と遷移先の状態は、状態Ｄ２の対応情報に対応するため、対応付け部１４０ａは、新たな情報を、対応マップ１３０ｄに登録しない。対応付け部１４０ａは、状態Ｄ２が、イベントｃによって、状態Ｄ２に遷移する旨を、決定性状態集合情報１３０ｃに登録する。
【００７４】
図１７について説明する。対応付け部１４０ａは、対応待ち集合５０Ａから状態Ｄ３を取り出す。対応付け部１４０ａは、状態Ｄ３に対応する状態０、状態１から、イベントａによって遷移する状態を、非決定性状態集合情報１３０ａを基に判定する。遷移元を状態０とすると、イベントａにより、状態０と状態１に遷移する。また、遷移元を状態１とすると、イベントａにより、状態１に遷移する。この遷移元の状態と遷移先の状態は、状態Ｄ３の対応情報に対応するため、対応付け部１４０ａは、新たな情報を、対応マップ１３０ｄに登録しない。対応付け部１４０ａは、状態Ｄ３が、イベントａによって、状態Ｄ３に遷移する旨を、決定性状態集合情報１３０ｃに登録する。
【００７５】
対応付け部１４０ａは、状態Ｄ３に対応する状態０、状態１から、イベントｂによって遷移する状態を、非決定性状態集合情報１３０ａを基に判定する。遷移元を状態０とすると、イベントｂにより、状態０に遷移する。また、遷移元を状態１とすると、イベントｂにより、状態１、状態２に遷移する。この遷移元の状態と遷移先の状態は、状態Ｄ４の対応情報に対応するため、対応付け部１４０ａは、新たな情報を、対応マップ１３０ｄに登録しない。対応付け部１４０ａは、状態Ｄ３が、イベントｂによって、状態Ｄ４に遷移する旨を、決定性状態集合情報１３０ｃに登録する。
【００７６】
対応付け部１４０ａは、状態Ｄ３に対応する状態０、状態１から、イベントｃによって遷移する状態を、非決定性状態集合情報１３０ａを基に判定する。遷移元を状態０とすると、イベントｃにより、状態０に遷移する。また、遷移元を状態１とすると、イベントｃにより、状態１に遷移する。この遷移元の状態と遷移先の状態は、状態Ｄ５の対応情報に対応するため、対応付け部１４０ａは、新たな情報を、対応マップ１３０ｄに登録しない。対応付け部１４０ａは、状態Ｄ３が、イベントｃによって、状態Ｄ５に遷移する旨を、決定性状態集合情報１３０ｃに登録する。
【００７７】
図１８について説明する。対応付け部１４０ａは、対応待ち集合５０Ａから状態Ｄ４を取り出す。この状態Ｄ４は、対応マップ１３０ｄを参照すると、状態０、１、２に対応付けられている。状態２は、非決定性状態集合情報１３０ａにより受理状態である。対応付け部１４０ａは、状態Ｄ４を、付加アクション情報１３０ｅに登録する。
【００７８】
対応付け部１４０ａは、状態Ｄ４に対応する状態０、１、２のうち、状態０、１からイベントａによって遷移する状態を、非決定性状態集合情報１３０ａを基に判定する。状態２は受理状態であるため、スキップする。遷移元を状態０とすると、イベントａにより、状態０、状態１に遷移する。また、遷移元を状態１とすると、イベントａにより、状態１に遷移する。この遷移元の状態と遷移先の状態は、状態Ｄ３に対応するため、対応付け部１４０ａは、新たな情報を、対応マップ１３０ｄに登録しない。対応付け部１４０ａは、状態Ｄ４が、イベントａによって、状態Ｄ３に遷移する旨を、決定性状態集合情報１３０ｃに登録する。
【００７９】
対応付け部１４０ａは、状態Ｄ４に対応する状態０、１、２のうち、状態０、１からイベントｂによって遷移する状態を、非決定性状態集合情報１３０ａを基に判定する。遷移元を状態０とすると、イベントｂにより、状態０に遷移する。また、遷移元を状態１とすると、イベントｂにより、状態１、状態２に遷移する。この遷移元の状態と遷移先の状態は、状態Ｄ４に対応するため、対応付け部１４０ａは、新たな情報を、対応マップ１３０ｄに登録しない。対応付け部１４０ａは、状態Ｄ４が、イベントｂによって、状態Ｄ４に遷移する旨を、決定性状態集合情報１３０ｃに登録する。
【００８０】
対応付け部１４０ａは、状態Ｄ４に対応する状態０、１、２のうち、状態０、１からイベントｃによって遷移する状態を、非決定性状態集合情報１３０ａを基に判定する。遷移元を状態０とすると、イベントｃにより、状態０に遷移する。また、遷移元を状態１とすると、イベントｃにより、状態１に遷移する。この遷移元の状態と遷移先の状態は、状態Ｄ５に対応するため、対応付け部１４０ａは、新たな情報を、対応マップ１３０ｄに登録しない。対応付け部１４０ａは、状態Ｄ４が、イベントｃによって、状態Ｄ５に遷移する旨を、決定性状態集合情報１３０ｃに登録する。
【００８１】
図１９について説明する。対応付け部１４０ａは、対応待ち集合５０Ａから状態Ｄ５を取り出す。対応付け部１４０ａは、状態Ｄ５に対応する状態０、状態１から、イベントａによって遷移する状態を、非決定性状態集合情報１３０ａを基に判定する。遷移元を状態０とすると、イベントａにより、状態０、状態１に遷移する。また、遷移元を状態１とすると、イベントａにより、状態１に遷移する。この遷移元の状態と遷移先の状態は、状態Ｄ３に対応するため、対応付け部１４０ａは、新たな情報を、対応マップ１３０ｄに登録しない。対応付け部１４０ａは、状態Ｄ５が、イベントａによって、状態Ｄ３に遷移する旨を、決定性状態集合情報１３０ｃに登録する。
【００８２】
対応付け部１４０ａは、状態Ｄ５に対応する状態０、状態１から、イベントｂによって遷移する状態を、非決定性状態集合情報１３０ａを基に判定する。遷移元を状態０とすると、イベントｂにより、状態０に遷移する。また、遷移元を状態１とすると、イベントｂにより、状態１、状態２に遷移する。この遷移元の状態と遷移先の状態は、状態Ｄ４に対応するため、対応付け部１４０ａは、新たな情報を、対応マップ１３０ｄに登録しない。対応付け部１４０ａは、状態Ｄ５が、イベントａによって、状態Ｄ４に遷移する旨を、決定性状態集合情報１３０ｃに登録する。
【００８３】
対応付け部１４０ａは、状態Ｄ５に対応する状態０、状態１から、イベントｃによって遷移する状態を、非決定性状態集合情報１３０ａを基に判定する。遷移元を状態０とすると、イベントｃにより、状態０に遷移する。また、遷移元を状態１とすると、イベントｃにより、状態１に遷移する。この遷移元の状態と遷移先の状態は、状態Ｄ５に対応するため、対応付け部１４０ａは、新たな情報を、対応マップ１３０ｄに登録しない。対応付け部１４０ａは、状態Ｄ５が、イベントｃによって、状態Ｄ５に遷移する旨を、決定性状態集合情報１３０ｃに登録する。
【００８４】
図１９に示す処理が終わった時点で、処理待ち集合５０Ａが空になるため、対応付け部１４０ａは、処理を終了する。上記のように、図１３〜図１９に示す処理を、対応付け部１４０ａが実行することで、決定性状態集合情報１３０ｃ、対応マップ１３０ｄ、付加アクション情報１３０ｅが生成される。
【００８５】
図１の説明に戻る。オートマトン実行部１４０ｂは、遷移条件を充足しつつ、受理状態に至るイベントの組を判定する処理部である。図２０〜図２２は、オートマトン実行部の処理の概要を説明するための図である。
【００８６】
オートマトン実行部１４０ｂは、入力イベント列１３０ｆの先頭のイベントから順に、決定性状態集合情報１３０ｃと比較して、状態Ｄを遷移させる。一例として、入力イベント列１３０ｆを、図７に示すように、ａ、ａ、ｂ、ｂ、で始まる無限の列とし、最初の４つの各イベントのプロパティｉｄをそれぞれ１、２、２、１とする。この場合には、図２０に示すように、状態Ｄは、初期状態Ｄ０、状態Ｄ１、状態Ｄ３、状態Ｄ４、状態Ｄ４の順に遷移する。なお、各状態Ｄは、対応情報に対応付けられている。対応情報は、図５等に示したものである。
【００８７】
オートマトン実行部１４０ｂは、受理状態を含む状態Ｄを特定する。オートマトン実行部１４０ｂは、特定した状態Ｄの受理状態を起点として、遷移前の状態を辿っていく。また、オートマトン実行部１４０ｂは、状態を辿っていく際に、非決定性状態集合情報１３０ａを基にして、検出対象となる遷移を特定する。検出対象となる遷移では、遷移を引き起こしたイベント記号と、イベント記号に対応するプロパティｉｄを検出する。
【００８８】
図２０に示した先頭から４番目のＤ４は、受理状態を含む状態Ｄである。オートマトン実行部１４０ｂは、４番目の状態Ｄ４の受理状態２を起点として、遷移前の状態を辿っていくと、図２１の６０に示す状態遷移列となる。図２０に示した先頭から５番目のＤ４は、受理状態を含む状態Ｄである。オートマトン実行部１４０ｂは、５番目の状態Ｄ４の受理状態２を起点として、遷移前の状態を辿っていくと、図２１の７０に示す状態遷移列となる。
【００８９】
図２１の状態遷移列６０が生成される過程を説明する。図２０において、４番目の状態Ｄ４の状態２の遷移前は、状態１である。３番目の状態Ｄ３の状態１の遷移前は、状態０または状態１である。２番目の状態Ｄ１の状態０の遷移前は、状態０である。また、２番目の状態Ｄ１の状態１の遷移前は、状態０である。初期状態Ｄ０に状態０の遷移前は、状態ｉとなる。このため、オートマトン実行部１４０ｂは、状態遷移列６０を生成する。また、図２に示すとおり、状態０から状態１への遷移、状態１から状態２への遷移が検出対象の遷移となる。
【００９０】
図２１の状態遷移列６０は、状態遷移列６０ａと状態遷移列６０ｂとを含む。また、遷移６１を引き起こすイベント記号とプロパティｉｄの組は、図２０を参照すると、イベントａ、プロパティｉｄ＝１となる。遷移６２を引き起こすイベント記号とプロパティｉｄの組は、図２０を参照すると、イベントａ、プロパティｉｄ＝２となる。遷移６３を引き起こすイベント記号とプロパティｉｄの組は、図２０を参照すると、イベントｂ、プロパティｉｄ＝２となる。ここで、遷移条件を充足する状態遷移列は、状態遷移列６０ａとなることがわかる。このため、オートマトン実行部１４０ｂは、状態遷移列６０ａを残し、状態遷移列６０ｂを削除する。
【００９１】
図２１の状態遷移列７０が生成される過程を説明する。図２０において、５番目の状態Ｄ４の状態２の遷移前は、状態１である。４番目の状態Ｄ４の状態１の遷移前は、状態１である。３番目の状態Ｄ３の状態１の遷移前は、状態０または状態１である。２番目の状態Ｄ１の状態０の遷移前は、状態０である。また、２番目の状態Ｄ１の状態１の遷移前は、状態０である。初期状態Ｄ０に状態０の遷移前は、状態ｉとなる。このため、オートマトン実行部１４０ｂは、状態遷移列７０を生成する。また、図２に示すとおり、状態０から状態１への遷移、状態１から状態２への遷移が検出対象の遷移となる。
【００９２】
図２１の状態遷移列７０は、状態遷移列７０ａと状態遷移列７０ｂとを含む。また、遷移７１を引き起こすイベント記号とプロパティｉｄの組は、図２０を参照すると、イベントａ、プロパティｉｄ＝１となる。遷移７２を引き起こすイベント記号とプロパティｉｄの組は、図２０を参照すると、イベントａ、プロパティｉｄ＝２となる。遷移７３を引き起こすイベント記号とプロパティｉｄの組は、図２０を参照すると、イベントｂ、プロパティｉｄ＝１となる。ここで、遷移条件を充足する状態遷移列は、状態遷移列７０ｂとなることがわかる。このため、オートマトン実行部１４０ｂは、状態遷移列７０ｂを残し、状態遷移列７０ａを削除する。
【００９３】
上記処理を実行することで、図２２に示すように、状態遷移列６０ａと状態遷移列７０ｂとが残る。状態遷移列６０ａ、７０ｂは、遷移条件を充足しつつ、受理状態に遷移するものである。オートマトン実行部１４０ｂは、状態遷移列６０ａ、７０ｂを引き起こしたイベントおよびプロパティｉｄの組を出力する。状態遷移列６０ａを引き起こしたイベントおよびプロパティｉｄの組は、「イベントａ、プロパティｉｄ＝２」、「イベントｂ、プロパティｉｄ＝２」となる。状態遷移列７０ｂを引き起こしたイベントおよびプロパティｉｄの組は、「イベントａ、プロパティｉｄ＝１」、「イベントｂ、プロパティｉｄ＝１」となる。
【００９４】
次に、オートマトン実行部１４０ｂの処理をより詳細に説明する。オートマトン実行部１４０ｂは、入力イベント列１３０ｆの先頭のイベントから順に、決定性状態集合情報１３０ｃと比較する。オートマトン実行部１４０ｂは、比較結果により、初期状態Ｄ０から状態Ｄを遷移させ、遷移する度に、イベント記号およびプロパティと、遷移先の状態Ｄとを順にリスト情報１３０ｇに格納する。
【００９５】
また、オートマトン実行部１４０ｂは、リスト情報１３０ｇに格納された状態Ｄが受理状態に対応する場合に、リスト情報１３０ｇにおいて、該当する状態Ｄを逆順に辿る。オートマトン実行部１４０ｂは、逆順に辿る過程において、イベント記号およびプロパティと、状態Ｄをリスト情報１３０ｇから抽出し、遷移条件集合情報１３０ｂおよび対応マップ１３０ｄを基にして、遷移条件を充足しつつ、受理状態に至ったイベント列のイベントおよびプロパティの組を判定する。
【００９６】
ここで、オートマトン実行部１４０ｂが、リスト情報１３０ｇを生成する処理の処理手順について説明する。図２３は、リスト情報を生成する処理の処理手順を示すフローチャートである。図２３に示すように、オートマトン実行部１４０ｂは、現在の状態として、状態Ｄ０をセットし（ステップＳ２０１）、リスト情報１３０ｇに状態Ｄ０を追加する（ステップＳ２０２）。
【００９７】
オートマトン実行部１４０ｂは、入力イベント列１３０ｆからイベント１つおよびそのプロパティを取り出す（ステップＳ２０３）。オートマトン実行部１４０ｂは、取り出したイベントおよびプロパティをリスト情報１３０ｇに追加する（ステップＳ２０４）。
【００９８】
オートマトン実行部１４０ｂは、決定性状態集合情報１３０ｃを参照して、現在の状態Ｄと、取り出したイベントに基づき遷移後の状態Ｄを決定し（ステップＳ２０５）、リスト情報１３０ｇに遷移後の状態Ｄを追加する（ステップＳ２０６）。オートマトン実行部１４０ｂは、遷移後の状態Ｄが、付加アクション情報１３０ｅに登録されているか否かを判定する（ステップＳ２０７）。
【００９９】
オートマトン実行部１４０ｂは、遷移後の状態Ｄが、付加アクション情報１３０ｅに登録されていない場合には（ステップＳ２０７，Ｎｏ）、ステップＳ２０９に移行する。
【０１００】
オートマトン実行部１４０ｂは、遷移後の状態Ｄが、付加アクション情報１３０ｅに登録されている場合には（ステップＳ２０７，Ｙｅｓ）、付加アクションを実行する（ステップＳ２０８）。
【０１０１】
オートマトン実行部１４０ｂは、入力イベント列終了ではない場合には（ステップＳ２０９，Ｎｏ）、ステップＳ２０３に移行する。オートマトン実行部１４０ｂは、入力イベント列終了の場合には（ステップＳ２０９，Ｙｅｓ）、リスト情報１３０ｇを生成する処理を終了する。
【０１０２】
オートマトン実行部１４０ｂが、図２３に示した処理手順に基づいて、リスト情報１３０ｇを生成する処理の過程を示す。図２４は、オートマトン実行部がリスト情報を生成する処理を説明するための図である。オートマトン実行部１４０ｂは、リスト情報１３０ｆの位置＠０に、状態Ｄ０を登録する。リスト情報１３０ｇのデータ構造は、図２４のリスト情報１３０ｇ（１）に示すものとなる。
【０１０３】
オートマトン実行部１４０ｂは、入力イベント列１３０ｆの先頭のイベントａと、プロパティｉｄ＝１とを取り出す。オートマトン実行部１４０ｂは、状態Ｄ０から、イベントａによる遷移先を、決定性状態集合情報１３０ｃから判定する。状態Ｄ０は、イベントａによって状態Ｄ１に遷移する。このため、オートマトン実行部１４０ｂは、リスト情報１３０ｆの位置＠１にａ（ｉｄ＝１）を登録する。オートマトン実行部１４０ｂは、リスト情報１３０ｆの位置＠２に状態Ｄ１を登録する。リスト情報１３０ｇのデータ構造は、図２４のリスト情報１３０ｇ（２）に示すものとなる。
【０１０４】
オートマトン実行部１４０ｂは、入力イベント列１３０ｆの２番目のイベントａと、プロパティｉｄ＝２を取り出す。オートマトン実行部１４０ｂは、状態Ｄ１から、イベントａによる遷移先を、決定性状態集合情報１３０ｃから判定する。状態Ｄ１は、イベントａによって状態Ｄ３に遷移する。このため、オートマトン実行部１４０ｂは、位置＠３にａ（ｉｄ＝２）を登録する。オートマトン実行部１４０ｂは、位置＠４に状態Ｄ３を登録する。リスト情報１３０ｇのデータ構造は、図２４のリスト情報１３０ｇ（３）に示すものとなる。
【０１０５】
オートマトン実行部１４０ｂは、入力イベント列１３０ｆの３番目のイベントｂと、プロパティｉｄ＝２を取り出す。オートマトン実行部１４０ｂは、状態Ｄ３から、イベントｂによる遷移先を、決定性状態集合情報１３０ｃから判定する。状態Ｄ３は、イベントｂによって、状態Ｄ４に遷移する。このため、オートマトン実行部１４０ｂは、位置＠５にｂ（ｉｄ＝２）を登録する。オートマトン実行部１４０ｂは、位置＠６に状態Ｄ４を登録する。リスト情報１３０ｇのデータ構造は、図２４のリスト情報１３０ｇ（４）に対応するものとなる。
【０１０６】
リスト情報１３０ｇに登録された状態Ｄ４は、付加アクション情報１３０ｅに登録された状態である。この場合には、オートマトン実行部１４０ｂは、他のスレッドとして、付加アクションを実行する。オートマトン実行部１４０ｂが実行する付加アクションについては後述する。オートマトン実行部１４０ｂは、付加アクションを他のスレッドで実行しつつ、リスト情報１３０ｇを生成する処理を継続して実行する。
【０１０７】
オートマトン実行部１４０ｂは、入力イベント列１３０ｆの４番目のイベントｂと、プロパティｉｄ＝１を取り出す。オートマトン実行部１４０ｂは、状態Ｄ４から、イベントｂによる遷移を、決定性状態集合情報１３０ｃから判定する。状態Ｄ４は、イベントｂによって、状態Ｄ４に遷移する。このため、オートマトン実行部１４０ｂは、位置＠７にｂ（ｉｄ＝１）を登録する。オートマトン実行部１４０ｂは、位置＠８に状態Ｄ４を登録する。リスト情報１３０ｇのデータ構造は、図２４のリスト情報１３０ｇ（５）に示すものとなる。
【０１０８】
リスト情報１３０ｇに登録された状態Ｄ４は、付加アクション情報１３０ｅに登録された状態である。この場合には、オートマトン実行部１４０ｂは、他のスレッドとして、付加アクションを実行する。オートマトン実行部１４０ｂが実行する付加アクションについては後述する。オートマトン実行部１４０ｂは、付加アクションを他のスレッドで実行しつつ、リスト情報１３０ｇを生成する処理を継続して実行する。
【０１０９】
この後、オートマトン実行部１４０ｂは、入力イベント列１３０ｆから例示しないイベントを無限に受けとる。ここでは説明を省略するが、オートマトン実行部１４０ｂは、図２３のステップＳ２０３に移行し、リスト情報を生成する。
【０１１０】
次に、リスト情報１３０ｇに格納された状態Ｄが受理状態である場合の処理について説明する。ここで、状態Ｄが受理状態であることと、状態Ｄが付加アクション情報１３０ｅに登録されていることは、同じことである。以下に示す処理は、上記の付加アクションに対応する処理である。なお参照ポインタ、スタック１３０ｈ、充足判定情報１３０ｉ、充足判定対象情報１３０ｊは新規作成されるスレッドごとにその格納領域がある。
【０１１１】
図２５は、付加アクションの処理手順を示すフローチャートである。図２５に示すように、オートマトン実行部１４０ｂは、スタック１３０ｈ、充足判定情報１３０ｉ、充足判定対象情報１３０ｊを空に設定する（ステップＳ３０１）。
【０１１２】
オートマトン実行部１４０ｂは、新規スレッドを作成し、リスト情報１３０ｇの末尾を参照ポインタに設定する（ステップＳ３０２）。ステップＳ３０２において、末尾は、リスト情報１３０ｇにおいて、受理状態となる状態Ｄから最も離れた位置＠に対応する。
【０１１３】
オートマトン実行部１４０ｂは、参照ポインタの状態Ｄに対応し、遷移先が受理状態となる（非決定性状態集合情報１３０ａの）遷移の集合を対応マップ１３０ｄから検索する（ステップＳ３０３）。オートマトン実行部１４０ｂは、検索結果に複数の要素すなわち（非決定性状態集合情報１３０ａの）遷移が存在する場合には、２要素目以降を処理するためのスレッドを要素毎に作成する。このとき参照ポインタ、スタック１３０ｈ、充足判定情報１３０ｉ、充足判定対象情報１３０ｊの内容を元のスレッドから新しいスレッドにコピーする（ステップＳ３０４）。以降の処理は各スレッドに対してそれぞれ行う処理である。
【０１１４】
オートマトン実行部１４０ｂは、該当要素の遷移先の（非決定性状態集合情報１３０ａの）状態をスタック１３０ｈにプッシュする（ステップＳ３０５）。オートマトン実行部１４０ｂは、参照ポインタをリスト情報１３０ｇの一つ前の状態に移動させ（ステップＳ３０６）、参照ポインタが指し示す位置を、スタック１３０ｈにプッシュする（ステップＳ３０７）。
【０１１５】
オートマトン実行部１４０ｂは、状態遷移が遷移条件を伴う場合、すなわち状態遷移の遷移前後の（非決定性状態集合情報１３０ａの）状態と参照ポインタが指し示す位置のイベント記号の両方がマッチし遷移条件が書かれた行が遷移条件集合情報１３０ｂに現れる場合に、その遷移条件を充足判定情報１３０ｉに格納し、判定状況を未判定に設定する（ステップＳ３０８）。オートマトン実行部１４０ｂは、状態遷移が遷移条件に対応する場合、すなわち状態遷移の遷移前後の（非決定性状態集合１３０ａの）状態と参照ポインタが指し示す位置のイベント記号の両方がマッチしイベント参照記号名が書かれた行が遷移条件集合情報１３０ｂに現れる場合に、そのイベント参照記号名と参照ポインタが指し示す位置との組を、充足判定対象情報１３０ｊに登録する（ステップＳ３０９）。
【０１１６】
オートマトン実行部１４０ｂは、充足判定情報１３０ｉに格納された遷移条件を一つ選択し、遷移条件に現れるイベント記号参照名すべてが充足判定対象情報１３０ｊに格納されているなら、イベント記号参照名に対応づいたイベントポインタのポイント先を参照してイベントのプロパティの値を取得しそれを遷移条件に代入したうえで遷移条件を充足判定する（ステップＳ３１０）。オートマトン実行部１４０ｂは、遷移条件の充足判定が行われた結果充足しないことが判明した場合には（ステップＳ３１１，Ｎｏ）、この処理を実行しているスレッドを終了する。なお他のスレッドの処理は継続する。３００Ａに示す処理ステップＳ３０４〜３１８および３００Ｂに示す処理ステップＳ３０２〜３１８は、スレッド毎に実行されるものとする。
【０１１７】
オートマトン実行部１４０ｂは、遷移条件を充足するもしくは遷移条件充足判定が行われなかった場合には（ステップＳ３１１，Ｙｅｓ）、充足判定情報１３０ｉに格納された遷移条件を全て選択したか否かを判定する（ステップＳ３１２）。オートマトン実行部１４０ｂは、遷移条件を全て選択していない場合には（ステップＳ３１２，Ｎｏ）、ステップＳ３１０に移行する。
【０１１８】
オートマトン実行部１４０ｂは、充足判定情報１３０ｉに格納された遷移条件を全て選択した場合には（ステップＳ３１２，Ｙｅｓ）、参照ポインタをリスト情報１３０ｇの一つ前の位置に移動する（ステップＳ３１３）。オートマトン実行部１４０ｂは、参照ポインタの状態Ｄは初期状態であるか否かを判定する（ステップＳ３１４）。
【０１１９】
オートマトン実行部１４０ｂは、参照ポインタの状態Ｄが初期状態ではない場合には（ステップＳ３１４，Ｎｏ）、状態Ｄに対応し、かつ、遷移先の状態が、ステップＳ３０５の遷移元となる（非決定性状態集合情報１３０ａの）遷移の集合を対応マップ１３０ｄから検索する（ステップＳ３１５）。オートマトン実行部１４０ｂは、ステップＳ３０４に移行する。
【０１２０】
一方、オートマトン実行部１４０ｂは、参照ポインタの状態Ｄが初期状態の場合には（ステップＳ３１４，Ｙｅｓ）、（非決定性状態集合情報１３０ａの）初期状態０をスタック１３０ｈにプッシュする（ステップＳ３１６）。オートマトン実行部１４０ｂは、スタック１３０ｈに格納されたイベントの内容をスタックボトム側から順にコピーする。ただしスタック１３０ｈ上でイベント前後の（非決定性状態集合情報１３０ａの）状態について、スタックボトム側の状態が非決定性状態集合情報１３０ａの２０Ａの遷移元状態となり逆側の状態が遷移先状態となりかつイベント記号が合致する行が存在してそのイベント種別が検出対象であるイベントのみをコピーする。またスタック１３０ｈにはリスト情報１３０ｇへのポインタのみが格納されているが、コピーするのはポインタではなくポインタが指し示す先のイベント記号および付随するプロパティの内容である（ステップＳ３１７）。リストを「検出したイベント列の一つ」として出力し、この処理スレッドを終了する（ステップＳ３１８）。ステップＳ３１７において、スタックボトムは最初にプッシュされた内容が格納されている側である。なお他のスレッドの処理は継続する。３００Ａに示す処理ステップＳ３０４〜３１８および３００Ｂに示す処理ステップＳ３０２〜３１８は、スレッド毎に実行されるものとする。
【０１２１】
オートマトン実行部１４０ｂが、図２５に示した処理手順に基づいて、付加アクションを実行する処理について説明する。図２６〜図３２は、オートマトン実行部が付加アクションを実行する処理を説明するための図である。ここでは、オートマトン実行部１４０ｂは、リスト情報１３０ｇの位置＠６にて、付加アクションを実行する場合について説明する。
【０１２２】
図２６について説明する。オートマトン実行部１４０ｂは、新規スレッドを作成し、参照ポインタを位置＠６に設定する。参照ポインタ＠６の状態Ｄ４に対応し、遷移先が受理状態となる対応付け前の遷移の集合は｛１→２｝となる。オートマトン実行部１４０ｂは、遷移の集合を、対応マップ１３０ｄを基に判定する。オートマトン実行部１４０ｂは、遷移先の状態２をスタック１３０ｈにプッシュする。また、オートマトン実行部１４０ｂは、遷移の集合｛１→２｝の各要素について個々のスレッドで以降の処理を行うが今回は要素が一つであるためスレッド分岐せずに要素である（非決定性状態集合情報１３０ａの）遷移１→２についての処理を行う。遷移１→２に対してその遷移先である状態２をスタック１３０ｈにプッシュする。
【０１２３】
オートマトン実行部１４０ｂは、参照ポインタをリスト情報１３０ｇの一つ前の位置＠５に移動する。オートマトン実行部１４０ｂは、参照ポインタが指し示す位置＠５をスタック１３０ｈにプッシュする。図２６のスタック１３０ｈでは位置＠５のイベント内容が何であるか追いやすいように括弧書きでイベント記号とプロパティ値を記してあるが、ここに実際に格納するのは位置＠５のみである。これは以降の図２７から図３２でも同様である。
【０１２４】
また、遷移条件集合情報１３０ｂを参照すると、イベントｂによる状態１から状態２への遷移は、遷移条件「x.id==y.id」を伴う。また、遷移条件集合情報１３０ｂを参照すると、該当遷移は、遷移条件の充足判定のために記憶しておく必要があり、イベント記号参照名は「ｙ」となる。このため、オートマトン実行部１４０ｂは、充足判定情報１３０ｉに遷移条件「x.id==y.id」を登録し、判定状況を「未判定」に設定する。また、オートマトン実行部１４０ｂは、充足判定対象情報１３０ｊのイベント記号参照名に「ｙ」を登録し、イベントポインタを位置＠５に設定する。図２６の充足判定対象情報１３０ｊでは位置＠５のイベント内容が何であるか追いやすいように括弧書きでイベント記号とプロパティ値を記してあるが、ここに実際に格納するのは位置＠５のみである。これは以降の図２７から図３２でも同様である。
【０１２５】
オートマトン実行部１４０ｂは、参照ポインタをリスト情報１３０ｇの一つ前の位置＠４に移動する。オートマトン実行部１４０ｂは、参照ポインタ＠４の状態Ｄ３に対応し、遷移後の状態が状態１となる対応付け前の遷移の集合を判定すると、｛０→１、１→１｝となる。
【０１２６】
図２７について説明する。ここでは、状態遷移集合｛０→１、１→１｝の一つの要素である状態遷移０→１に着目する。状態遷移１→１に関しては、別のスレッドにより実行される。オートマトン実行部１４０ｂは、遷移先の状態１をスタック１３０ｈにプッシュする。また、オートマトン実行部１４０ｂは、状態遷移０→１に対してその遷移先である状態１をスタック１３０ｈにプッシュする。
【０１２７】
オートマトン実行部１４０ｂは、参照ポインタをリスト情報１３０ｇの一つ前の位置＠３に移動する。オートマトン実行部１４０ｂは、参照ポインタが指し示す位置＠３をスタック１３０ｈにプッシュする。
【０１２８】
また、遷移条件集合情報１３０ｂを参照すると、イベントａによる状態０から状態１への遷移は、遷移条件の充足判定のために記憶しておく必要があり、イベント記号参照名は「ｘ」となる。このため、オートマトン実行部１４０ｂは、充足判定対象情報１３０ｊのイベント記号参照名に「ｘ」を登録し、イベントポインタを位置＠３に設定する。
【０１２９】
充足判定に必要な情報が全て充足判定対象情報１３０ｊに格納されているので、オートマトン実行部１４０ｂは、遷移条件「x.id==y.id」を充足するか否かを判定する。オートマトン実行部１４０ｂは、x.idとy.idとが等しいので、判定状況を「判定済み・充足」に設定する。
【０１３０】
オートマトン実行部１４０ｂは、参照ポインタをリスト情報１３０ｇの一つ前の位置＠２に移動する。オートマトン実行部１４０ｂは、参照ポインタ＠２の状態Ｄ１に対応し、遷移後の状態が状態０となる対応付け前の遷移の集合を判定すると、｛０→０｝となる。
【０１３１】
図２８について説明する。ここでは、状態遷移集合｛０→０｝の唯一の要素である状態遷移０→０に着目する。オートマトン実行部１４０ｂは、遷移先の状態０をスタック１３０ｈにプッシュする。また、オートマトン実行部１４０ｂは、状態遷移０→０に対してその遷移先である状態０をスタック１３０ｈにプッシュする。
【０１３２】
オートマトン実行部１４０ｂは、参照ポインタをリスト情報１３０ｇの一つ前の位置＠１に移動する。オートマトン実行部１４０ｂは、参照ポインタが指し示す位置＠１をスタック１３０ｈにプッシュする。
【０１３３】
図２９について説明する。オートマトン実行部１４０ｂは、参照ポインタをリスト情報１３０ｇの一つ前の位置＠０に移動する。オートマトン実行部１４０ｂは、参照ポインタ＠０の状態Ｄ０に対応し、遷移後の状態が状態０となる対応付け前の遷移の集合を判定すると｛ｉ→０｝となる。遷移集合｛ｉ→０｝の唯一の要素である状態遷移ｉ→０に着目する。オートマトン実行部１４０ｂは、遷移先の状態０をスタック１３０ｈにプッシュする。
【０１３４】
オートマトン実行部１４０ｂは、（非決定性状態集合情報１３０ａの）の初期状態０まで達したので、スタック１３０ｈに格納されたイベント列を参照し、図２の非決定性状態集合１３０ａで表されるパターンに合致し図３の遷移条件集合情報１３０ｂで表される遷移条件を充足したイベント列「ａ（ｉｄ＝２）、ｂ（ｉｄ＝１）」を出力する。図２６〜図２９に示した処理は、図２２に示した状態遷移列６０ａを検出することに対応する。
【０１３５】
上記図２７以降では、状態遷移集合｛０→１、１→１｝の一つの要素である状態遷移０→１に着目して、イベント列を抽出する場合について説明した。ここでは、状態遷移０→１に着目したスレッドとは別のスレッドで行われる、もう一つの要素である状態遷移１→１に着目した処理について説明する。なお、参照ポインタ、スタック１３０ｈ、充足判定情報１３０ｉ、充足判定対象情報１３０ｊは、スレッド毎に格納領域が存在する。これらの情報はスレッド分岐が行われる際に内容がコピーされる。
【０１３６】
図３０について説明する。ここでは、状態遷移１→１に着目する。オートマトン実行部１４０ｂは、状態遷移１→１に対してその遷移先である状態１をスタック１３０ｈにプッシュする。
【０１３７】
オートマトン実行部１４０ｂは、参照ポインタをリスト情報１３０ｇの一つ前の位置＠３に移動する。オートマトン実行部１４０ｂは、参照ポインタが指し示す位置＠３をスタック１３０ｈにプッシュする。
【０１３８】
オートマトン実行部１４０ｂは、参照ポインタをリスト情報１３０ｇの一つ前の位置＠２に移動する。オートマトン実行部１４０ｂは、参照ポインタ＠２の状態Ｄ１に対応し、遷移後の状態が状態１となる対応付け前の遷移の集合を判定すると、｛０→１｝となる。
【０１３９】
図３１について説明する。ここでは状態遷移集合｛０→１｝の唯一の要素である遷移０→１に着目する。オートマトン実行部１４０ｂは、遷移先の状態１をスタック１３０ｈにプッシュする。
【０１４０】
オートマトン実行部１４０ｂは、参照ポインタをリスト情報１３０ｇの一つ前の位置＠１に移動する。オートマトン実行部１４０ｂは、参照ポインタが指し示す位置＠１のイベントａとプロパティｉｄ＝１をスタック１３０ｈにプッシュする。
【０１４１】
また、遷移条件集合情報１３０ｂを参照すると、イベントａによる状態０から状態１への遷移は、遷移条件の充足判定のために記憶しておく必要があり、イベント記号参照名は「ｘ」となる。このため、オートマトン実行部１４０ｂは、充足判定対象情報１３０ｊのイベント記号参照名に「ｘ」を登録し、イベントポインタを位置＠１に設定する。
【０１４２】
充足判定に必要な情報が全て充足判定対象情報１３０ｊに格納されているので、オートマトン実行部１４０ｂは、遷移条件「x.id==y.id」を充足するか否かを判定する。オートマトン実行部１４０ｂは、x.idとy.idとが異なるので、判定状況を「判定済み・充足せず」に設定する。遷移条件を充足しないので、オートマトン実行部１４０ｂは、該当スレッドを終了する。
【０１４３】
ところで、オートマトン実行部１４０ｂは、リスト情報１３０ｇの位置＠８にて、付加アクションを実行すると、（非決定性状態集合情報１３０ａの）の初期状態０に至るまでの過程において、図３２に示すリスト情報１３０ｇが生成する。また、充足判定情報１３０ｉ、充足判定対象情報１３０ｊは、図３２に示すものとなる。
【０１４４】
オートマトン実行部１４０ｂは、遷移条件「x.id==y.id」を充足するか否かを判定する。オートマトン実行部１４０ｂは、x.idとy.idとが等しいので、判定状況を「判定済み・充足」に設定する。オートマトン実行部１４０ｂは、初期状態０まで達した後、スタック１３０ｈに格納されたイベント列を参照し、遷移条件を充足したイベント列「ａ（ｉｄ＝１）、ｂ（ｉｄ＝１）」を出力する。図３２に示した処理は、図２２に示した状態遷移列７０ｂを検出することに対応する。
【０１４５】
オートマトン実行部１４０ｂは、上記の処理を実行することで、入力イベント列１３０ｆから、図２の非決定性状態集合１３０ａで表されるパターンに合致し図３の遷移条件集合情報１３０ｂで表される遷移条件を満たすイベント列「ａ（ｉｄ＝２）、ｂ（ｉｄ＝１）」、「ａ（ｉｄ＝１）、ｂ（ｉｄ＝１）」を検出する。オートマトン実行部１４０ｂは、検出したイベント列を、出力部１２０に出力する。
【０１４６】
オートマトン実行部１４０ｂは、図２３のステップＳ２０７に示したように、リスト情報１３０ｇにおいて、遷移後の状態Ｄが付加アクション情報に登録されていることを検出する度に、新規のスレッドを立てて、並列的に付加アクションを実行する。また、オートマトン実行部１４０ｂは、付加アクションを実行する場合に、図２５のステップＳ３０４に示したように、検索結果に複数の要素が存在する場合には、各要素を処理するためのスレッドを立てて、付加アクションを並列的に実行する。なお、スレッド毎に、参照ポインタ、スタック１３０ｈ、充足判定情報１３０ｉ、充足判定対象情報１３０ｊの領域がそれぞれ確保されているものとする。
【０１４７】
次に、本実施例にかかる情報処理装置１００の処理手順について説明する。図３３は、本実施例にかかる情報処理装置の処理手順を示すフローチャートである。図３３に示す処理は、例えば、入力部１１０から、対応付け指示を受け付けた場合に、処理を開始しても良いし、非決定性状態集合情報１３０ａが記憶部１３０に格納された場合に、処理を開始してもよい。
【０１４８】
図３３に示すように、情報処理装置１００は、対応付け処理を実行し（ステップＳ４０１）、オートマトン実行処理を実行する（ステップＳ４０２）。ここで、ステップＳ４０１に示した対応付け処理は、図１２において説明した処理に対応する。また、ステップＳ４０２に示したオートマトン実行処理は、図２３、図２５に示した処理に対応する。
【０１４９】
次に、本実施例にかかる情報処理装置１００の効果について説明する。情報処理装置１００は、入力イベント列１３０ｆの先頭のイベントから順に、決定性状態集合情報１３０ｃと比較して、状態Ｄを遷移させて、リスト情報１３０ｇを生成する。情報処理装置１００は、リスト情報１３０ｇに、受理状態の状態Ｄが格納された場合に、各状態Ｄに対応付けられた状態および遷移前の状態の対応関係から、該当状態Ｄを起点として、スタック１３０ｈを利用し、遷移前の状態を順に辿っていく。情報処理装置１００は、状態Ｄを遷移前の状態に辿っていく過程において、遷移を引き起こしたイベント記号と、イベント記号に対応するプロパティを検出して、遷移条件を充足するか否かを判定し、遷移条件を満たすイベント列を検出する。このような処理を情報処理装置１００が実行することで、イベントパターンの照合精度の低下を防止することができる。
【０１５０】
また、情報処理装置１００は、受理状態となる状態Ｄが複数リスト情報１３０ｇに格納されている場合には、状態Ｄを起点として、並列的に、リスト情報１３０ｇを逆順に辿り、遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定する。このように、並列的に処理を実行するので、処理効率を向上させることができる。また、並列的に処理を実行する際に、一般に大きな格納領域を必要とするイベントの記号とプロパティ内容をコピーするのではなく、リスト情報１３０ｇに格納された唯一の内容を全ての並列的処理で参照するので、並列的処理にともなう格納領域使用量の増大を抑制することができる。
【０１５１】
また、情報処理装置１００は、状態Ｄを遷移前の状態に辿っていく過程において、状態Ｄを、対応付ける前の状態に戻して、遷移状態を逆順に辿り、受理状態に至ったイベント列のイベントの組を判定する。このため、対応付けによる情報損失を無くし、照合精度を向上させることができる。
【０１５２】
次に、実施例に示した情報処理装置１００と同様の機能を実現する情報処理プログラムを実行するコンピュータの一例を説明する。図３４は、情報処理プログラムを実行するコンピュータの一例を示す図である。
【０１５３】
図３４に示すように、コンピュータ２００は、各種演算処理を実行するＣＰＵ２０１と、ユーザからのデータの入力を受け付ける入力装置２０２と、ディスプレイ２０３を有する。また、コンピュータ２００は、記憶媒体からプログラム等を読取る読み取り装置２０４と、ネットワークを介して他のコンピュータとの間でデータの授受を行うインターフェース装置２０５とを有する。また、コンピュータ２００は、各種情報を一時記憶するＲＡＭ２０６と、ハードディスク装置２０７を有する。そして、各装置２０１〜２０７は、バス２０８に接続される。
【０１５４】
ハードディスク装置２０７は、例えば、対応付けプログラム２０７ａ、オートマトン実行プログラム２０７ｂを有する。ＣＰＵ２０１は、各プログラム２０７ａ、２０７ｂを読み出して、ＲＡＭ２０６に展開する。
【０１５５】
対応付けプログラム２０７ａは、対応付けプロセス２０６ａとして機能する。オートマトン実行プログラム２０７ｂは、オートマトン実行プロセス２０６ｂとして機能する。
【０１５６】
例えば、対応付けプロセス２０６ａは、図１の対応付け部１４０ａに対応する。オートマトン実行プロセス２０６ｂは、図１のオートマトン実行部１４０ｂに対応する。
【０１５７】
なお、各プログラム２０７ａ、２０７ｄについては、必ずしも最初からハードディスク装置２０７に記憶させておかなくてもよい。例えば、コンピュータ２００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に各プログラムを記憶させておく。そして、コンピュータ５００がこれらから各プログラム２０７ａ、２０７ｂを読み出して実行するようにしてもよい。
【０１５８】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１５９】
（付記１）単一の状態に対応付けられ、所定のイベントおよび遷移条件によって所定の状態に遷移する複数の第１状態を有する第１状態遷移情報と、遷移元の第１状態および遷移先の第１状態と、前記遷移元の第１状態から前記遷移先の第１状態に遷移する場合の遷移条件およびイベントとを対応付けた遷移条件集合情報とを記憶する記憶部と、
前記第１状態遷移情報を基にして、複数の第１状態に対応付けられた第２状態を有する第２状態遷移情報を生成し、前記第２状態と、前記第２状態に対応付けられた第１状態および該第１状態に遷移する前の第１状態とを対応付けた対応マップ情報を生成する対応付け部と、
継続的に無制限に入力される可能性がありかつ無視すべきイベントが間に入力され、複数のイベントとプロパティとを対応付けた入力イベント列の先頭のイベントから順に、前記第２状態遷移情報と比較して、前記第２状態遷移情報の初期状態から順に第２状態を遷移させ、遷移する度に、遷移した際のイベントおよびプロパティと遷移先の第２状態とを順にリスト情報に格納し、
リスト情報に格納された第２状態が受理状態である場合に、該第２状態から前記リスト情報を逆順に辿って、該リスト情報に格納されたイベントおよびプロパティと、第２状態とを抽出し、前記遷移条件集合情報および前記対応マップを基にして、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定するオートマトン実行部と
を有することを特徴とする情報処理装置。
【０１６０】
（付記２）前記オートマトン実行部は、受理状態となる複数の第２状態がリスト情報に格納されている場合には、各第２状態を起点として、前記リスト情報を逆順に辿り、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定することを特徴とする付記１に記載の情報処理装置。
【０１６１】
（付記３）前記オートマトン実行部は、前記遷移条件集合情報および前記対応マップを基にして、前記抽出した第２状態を第１状態に戻して、第１状態による状態遷移を受理状態から逆順に辿り、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定することを特徴とする付記１または２に記載の情報処理装置。
【０１６２】
（付記４）コンピュータが実行する情報処理方法であって、
前記コンピュータは、単一の状態に対応付けられ、所定のイベントおよび遷移条件によって所定の状態に遷移する複数の第１状態を有する第１状態遷移情報と、遷移元の第１状態および遷移先の第１状態と、前記遷移元の第１状態から前記遷移先の第１状態に遷移する場合の遷移条件およびイベントとを対応付けた遷移条件集合情報とを記憶する記憶装置を有し、
前記コンピュータが、
前記第１状態遷移情報を基にして、複数の第１状態に対応付けられた第２状態を有する第２状態遷移情報を生成し、前記第２状態と、前記第２状態に対応付けられた第１状態および該第１状態に遷移する前の第１状態とを対応付けた対応マップ情報を生成し、
継続的に無制限に入力される可能性がありかつ無視すべきイベントが間に入力され、複数のイベントとプロパティとを対応付けた入力イベント列の先頭のイベントから順に、前記第２状態遷移情報と比較して、前記第２状態遷移情報の初期状態から順に第２状態を遷移させ、遷移する度に、遷移した際のイベントおよびプロパティと遷移先の第２状態とを順にリスト情報に格納し、
リスト情報に格納された第２状態が受理状態である場合に、該第２状態から前記リスト情報を逆順に辿って、該リスト情報に格納されたイベントおよびプロパティと、第２状態とを抽出し、前記遷移条件集合情報および前記対応マップを基にして、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定する
各処理を実行することを特徴とする情報処理方法。
【０１６３】
（付記５）前記イベントの組を判定する処理は、受理状態となる複数の第２状態がリスト情報に格納されている場合には、各第２状態を起点として、前記リスト情報を逆順に辿り、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定することを特徴とする付記４に記載の情報処理方法。
【０１６４】
（付記６）前記イベントの組を判定する処理は、前記遷移条件集合情報および前記対応マップを基にして、前記抽出した第２状態を第１状態に戻して、第１状態による状態遷移を受理状態から逆順に辿り、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定することを特徴とする付記４または５に記載の情報処理方法。
【０１６５】
（付記７）単一の状態に対応付けられ、所定のイベントおよび遷移条件によって所定の状態に遷移する複数の第１状態を有する第１状態遷移情報と、遷移元の第１状態および遷移先の第１状態と、前記遷移元の第１状態から前記遷移先の第１状態に遷移する場合の遷移条件およびイベントとを対応付けた遷移条件集合情報とを記憶する記憶装置を有するコンピュータに、
前記第１状態遷移情報を基にして、複数の第１状態に対応付けられた第２状態を有する第２状態遷移情報を生成し、前記第２状態と、前記第２状態に対応付けられた第１状態および該第１状態に遷移する前の第１状態とを対応付けた対応マップ情報を生成し、
継続的に無制限に入力される可能性がありかつ無視すべきイベントが間に入力され、複数のイベントとプロパティとを対応付けた入力イベント列の先頭のイベントから順に、前記第２状態遷移情報と比較して、前記第２状態遷移情報の初期状態から順に第２状態を遷移させ、遷移する度に、遷移した際のイベントおよびプロパティと遷移先の第２状態とを順にリスト情報に格納し、
リスト情報に格納された第２状態が受理状態である場合に、該第２状態から前記リスト情報を逆順に辿って、該リスト情報に格納されたイベントおよびプロパティと、第２状態とを抽出し、前記遷移条件集合情報および前記対応マップを基にして、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定する
各処理を実行させることを特徴とする情報処理プログラム。
【０１６６】
（付記８）前記イベントの組を判定する処理は、受理状態となる複数の第２状態がリスト情報に格納されている場合には、各第２状態を起点として、前記リスト情報を逆順に辿り、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定することを特徴とする付記７に記載の情報処理プログラム。
【０１６７】
（付記９）前記イベントの組を判定する処理は、前記遷移条件集合情報および前記対応マップを基にして、前記抽出した第２状態を第１状態に戻して、第１状態による状態遷移を受理状態から逆順に辿り、前記遷移条件を充足しつつ、受理状態に至ったイベント列のイベントの組を判定することを特徴とする付記７または８に記載の情報処理プログラム。
【符号の説明】
【０１６８】
１００    情報処理装置
１１０    入力部
１２０    出力部
１３０    記憶部
１４０    制御部
【図１】
2013092904.tif 000003
【図２】
2013092904.tif 000004
【図３】
2013092904.tif 000005
【図４】
2013092904.tif 000006
【図５】
2013092904.tif 000007
【図６】
2013092904.tif 000008
【図７】
2013092904.tif 000009
【図８】
2013092904.tif 000010
【図９】
2013092904.tif 000011
【図１０】
2013092904.tif 000012
【図１１】
2013092904.tif 000013
【図１２】
2013092904.tif 000014
【図１３】
2013092904.tif 000015
【図１４】
2013092904.tif 000016
【図１５】
2013092904.tif 000017
【図１６】
2013092904.tif 000018
【図１７】
2013092904.tif 000019
【図１８】
2013092904.tif 000020
【図１９】
2013092904.tif 000021
【図２０】
2013092904.tif 000022
【図２１】
2013092904.tif 000023
【図２２】
2013092904.tif 000024
【図２３】
2013092904.tif 000025
【図２４】
2013092904.tif 000026
【図２５】
2013092904.tif 000027
【図２６】
2013092904.tif 000028
【図２７】
2013092904.tif 000029
【図２８】
2013092904.tif 000030
【図２９】
2013092904.tif 000031
【図３０】
2013092904.tif 000032
【図３１】
2013092904.tif 000033
【図３２】
2013092904.tif 000034
【図３３】
2013092904.tif 000035
【図３４】
2013092904.tif 000036
【図３５】
2013092904.tif 000037
【図３６】
2013092904.tif 000038
【図３７】
2013092904.tif 000039
【図３８】
2013092904.tif 000040
【図３９】
2013092904.tif 000041
【図４０】
2013092904.tif 000042