(57)【要約】      （修正有）【課題】グラフィカルユーザインターフェース（ＧＵＩ）に基づくアプリケーションの動作を観測して作成した決定性有限状態機械（ＤＦＳＭ）モデルの精度を向上する。【解決手段】最初にＤＦＳＭモデルは、推測モデル５００ｂの経路５０３がない状態で、構成される。隠れた動作を示す特定のパターンをルールパターンとして、モデルに適用することで、ルールパターンとの不一致を検出する。不一致に対し、新しいモデルを生成し、経路５０３を追加することで、正しい推測モデル５００ｂを得る。【選択図】図５Ｂ
2016004576.tif 000002
【特許請求の範囲】
【請求項１】
複数の経路を含むグラフィカルユーザインターフェース（ＧＵＩ）に基づくアプリケーションのモデルを受け取ることと、
それぞれの経路がルールパターンを満たすパターンを含む前記複数の経路の内の１つ又は複数の経路を決定することであって、前記ルールパターンが前記パターンによって示される前記モデル内の潜在的な不正確さに基づいていることと、
前記１つ又は複数の経路が前記ＧＵＩに基づくアプリケーションと一致しているか否かを決定することの優先順位付けに基づいて、前記モデルが前記ＧＵＩに基づくアプリケーションと一致しているか否かを検証することであって、前記１つ又は複数の経路の前記優先順位付けはそれぞれの経路が前記パターンを含む１つ又は複数の経路に基づいていることと、
を備える方法。
【請求項２】
前記１つ又は複数の経路は、１つ又は複数の第１経路であり、前記パターンは、第１パターンであり、前記ルールパターンは、第１ルールパターンであり、
前記方法は、更に、
それぞれの経路が第２ルールパターンを満たす第２パターンを含む前記複数の経路の内の１つ又は複数の第２経路を決定することであって、前記第２ルールパターンが前記第２パターンによって示される前記モデル内の潜在的な不正確さに基づいていることと、
前記１つ又は複数の第２経路が前記ＧＵＩに基づくアプリケーションと一致しているか否かを決定することの優先順位付けに基づいて、前記モデルが前記ＧＵＩに基づくアプリケーションと一致しているか否かを検証することであって、前記１つ又は複数の第２経路の前記優先順位位付けはそれぞれの経路が前記第２ルールパターンを満たす前記第２パターンを含む１つ又は複数の第２経路に基づいていること、を備える請求項１に記載の方法。
【請求項３】
更に、
前記１つ又は複数の第１経路が前記ＧＵＩに基づくアプリケーションと一致しているか否かを決定することの優先順位付けの上に、前記１つ又は複数の第２経路が前記ＧＵＩに基づくアプリケーションと一致しているか否かを決定することの優先順位を決めることを備える請求項２に記載の方法。
【請求項４】
前記１つ又は複数の第１経路が前記ＧＵＩに基づくアプリケーションと一致しているか否かを決定することの優先順位付けの上に、前記１つ又は複数の第２経路が前記ＧＵＩに基づくアプリケーションと一致しているか否かを決定することの前記優先順位を決めることは、前記第１ルールパターンよりも特異性を有する前記第２ルールパターンに基づいている請求項３に記載の方法。
【請求項５】
前記ルールパターンは、前記モデルの第１状態から前記モデルの第２状態への第１遷移と、前記第１遷移に後続する、前記第２状態から前記モデルの第３状態への第２遷移と、前記第２遷移に後続する、前記第３状態から前記モデルの第４状態への第３遷移をもたらす一連の動作を含み、前記第２状態及び前記第３状態は同じ潜在的動作を含む請求項１に記載の方法。
【請求項６】
前記ルールパターンは、前記モデルの第１状態から前記モデルの第２状態への第１遷移と、前記第１遷移に後続する、前記第２状態から前記モデルの第３状態への第２遷移と、前記第２遷移に後続する、前記第３状態から前記２状態へ戻る第３遷移をもたらす一連の動作を含む請求項１に記載の方法。
【請求項７】
更に、
前記１つ又は複数の経路に適用される１つ又は複数の発見的問題解決法に基づいて、前記１つ又は複数の経路に優先順位の重みを適用することと、
前記優先順位の重みに基づいて、前記１つ又は複数の経路が前記ＧＵＩに基づくアプリケーションと一致しているか否かを決定することに対する順番を決定することと、を備える請求項１に記載の方法。
【請求項８】
前記１つ又は複数の発見的問題解決法は、前記１つ又は複数の経路の１つ又は複数の状態と関連する複数の入力辺を含む請求項７に記載の方法。
【請求項９】
更に、
前記ＧＵＩに基づくアプリケーションの前記ＧＵＩにおいて直接に観測されることから隠されており且つ前記モデルにおける潜在的な不正確さを生成する、前記ＧＵＩに基づくアプリケーションの動作を示す前記モデルのトポロジーに基づいて、前記ルールパターンを決定することを備える請求項１に記載の方法。
【請求項１０】
前記モデルの前記トポロジーが前記モデル内の潜在的な不正確さを示すように、前記トポロジーは、前記ＧＵＩに基づくアプリケーションの複数の状態が、前記モデルにおける単一の状態によって潜在的に表されることを示す請求項９に記載の方法。
【請求項１１】
グラフィカルユーザインターフェース（ＧＵＩ）に基づくアプリケーションのモデルを検証する動作をシステムに実行させるように構成されたコンピュータ実行可能な命令を含むコンピュータ可読記憶媒体であって、
前記動作は、
複数の経路を含むグラフィカルユーザインターフェース（ＧＵＩ）に基づくアプリケーションのモデルを受け取ることと、
それぞれの経路がルールパターンを満たすパターンを含む前記複数の経路の内の１つ又は複数の経路を決定することであって、前記ルールパターンが前記パターンによって示される前記モデル内の潜在的な不正確さに基づいていることと、
前記１つ又は複数の経路が前記ＧＵＩに基づくアプリケーションと一致しているか否かを決定することの優先順位付けに基づいて、前記モデルが前記ＧＵＩに基づくアプリケーションと一致しているか否かを検証することであって、前記１つ又は複数の経路の前記優先順位付けはそれぞれの経路が前記パターンを含む１つ又は複数の経路に基づいていることと、
を備えるコンピュータ可読記憶媒体。
【請求項１２】
前記１つ又は複数の経路は、１つ又は複数の第１経路であり、前記パターンは、第１パターンであり、前記ルールパターンは、第１ルールパターンであり、
前記動作は、更に、
それぞれの経路が第２ルールパターンを満たす第２パターンを含む前記複数の経路の内の１つ又は複数の第２経路を決定することであって、前記第２ルールパターンが前記第２パターンによって示される前記モデル内の潜在的な不正確さに基づいていることと、
前記１つ又は複数の第２経路が前記ＧＵＩに基づくアプリケーションと一致しているか否かを決定することの優先順位付けに基づいて、前記モデルが前記ＧＵＩに基づくアプリケーションと一致しているか否かを検証することであって、前記１つ又は複数の第２経路の前記優先順位付けはそれぞれの経路が前記第２ルールパターンを満たす前記第２パターンを含む１つ又は複数の第２経路に基づいていること、
請求項１１に記載のコンピュータ可読記憶媒体。
【請求項１３】
前記動作は、更に、
前記１つ又は複数の第１経路が前記ＧＵＩに基づくアプリケーションと一致しているか否かを決定することの優先順位付けの上に、前記１つ又は複数の第２経路が前記ＧＵＩに基づくアプリケーションと一致しているか否かを決定することの優先順位を決めることを備える請求項１２に記載のコンピュータ可読記憶媒体。
【請求項１４】
前記１つ又は複数の第１経路が前記ＧＵＩに基づくアプリケーションと一致しているか否かを決定することの優先順位付けの上に、前記１つ又は複数の第２経路が前記ＧＵＩに基づくアプリケーションと一致しているか否かを決定することの前記優先順位を決めることは、前記第１ルールパターンよりも特異性を有する前記第２ルールパターンに基づいている請求項１３に記載のコンピュータ可読記憶媒体。
【請求項１５】
前記ルールパターンは、前記モデルの第１状態から前記モデルの第２状態への第１遷移と、前記第１遷移に後続する、前記第２状態から前記モデルの第３状態への第２遷移と、前記第２遷移に後続する、前記第３状態から前記モデルの第４状態への第３遷移をもたらす一連の動作を含み、前記第２状態及び前記第３状態は同じ潜在的動作を含む請求項１１に記載のコンピュータ可読記憶媒体。
【請求項１６】
前記ルールパターンは、前記モデルの第１状態から前記モデルの第２状態への第１遷移と、前記第１遷移に後続する、前記第２状態から前記モデルの第３状態への第２遷移と、前記第２遷移に後続する、前記第３状態から前記２状態へ戻る第３遷移をもたらす一連の動作を含む請求項１１に記載のコンピュータ可読記憶媒体。
【請求項１７】
前記動作は、更に、
前記１つ又は複数の経路に適用される１つ又は複数の発見的問題解決法に基づいて、前記１つ又は複数の経路に優先順位の重みを適用することと、
前記優先順位の重みに基づいて、前記１つ又は複数の経路が前記ＧＵＩに基づくアプリケーションと一致しているか否かを決定することに対する順番を決定することと、を備える請求項１１に記載のコンピュータ可読記憶媒体。
【請求項１８】
前記１つ又は複数の発見的問題解決法は、前記１つ又は複数の経路の１つ又は複数の状態と関連する複数の入力辺を含む請求項１７に記載のコンピュータ可読記憶媒体。
【請求項１９】
前記動作は、更に、
前記ＧＵＩに基づくアプリケーションの前記ＧＵＩにおいて直接に観察されることから隠されており且つ前記モデルにおける潜在的な不正確さを生成する、前記ＧＵＩに基づくアプリケーションの動作を示す前記モデルのトポロジーに基づいて、前記ルールパターンを決定することを備える請求項１１に記載のコンピュータ可読記憶媒体。
【請求項２０】
前記モデルの前記トポロジーが前記モデル内の潜在的な不正確さを示すように、前記トポロジーは、前記モデルにおける単一の状態が前記ＧＵＩに基づくアプリケーションの複数の状態と潜在的に関連することを示す請求項１９に記載のコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書で議論される実施形態は、グラフィカルユーザインターフェース（ＧＵＩ）に基づくアプリケーションのモデルを検証することに関する。
【背景技術】
【０００２】
携帯装置のための携帯アプリケーションのような、電子装置のためのグラフィカルユーザインターフェース（ＧＵＩ）に基づくアプリケーション（ｇｒａｐｈｉｃａｌ  ｕｓｅｒ  ｉｎｔｅｒｆａｃｅ  ｂａｓｅｄ  ａｐｐｌｉｃａｔｉｏｎ）は、ますます一般的になってきている。多くのＧＵＩに基づくアプリケーションは、タッチスクリーンによってＧＵＩで実行される操作に基づいて動作を実行し、ＧＵＩに基づくアプリケーションの使用を容易にし得る。しかし、ＧＵＩ及びＧＵＩに基づくアプリケーションのタッチスクリーンのインターフェースは、また、ＧＵＩに基づくアプリケーションの動作及びＧＵＩに基づくアプリケーションのモデル化を評価する際に、挑戦を提供する。
【０００３】
ここに請求される主題は、不利を解決するか、又は、上述したこれらのような環境のみで動作する実施形態には限定されない。むしろ、この背景は、ここに述べられるある実施形態が具体化されるかもしれない１つの例示の技術領域を説明するために、提供されるだけである。
【発明の概要】
【課題を解決するための手段】
【０００４】
一実施形態によれば、方法は、複数の経路を含むグラフィカルユーザインターフェース（ＧＵＩ）に基づくアプリケーションのモデルを受け取ることを含み得る。また、方法は、それぞれの経路がルールパターンを満たすパターンを含む、複数の経路の内の１つ又は複数の経路を決定することを含み得る。ルールパターンは、パターンによって示されるモデル内の潜在的な不正確さに基づき得る。方法は、また、モデルがＧＵＩに基づくアプリケーションと一致しているか否かを検証し得る。検証は、１つ又は複数の経路がＧＵＩに基づくアプリケーションと一致しているか否かを決定することの優先順位付けに基づき得る。１つ又は複数の経路の優先順位付けはそれぞれの経路がパターンを含む１つ又は複数の経路に基づき得る。
【０００５】
本発明の目的及び効果は、特に請求項において指摘される構成要素及び組み合わせを用いることによって認識され且つ得られるだろう。
【０００６】
前述の一般的な説明及び後述の詳細な説明の両方は、例示的及び説明的なものであり、特許請求の範囲に記載されている本発明を制限するものではない。
【０００７】
例示の実施形態が、添付の図面を用いて、追加の特定及び詳細と共に、述べられて説明される。
【図面の簡単な説明】
【０００８】
【図１Ａ】図１Ａは、ＧＵＩに基づくアプリケーションのモデルを生成及び検証する例示のシステムを示す。
【図１Ｂ】図１Ｂは、例示のルールパターンを示す。
【図１Ｃ】図１Ｃは、他の例示のルールパターンを示す。
【図２Ａ】図２Ａは、サンプルのＧＵＩに基づくアプリケーションの様々な画面を示す。
【図２Ｂ】図２Ｂは、図２ＡのサンプルのＧＵＩに基づくアプリケーションの動作を表し得る例示のＤＦＳＭモデルを示す。
【図３】図３は、ＧＵＩに基づくアプリケーションのＤＦＳＭモデルを生成する例示の方法のフローチャートである。
【図４Ａ】図４Ａは、ＧＵＩに基づくアプリケーションのＤＦＳＭモデルを検証する例示の方法のフローチャートである。
【図４Ｂ】図４Ｂは、図４Ａのフローチャートの続きである。
【図５Ａ】図５Ａは、図２ＡのＧＵＩに基づくアプリケーションの例示の推測モデルを示す。
【図５Ｂ】図５Ｂは、図２ＡのＧＵＩに基づくアプリケーションの他の例示の推測モデルを示す。
【発明を実施するための形態】
【０００９】
グラフィカルユーザインターフェース（ＧＵＩ）に基づくアプリケーション（以下、ＧＵＩに基づくアプリケーションと称される）の動作（ｂｅｈａｖｉｏｒ：）は、学習されて、その後、任意の数の動作（又は行動）学習技術及びアルゴリズムを用いて、有限状態モデル（ｆｉｎｉｔｅ−ｓｔａｔｅ  ｍｏｄｅｌ）としてモデル化され得る。例えば、クローラ（ｃｒａｗｌｅｒ）は、ＧＵＩに基づくアプリケーションをクロール（ｃｒａｗｌ）し、クロールの間にＧＵＩに基づくアプリケーションを観測し且つ記録し得る。記録された動作は、記録された動作に基づいてＧＵＩに基づくアプリケーションの有限状態の推測モデル（以下、推測モデルと称される）を導き得る学習エンジンに送られ得る。ある例では、推測モデルは、ＧＵＩに基づくアプリケーションの実際の動作に対して不正確であり得る。
【００１０】
例えば、クローラは、ＧＵＩに基づくアプリケーションのＧＵＩから直接観測可能であるＧＵＩに基づくアプリケーションの動作（以下、直接観測可能な動作）をクローラが観測するような、ＧＵＩに基づくアプリケーションのＧＵＩ上の活動を実行することによって、ＧＵＩに基づくアプリケーションの動作を観測し且つ記録し得る。しかし、ＧＵＩに基づくアプリケーションは、ＧＵＩに基づくアプリケーション上で直接観測可能でない動作(以下、隠れた動作と称される)を含み得る。従って、クローラは、ＧＵＩに基づくアプリケーションの真実の動作を正確に観測しないので、推測モデルは、ＧＵＩに基づくアプリケーションの実際の動作と比べて不正確であり得る。
【００１１】
ＧＵＩに基づくアプリケーションの隠れた動作は、ＧＵＩに基づくアプリケーションの直接観測可能な動作における特定のパターンとして、現れ得る。従って、特定のパターンに従う推測モデルの経路（ｐａｔｈ）は、ＧＵＩに基づくアプリケーションの隠れた動作が、特定のパターンに従う経路によって表され得る直接観測可能な動作と共に生じ得ることを示し得る。結果として、特定のパターンに従う経路は、ＧＵＩに基づくアプリケーションの真実の動作と矛盾していることの高い可能性を有し得る。
【００１２】
以下に詳述されるように、本開示のある実施形態によれば、推測モデルは、推測モデルのどの経路がルールパターンを満たすパターンを含むのかを決定することによって検証され得る。ルールパターンは、パターンによって示され得る推測モデルの潜在的な不正確さに基づき得る。例えば、ルールパターンは、ＧＵＩに基づくアプリケーションの隠れた動作と通常関連しているパターンに基づき得る。
【００１３】
ルールパターンを満たす経路は、経路がＧＵＩに基づくアプリケーションと一致しているか否かを決定するために、ルールパターンを満たさない経路の上に優先順位付け（ｐｒｉｏｒｉｔｉｚｅｄ  ｏｖｅｒ  ｐａｔｈ）され得る。経路の優先順位付けは、推測モデルがＧＵＩに基づくアプリケーションに対して不正確であり且つ一致しないことを早く決定する可能性を増加し得る。従って、推測モデルを検証する効率は、ルールに基づく検証を実行しない他の検証方法と比べて、向上し得る。本開示では、モデル又はモデルの経路がＧＵＩに基づくアプリケーションに対して一致するか、等しいか又は正確であるか否かに関する参照は、モデル又は経路がＧＵＩに基づくアプリケーションの実際の動作を正確に表すか否かに例えられ得る。
【００１４】
本開示の実施形態は、添付の図面を参照して説明される。
【００１５】
図１Ａは、本開示の少なくとも１つの実施形態に従って用意された、ＧＵＩに基づくアプリケーション１０２の決定性有限状態機械（ｄｅｔｅｒｍｉｎｉｓｔｉｃ  ｆｉｎｉｔｅ  ｓｔａｔｅ−ｍａｃｈｉｎｅ（決定性有限オートマン）：ＤＦＳＭ）モデル１０６を生成及び検証する例示のシステム１００を示す。ＧＵＩに基づくアプリケーション１０２は、電子装置に含まれ得る任意の適切なＧＵＩに基づくアプリケーションであり得る。電子装置は、制限されないが、タブレットコンピュータ、スマートフォン、ナビゲーションシステム、エンターテイメントシステム、デスクトップコンピュータ、ラップトップコンピュータ又はデジタルミュージックプレーヤ等を含み得る。
【００１６】
ＧＵＩに基づくアプリケーション１０２は、１つ又は複数の状態を含み得る。ＧＵＩに基づくアプリケーション１０２は、ＧＵＩに基づくアプリケーション１０２のＧＵＩ上で処理され得る動作に基づいて、状態間を遷移し得る。状態は、ＧＵＩに基づくアプリケーションの画面と関連しており、１つよりも多い状態が同じ画面と関連し得る。１つよりも多い状態が同じ画面と関連している時、状態間の違いは、ＧＵＩに基づくアプリケーション１０２のＧＵＩから直接観測され得ないＧＵＩに基づくアプリケーション１０２の隠れた動作に基づき得る。従って、ある例では、ＧＵＩに基づくアプリケーション１０２の異なる状態は、同じ状態にあるＧＵＩに基づくアプリケーションのＧＵＩ上に直接観測され得る。上述し且つ後述されるように、隠れた動作は、ＧＵＩに基づくアプリケーション１０２に対して生成され得るモデル内に不一致を作り得る。
【００１７】
ある実施形態では、システム１００は、計算システム１０４を有し得る。計算システム１０４は、プロセッサ１０８及びメモリ１１０を有し得る。プロセッサ１０８は、様々なコンピュータ・ハードウェア又はソフトウェア・モジュールを含む、任意の適切な特別な目的又は多目的なコンピュータ、計算エンティティ、又は処理装置であり、且つ、任意の適用可能なコンピュータ可読媒体に格納された命令を実行するように構成され得る。例えば、プロセッサ１０８は、マイクロプロセッサ、マイクロコントローラ、デジタルシグナルプロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルアレイ（ＦＰＧＡ）、又は、プログラム命令をインタプリート（解釈）し及び／又は実行し、及び／又はデータを処理するように構成された任意の他のデジタル又はアナログ回路を含み得る。図１Ａでは単一のプロセッサが示されているが、プロセッサ１０８は、任意の数の処理を一緒に及び／又は個別に実行するように構成された任意の数のプロセッサを含み得る。
【００１８】
メモリ１１０は、内部に記憶されたコンピュータ実行可能な命令又はデータ構造を運ぶ又は有するコンピュータ可読媒体を含み得る。そのようなコンピュータ可読媒体は、多目的又は特別な目的のコンピュータによってアクセスされ得る任意の利用可能な媒体であり得る。例えば、制限されることなく、そのようなコンピュータ可読媒体は、コンピュータ実行可能な命令又はデータ構造の形で所望のプログラムコードを運ぶ又は記憶するために使用され、且つ多目的又は特別な目的のコンピュータによってアクセスされ得る、ランダムアクセスメモリ（ＲＡＭ）、リードオンリーメモリ（ＲＯＭ）、電気的イレイサブルプログラマブルリードオンリーメモリ（ＥＥＰＲＯＭ）、コンパクトディスクリードオンリーメモリ（ＣＤ−ＲＯＭ）又は他の光ディスクメモリ、磁気ディスクメモリ又は他の磁気記憶装置、フラッシュメモリ（例えばソリッドステートメモリ装置）又は他の任意の記憶媒体を含む非一時的なコンピュータ可読媒体を有し得る。上記の組み合わせは、また、コンピュータ可読媒体の範囲内に含まれ得る。コンピュータ実行可能な命令は、例えば、プロセッサ１０８に対して、所定の機能又は機能の群を実行させる命令及びデータを有し得る。
【００１９】
計算装置１０４は、ＧＵＩに基づくアプリケーション１０２を受け取るように構成され、且つ、ＧＵＩに基づくアプリケーション１０２のＤＦＳＭモデル１０６を生成するように構成され得る。ＤＦＳＭモデル１０６は、ＧＵＩに基づくアプリケーション１０２の動作及びＧＵＩに基づくアプリケーションの状態間の遷移を表し得る。ある実施形態では、計算装置１０４は、後述する図３の方法３００に従ってＤＦＳＭモデル１０６を生成するように構成され得る。
【００２０】
図２Ａは、本明細書で説明する少なくとも１つの実施形態に従って、それぞれがＧＵＩに基づくアプリケーション２０１（以下本明細書ではサンプルアプリケーション２０１と称される）の１つ又は複数の状態と関連付けられ得るサンプルアプリケーション２０１の様々な画面を示す。図２Ｂは、本明細書で説明する少なくとも１つの実施形態に従って、サンプルアプリケーション２０１の動作を表し得る例示のＤＦＳＭモデル２００（以下本明細書ではモデル２００と称される）を示す。ある実施形態では、サンプルアプリケーション２０１は、図１ＡのＧＵＩに基づくアプリケーションの例であり、モデル２００は、計算システム１０４によってサンプルアプリケーション２０１から生成され得るＤＦＳＭモデル１０６の例であり得る。
【００２１】
サンプルアプリケーション２０１は、ユーザが食べ物を得る近くの場所を見つけて、場所を位置付けるＧＵＩに基づくアプリケーションであり得る。例示として図２Ａに示されるように、サンプルアプリケーション２０１は、ホーム画面２０２、アバウト（ａｂｏｕｔ）画面２０４、サーチ画面２０６、情報画面２０８、結果画面２１０及びマップ画面２１２を含み得る。ホーム画面２０２は、ユーザがサンプルアプリケーション２０１に関する様々な操作を実行することを許容し得る様々なウィジェット（ｗｉｄｇｅｔ）を含み得る。アバウト画面２０４は、サンプルアプリケーション２０１に関する情報を提供し得る。サーチ画面２０６は、ユーザが食べ物を得る場所を探すことを許容し得る。情報画面２０８は、食べ物を提供し得る場所に関する情報を提供し得る。結果画面２１０は、サーチ画面２０６上で実行され得る探索の結果を提供し得る。マップ画面２１２は、結果画面２１０に含まれる位置を地図上に示し得る。異なる画面上で実行され得る異なる動作間の関係及び状態及び／又は画面間の関連する遷移は、モデル２００に対して下記に詳細に説明される。
【００２２】
例えば、モデル２００は、状態２２０においてラベル「ホーム」と示されるように、ホーム画面２０２と関連付けられ得る状態２２０を含み得る。モデル２００は、状態２２０から状態２３０への遷移辺２２４を含み得る。状態２３０は、状態２３０においてラベル「アバウト」と示されるように、アバウト画面２０４と関連づけられ得る。遷移辺２２４は、ユーザがホーム画面２０２上の「アバウト」ウィジェット２１４をタップすることに応答して、状態２２０及びホーム画面２０２から状態２３０及びアバウト画面２０４への遷移を示し得る。
【００２３】
モデル２００は、状態２２０から状態２３２への遷移辺２２６を含み得る。状態２３２は、状態２３２においてラベル「情報」と示されるように、情報画面２０８と関連づけられ得る。遷移辺２２６は、ユーザがホーム画面２０２上の「最近接」ウィジェット２１８をタップすることに応答して、状態２２０及びホーム画面２０２から状態２３２及び情報画面２０８への遷移を示し得る。モデル２００は、また、状態２３２から状態２２０へ戻る遷移辺２２８を含み得る。サンプルアプリケーション２０１が状態２３２にある時にユーザが情報画面２０８の「戻る」ウィジェット２２１をタップすることに応答して、遷移辺２２８は、状態２３２及び情報画面２０８から状態２２０及びホーム画面２０２への遷移を示し得る。モデル２００の自己遷移辺２２７は、ユーザが情報画面２０８上の「トグル（ＴＯＧＧＬＥ：留まる）」ウィジェット２２５をタップすることに応答して、サンプルアプリケーション２０１が状態２３２に留まることを示す。
【００２４】
また、モデル２００は、状態２２０から状態２３４への遷移辺２２９を含み得る。状態２３４は、状態２３４においてラベル「サーチ」と示されるように、サーチ画面２０６と関連づけられ得る。遷移辺２２９は、ユーザがホーム画面２０２上の「サーチ」ウィジェット２１６をタップすることに応答して、状態２２０及びホーム画面２０２から状態２３４及びサーチ画面２０６への遷移を示し得る。モデル２００は、また、状態２３４から状態２２０へ戻る遷移辺２３１を含み得る。遷移辺２３１は、サンプルアプリケーション２０１が状態２３４にある時にユーザがサーチ画面２０６上の「戻る」ウィジェット２２３をタップすることに応答して、状態２３４及びサーチ画面２０６から状態２２０及びホーム画面２０２への遷移を示し得る。
【００２５】
また、モデル２００は、状態２３４から状態２３８への遷移辺２３６を含み得る。状態２３８は、状態２３８においてラベル「結果」と示されるように、結果画面２１０と関連づけられ得る。遷移辺２３６は、ユーザがサーチ画面２０６上の「ファインド（ＦＩＮＤ：見つける）」ウィジェット２４２をタップすることに応答して、状態２３４及びサーチ画面２０６から状態２３８及び結果画面２１０への遷移を示し得る。モデル２００は、また、状態２３８から状態２３４へ戻る遷移辺２４０を含み得る。サンプルアプリケーション２０１が状態２３８にある時にユーザが結果画面２１０上の「戻る」ウィジェット２４４をタップすることに応答して、遷移辺２４０は、状態２３８及び結果画面２１０から状態２３４及びサーチ画面２０６へ戻る遷移を示し得る。
【００２６】
モデル２００は、また、状態２３８から状態２４６への遷移辺２４８を含み得る。状態２４６は、状態２４６においてラベル「マップ」と示されるように、マップ画面２１２と関連付けられ得る。ユーザが結果画面２１０上の「マップ」ウィジェット２５２をタップすることに応答して、遷移辺２４８は、状態２３８及び結果画面２１０から状態２４６及びマップ画面２１２への遷移を示し得る。モデル２００は、また、状態２４６から状態２３８へ戻る遷移辺２５０を含み得る。サンプルアプリケーション２０１が状態２４６にある時にユーザがマップ画面２１２上の「戻る」ウィジェット２５４をタップすることに応答して、遷移辺２５０は、状態２４６及びマップ画面２１２から状態２３８及び結果画面２１０へ戻る遷移を示し得る。
【００２７】
モデル２００は、また、状態２３８から状態２５６への遷移辺２５８を含み得る。状態２５６は、状態２５６においてラベル「情報」と示されるように、情報画面２０８と関連付けられ得る。ユーザが結果画面２１０上の「位置」ウィジェット２６２をタップすることに応答して、遷移辺２５８は、状態２３８及び結果画面２１０から状態２５６及び情報画面２０８への遷移を示し得る。モデル２００は、また、状態２５６から状態２３８への遷移辺２６０を含み得る。サンプルアプリケーション２０１が状態２５６にある時にユーザが情報画面２０８上の「戻る」ウィジェット２２１をタップすることに応答して、遷移辺２６０は、状態２５６及び情報画面２０８から状態２３８及び結果画面２１０への遷移を示し得る。ユーザが情報画面２０８上の「トグル」ウィジェット２２５をタップすることに応答して、モデル２００の自己遷移辺２６４は、サンプルアプリケーション２０１が状態２５６に留まることを示す。
【００２８】
図２Ａ及び図２Ｂに示されるサンプルアプリケーション２０１及びモデル２００は、単なる例示であり、制限されることを意味するものではない。本開示に従って、任意の数のＤＦＳＭモデルが、任意の数のＧＵＩに基づくアプリケーションに対して生成され得る。
【００２９】
図１Ａに戻って、ある実施形態では、ＤＦＳＭモデルの生成中に、計算システム１０４は、推測ＤＦＳＭモデル（推測モデル）を生成し得る。計算システム１０４は、推測モデルを検証して、推測モデルがＧＵＩに基づくアプリケーション１０２と実質的に一致するか否かを決定するように構成され得る。推測モデルが、ＧＵＩに基づくアプリケーション１０２と実質的に一致すると考えられる時、推測モデルは、ＤＦＳＭモデル１０６として出力され得る。ある実施形態では、計算システム１０４は、後述するように、図４Ａ及び図４Ｂの方法４００に従って、推測モデルを検証するように構成され得る。
【００３０】
ある実施形態では、計算システム１０４は、推測モデルの１つ又は複数の経路がＧＵＩに基づくアプリケーション１０２と一致しているか否かを決定することによって、推測モデルを検証するように構成され得る。経路がＧＵＩに基づくアプリケーション１０２と一致しているか否かを決定することは、また、経路を検証することとも称され得る。本実施形態又は他の実施形態では、推測モデルの複数の経路は、優先順位付けスキーム（ｐｒｉｏｒｉｔｉｚａｔｉｏｎ  ｓｃｈｅｍｅ）に従って順序づけられ得る。
優先順位付けスキームは、どの経路が最初に検証されるかを決定する。
【００３１】
ある実施形態では、経路の優先順位付けは、どの経路が１つ又は複数のルールパターンを満たすパターンを含むかに基づき得る。ルールパターンは、パターンによって示され得る、推測モデル内の潜在的な不正確さに基づき得る。上述したように、推測モデル内の不正確さは、ＧＵＩに基づくアプリケーション１０２内の隠された動作により得る。従って、ある実施形態では、ルールパターンは、ＧＵＩに基づくアプリケーション１０２の隠された動作を示し得る推測モデルのトポロジー（ｔｏｐｏｌｏｇｙ）内の潜在的なパターンに基づき得る。本実施形態及び他の実施形態では、１つ又は複数のルールパターンは、ＧＵＩに基づくアプリケーション１０２の複数の状態が推測モデルにおける単一の状態によって表される時の例を示す。
【００３２】
図１Ｂは、本明細書で説明する少なくとも１つの実施形態に従って、例示のルールパターン１１１を示す。ルールパターン１１１は、推測モデルのトポロジー内に潜在的に現れ、且つ必要ではないが、ＧＵＩに基づくアプリケーション１０２の隠れた動作を示すパターンを含み得る。従って、ある実施形態では、ルールパターン１１１は、推測モデルとＧＵＩに基づくアプリケーション１０２との間の不一致を示し得る。ルールパターン１１１は、第１状態１１２、第２状態１１４及び第３状態１１６を含み得る。ルールパターン１１１は、動作ａに応答して、第１状態１１２から第２状態１１４への遷移が起こり、動作ｂに応答して、第２状態１１４から第３状態１１６への遷移が起こり、動作ｃに応答して、第３状態１１６から第２状態１１４へ戻る遷移が起こり得るという、一連の動作「ａ→ｂ→ｃ」に従い得る。
【００３３】
ある例では、ルールパターン１１１は、ＧＵＩに基づくアプリケーション１０２の「戻る」操作と関連づけられ得る、ＧＵＩに基づくアプリケーション１０２の隠れた動作を示し得る。例えば、ＧＵＩに基づくアプリケーション１０２は、２つ以上の異なる状態が特定の画面と関連付けられ得るように、ＧＵＩに基づくアプリケーション１０２の２つ以上の異なる画面からＧＵＩに基づくアプリケーション１０２の特定の画面へ遷移し得る。従って、特定の状態に関して特定の画面上で「戻る」操作が実行される時、どの画面及び状態から特定の画面及び特定の状態への遷移が生じたのかに依存して、ＧＵＩに基づくアプリケーション１０２は、異なる画面及び状態へ遷移し得る。「戻る」操作に応答して、どの画面及び状態から特定の画面及び特定の状態への遷移に関するかを決定することは、ＧＵＩに基づくアプリケーション１０２のＧＵＩから隠れている動作を含み得る。
【００３４】
「戻る」操作と関連する隠れた動作のために、推測モデルは、推測モデルが「戻る」操作と関連する動作を不正確に表し得るというような単一の状態として、ＧＵＩに基づくアプリケーション１０２の複数の状態を表し得る。例えば、推測モデルは、第２状態１１４がＧＵＩに基づくアプリケーション１０２の複数の状態を表すように、一連の動作「ａ→ｂ→ｃ」における動作「ｂ」が「戻る」操作と関連づけられ得るルールパターン１１１を含み得る。従って、推測モデルは、「戻る」操作に応答して第１状態１１２へ戻る代わりに、「戻る」操作に応答してＧＵＩに基づくアプリケーション１０２が第２状態１１４から第３状態１１６へ遷移し得るというように不正確に表し得る。
【００３５】
図１Ｃは、本明細書で説明する少なくとも１つの実施形態に従って、例示のルールパターン１１８を示す。図１Ｂのルールパターンと同様に、ルールパターン１１８は、推測モデルのトポロジー内に潜在的に現れ、且つ必要ではないが、ＧＵＩに基づくアプリケーション１０２の隠れた動作を示すパターンを含み得る。従って、ある実施形態では、ルールパターン１１８も、推測モデルとＧＵＩに基づくアプリケーション１０２との間の不一致を示し得る。
【００３６】
ルールパターン１１８は、第１状態１２０、第２状態１２２、第３状態１２４及び第４状態１２６を含み得る。第２状態１２２及び第３状態１２４は、同じ潜在的な動作を含み得る、例えば、第２状態１２２及び第３状態１２４は、ＧＵＩに基づくアプリケーション１０２の同じ画面と関連付けられ得る。ルールパターン１１８は、動作ａに応答して、第１状態１２０から第２状態１２２への遷移が起こり、動作ｃに応答して、第２状態１２２から第３状態１２４への遷移が起こり、動作ｅに応答して、第３状態１２４から第４状態１２６への遷移が起こり得るという、一連の動作「ａ→ｃ→ｅ」に従い得る。
【００３７】
ルールパターン１１８は、ＧＵＩに基づくアプリケーションに対応する一画面が第２状態１２２及び第３状態１２４によって表され、且つ、画面がＧＵＩに基づくアプリケーションを同じ画面及び自己ループにおいて同じ状態に留めさせ得る動作ｃをサポートするという潜在的な不一致を表し得る。しかし、ある実施形態では、この動作は、ルールパターン１１８に示されるように、画面（例えば第２状態１２２）と関連付けられるある状態から画面（例えば第３状態）と関連付けられる他の状態への遷移として推測モデルにおいて不正確に表され得る。これと対称的に、この動作の一貫して正しいモデルでは、同じ画面と関連付けられる２つの状態のそれぞれは、動作ｃと関連づけられる自己ループを有し得る。
【００３８】
図１Ａに戻って、ある実施形態では、計算システム１０４は、特異性（ｓｐｅｃｉｆｉｃｉｔｙ）に基づいて、ルールパターンを分類するように構成され得る。特異性は、ルールパターンに従う経路がＧＵＩに基づくアプリケーション１０２とどのくらい不一致にあるのかに関係し得る。例えば、図１Ｂのルールパターン１１１に従う経路のより高いパーセンテージは、図１Ｃのルールパターン１１８に従う経路のパーセンテージよりも、ＧＵＩに基づくアプリケーション１０２とより一致する。従って、ルールパターン１１８は、ルールパターン１１１よりも特異度がより高いと考えられ得る。
【００３９】
計算システム１０４は、ルールパターンの順序づけられた特異性に基づいて、推測モデルの経路を検証するように構成され得る。例えば、計算システム１０４は、どの経路がルールパターン１１１を満たすかを決定し且つこれらの対応する経路を検証する前に、推測モデルのどの経路がルールパターン１１８を満たすかを判断し、且つこれらの経路を検証するように構成され得る。従って、早期に不一致を決定する可能性が、増加され得る。
【００４０】
本実施形態又は他の実施形態では、計算システム１０４は、推測モデルの１つ又は複数の経路に対する１つ又は複数の優先順位の重みを決定するように構成され得る。ある実施形態では、優先順位の重みは、経路に適用される１つ又は複数の発見的問題解決法（ｈｅｕｒｉｓｔｉｃｓ：ヒューリスティックス）に基づき得る。発見的問題解決法は、潜在的な不一致が生じ得ることを示し得る経路の性質に基づき得る。
【００４１】
例えば、推測モデルにおけるある状態と関連する多数の入力辺は、状態がＧＵＩに基づくアプリケーション１０２の複数の状態を表すことを示し得る。従って、ある実施形態では、発見的問題解決法は、複数の経路の１つ又は複数の状態と関連する複数の入力辺を含み得る。１つ又は複数の対応する状態と関連するより多数の入力辺を有する経路には、より高い優先順位の重みが与えられ得る。
【００４２】
計算システム１０４は、また、優先順位の重みに基づいて、推測モデルの経路を検証するように構成され得る。例えば、計算システム１０４は、低い優先順位の重みを有する経路を検証する前に、高い優先順位の重みを有する経路を検証するように構成され得る。ある実施形態では、特定のルールパターンを満たす経路は、それぞれの経路の優先順位の重みに基づいている順番で検証され得る。
【００４３】
このように、システム１００は、ＧＵＩに基づくアプリケーションのＤＦＳＭモデルを生成し且つ検証するように構成され得る。修正、追加又は省略は、本開示の範囲を逸脱することなくシステム１００に対してなされ得る。例えば、ルールパターン１１１及び１１８は、単に、推測モデルを検証するために使用され得る例示のルールパターンに過ぎない。他のルールパターンも、推測モデルを検証するために使用され得る。また、入力辺の数は、単に、経路の優先順位の重みを決定するために用いられ得る例示の発見的問題解決法に過ぎない。例えば、経路の長さは、優先順位付けの基準として使用され得る。本当に長い経路は、総計があまりに多く且つ検証するのにかなり高価（ｅｘｐｅｎｓｉｖｅ）である一方で、短い経路は、不一致を露出させるのに実質的に十分な動作をカバーしないだろう。従って、中間の長さが好まれる非単調優先準位付けスキーム（ｎｏｎ−ｍｏｎｏｔｏｎｉｃ  ｐｒｉｏｒｉｔｉｚａｔｉｏｎ  ｓｃｈｅｍｅ）が使用され得る。
【００４４】
他の発見的問題解決法は、以前に調べられた経路の内の最長のサブシーケンス（ｓｕｂ−ｓｅｑｕｅｎｃｅ：部分列）の長さに基づいて、経路の優先順位付けを行うことであり得る。サブシーケンスが小さい程、この経路は、実質的に新しい動作を探索する可能性があり且つ不一致を露呈する可能性があり得る。また、他の発見的問題解決法は、不一致な動作としばしば関係するあらかじめ定義された動作のセットから１つ又は複数の動作のインスタンス（ｉｎｓｔａｎｃｅ：例）を含む経路を優先することであり得る。「戻る」動作は、そのような動作の一例である。
【００４５】
図３は、本明細書で説明する少なくとも１つの実施形態に従って、ＧＵＩに基づくアプリケーションのＤＦＳＭモデルを生成する例示の方法３００のフローチャートである。方法３００は、図１Ａの計算システム１０４のような計算システムによって、ある実施形態では組み込まれ得る。例えば、計算システム１０４のプロセッサ１０８は、方法３００の１つ又は複数のブロックによって表されるように、ＧＵＩに基づくアプリケーション１０２のＤＦＳＭモデル１０６を生成するための動作を実行するべく、メモリ１１０に格納されるコンピュータ命令を実行するように構成され得る。離散的なブロックとして示さているけれども、各ブロックは、所望の実装に依存して、追加の複数のブロックに分割されたり、より少数のブロックに結合されたり、又は省略され得る。
【００４６】
方法３００は、ブロック３０２において、ＧＵＩに基づくアプリケーション「ａｐｐ」を受け取ると開始し得る。例えば、図１ＡのＧＵＩに基づくアプリケーション１０２は、ブロック３０２において受け取られる。ブロック３０４では、「ａｐｐ」は、クロールされて、「ａｐｐ」の動作「ｂ」が観測され且つ抽出され得る。クロールは、「ａｐｐ」のＧＵＩにおける変化によって示されるように、クローラが「ａｐｐ」の動作「ｂ」を記録し且つ観測し得るように、「ａｐｐ」のＧＵＩを介して「ａｐｐ」と自動的に相互作用し得る任意の適切なクローラ（例えば動的クローラ）によって実行され得る。
【００４７】
ブロック３０６では、推測モデルである「ａｐｐ」の「モデル」が、動作「ｂ」から学習され得る。学習は、受動的学習エンジン又は能動的学習エンジンであり得る任意の適切な学習エンジン（ｌｅａｒｎｉｎｇ  ｅｎｇｉｎｅ）によって実行され得る。受動的学習エンジンは、受動的学習エンジンからの入力なしにクローラによって観測され得る動作「ｂ」に基づいて、「モデル」を生成し得る。対称的に、能動的学習エンジンは、能動的学習エンジンが動作「ｂ」の抽出に対応する入力を提供するように、動作「ｂ」の生成において１つ又は複数の「ａｐｐ」の部分をクロールするようにクローラを導き得る。
【００４８】
ブロック３０８では、「モデル」が実質的に「ａｐｐ」と等しいか否かが決定され得る。上述したように、「モデル」が実質的に「ａｐｐ」と等しいか否かを決定することは、「モデル」が「ａｐｐ」の動作を正確に表すか否かに関する決定であり得る。ある実施形態では、ブロック３０８において実行された決定は、図４Ａ及び４Ｂに関して後述される方法４００に従って実行され得る。「モデル」が「ａｐｐ」と実質的に等しくない時、「モデル」と「ａｐｐ」との間の不一致「ｐ」が観測されて、方法３００はブロック３０８からブロック３１０へ進み得る。ある実施形態では、不一致「ｐ」は、方法４００と関連する１つ又は複数の動作に従って確認され得る。「モデル」が「ａｐｐ」と実質的に等しい時、方法３００は、ブロック３０８からブロック３１４へ進み得る。
【００４９】
ブロック３１０では、不一致「ｐ」は、読み出され得る。ブロック３１２では、動作「ｂ」は、不一致「ｐ」に関して、拡張され得る。例えば、ある実施形態では、不一致「ｐ」は、「モデル」における経路と一致しない「ａｐｐ」の経路であり得る。本実施形態及び他の実施形態では、不一致「ｐ」は、その後、クローラへ与えられる反例として使用され得る。そして、クローラは、「ａｐｐ」の追加の動作が観測され且つ抽出され得るように、不一致「ｐ」に基づいて「ａｐｐ」をクロールし得る。追加の動作は、動作「ｂ」が不一致「ｐ」に関して実質的に拡張され得るように、動作「ｂ」に追加され得る。ブロック３１２に続いて、方法３００は、新しい推測モデル「モデル」が拡張された動作「ｂ」に基づいて学習され得るブロック３０６へ戻り得る。
【００５０】
ブロック３１４では、「モデル」が実質的に「ａｐｐ」と等しい時、「モデル」は「ａｐｐ」の検証されたＤＦＳＭモデルとして出力され得る。例えば、図１Ａに関して、ＤＦＳＭモデル１０６は、ＧＵＩに基づくアプリケーション１０２の検証されたモデルとして、ブロック３１４において出力され得る。
【００５１】
このように、方法３００は、ＧＵＩに基づくアプリケーションのＤＦＳＭモデルを生成するために使用され得る。修正、追加又は省略は、本開示の範囲を逸脱することなく方法３００に対してなされ得る。例えば、当業者は、方法３００に対して、実行される機能が異なる順番で実装され得ることを認識するだろう。更に、概説されたステップ及び動作は、例として提供されるだけであり、開示された実施形態を損なうことなく、いくつかのステップ及び動作は、任意であり、より少ないステップ及び動作に結合されるか、又は、追加のステップ及び動作に拡張され得る。例えば、ブロック３０８において実行される動作は、図４Ａ及び４Ｂに関して後述されるように、任意の数の追加の動作を含み得る。
【００５２】
図４Ａ及び４Ｂは、本明細書で説明する少なくとも１つの実施形態に従って配置された、ＧＵＩに基づくアプリケーションのＤＦＳＭモデルを検証する例示の方法４００のフローチャートを示す。上述したように、方法４００は、上記方法３００のブロック３０８及び３１０に関連する１つ又は複数の動作を実行するために使用され得る。方法４００は、ある実施形態では、図１の計算システム１０４のような、計算システムによって実装され得る。例えば、計算システム１０４のプロセッサ１０８は、方法４００の１つ又は複数のブロックによって表されるように、ＧＵＩに基づくアプリケーション１０２のＤＦＳＭモデルを検証する動作を実行するべく、メモリ１１０内に格納されるコンピュータ命令を実行するように構成され得る。離散的なブロックとして示さているけれども、各ブロックは、所望の実装に依存して、追加の複数のブロックに分割されたり、より少数のブロックに結合されたり、又は省略され得る。
【００５３】
方法４００は、ＧＵＩに基づくアプリケーション「ａｐｐ」が受け取られ得る、ブロック４０２において開始し得る。例えば、図１のＧＵＩに基づくアプリケーション１０２が、読み出され得る。上述したように、ある実施形態では、図４Ａ及び４ＢのＧＵＩに基づくアプリケーション「ａｐｐ」は、図３の同じＧＵＩに基づくアプリケーション「ａｐｐ」を含み得る。
【００５４】
ブロック４０４では、推測モデル「モデル」が受け取られ得る。上述したように、推測モデル「モデル」は、図３のブロック３０６で学習され得る推測モデル「モデル」を含み得る。
【００５５】
ブロック４０６では、一組のルールパターン「ルール」が受け取られ得る。一組のルールパターン「ルール」は、推測モデル「モデル」における潜在的な不正確さを示し得る１つ又は複数のパターンを含み得る。例えば、一組のルールパターン「ルール」は、図１Ｂ及び１Ｃに関して上述したようにルールパターン１１１及び１１８それぞれを含み得る。また、ある実施形態では、一組のルールパターン「ルール」は、特異性に従って、分類され得る。
【００５６】
ブロック４０８では、推測モデル「モデル」の実行されていない一組の経路「ｐａｔｈＳｅｔ」が受け取られ得る。本開示では、経路がまだ検証されていない時、その経路は、方法４００の文脈において、実行されていないと考えられ得る。例えば、「ａｐｐ」上で以前に実行され且つ推測モデル「モデル」を学習するために直接使用された経路は、検証されたものとして考えられ得る。ブロック４１０では、優先順位の重みが「ｐａｔｈＳｅｔ」内の経路に対して決定され得る。ある実施形態では、優先順位の重みは、上述したように、１つ又は複数の発見的解決法に基づいて、決定され得る。例えば、優先順位の重みは、「ｐａｔｈＳｅｔ」内の経路の１つ又は複数の状態への入力辺の数に基づいて、決定され得る。
【００５７】
ブロック４１２では、一組のルールパターン「ルール」内に適用されていないルールパターンがあるか否かが決定され得る。本開示では、方法４００の文脈において、推測モデル「モデル」の１つ又は複数の経路が特定のルールパターンを含むか否かが決定されていない時、特定のルールパターンは、「適用されていない」ことと考慮され得る。一組のルールパターン「ルール」が１つ又は複数の適用されていないルールパターンを含む時、方法４００はブロック４１４へ進み得る。
【００５８】
ブロック４１４では、次の適用されていないルールパターン「ｒ」が一組のルールパターン「ルール」から読みだされ得る。ブロック４１６では、「ｐａｔｈＳｅｔ」内の経路がルールパターン「ｒ」と一致するか否かが決定され得る。本開示では、経路がルールパターンと一致するパターンを含む時、経路は、「ルールパターンと一致する」又は「ルールパターンを満たす」と考えられ得る。「ｐａｔｈＳｅｔ」内の１つ又は複数の経路がルールパターン「ｒ」と一致する時、方法４００はブロック４１８へ進む。「ｐａｔｈＳｅｔ」内の経路がルールパターン「ｒ」と一致しない時、方法４００はブロック４１２へ戻る。
【００５９】
ブロック４１８では、ルールパターン「ｒ」と一致する「ｐａｔｈＳｅｔ」からの経路（「一致（ｍａｔｃｈｅｓ）」）が受け取られる。ブロック４２０では、「一致」に含まれる経路が、それらの優先順位の重みに従って分類される。ブロック４２２では、「一致」が実行されていない経路を含むか否かが決定され得る。「一致」が１つ又は複数の実行されていない経路を含む時、方法４００はブロック４２４へ進み得る。「一致」が１つ又は複数の実行されていない経路を含まない時、方法４００はブロック４１２へ進み得る。
【００６０】
ブロック４２４では、「一致」からの次の実行されていない経路「ｐ」が選択され得る。ブロック４２６では、経路「ｐ」が「ａｐｐ」と一致するか否かが決定され得る。経路「ｐ」が「ａｐｐ」と一致しない時、方法４００はブロック４２８へ進み得る。ブロック４２８では、経路「ｐ」は「ａｐｐ」に関して一致しないと出力され得る。ある実施形態では、経路「ｐ」は、次に、上述した方法３００のブロック３１０及び３１２の不一致「ｐ」として機能し得る。
【００６１】
ブロック４２６において経路「ｐ」が「ａｐｐ」と一致する時、方法４００は、ブロック４２２へ戻り得る。ブロック４２６において不一致が見つけられるまでか、又は、「ルール」内の適用されていない「ルールパターン」がもはやないとブロック４１２において決定されるまで、１つ又は複数のブロック４１２，４１４，４１６，４１８，４２０，４２２，４２４，４２６が繰り返され得る。上述したように、一組のルールパターン「ルール」が１つ又は複数の適用されていないルールパターンを含まない時、方法４００はブロック４３０へ進む「ルール」内のルールパターンを適用した後、方法４００がブロック４３０へ到着した時、推測モデルは「ａｐｐ」と実質的に等しいと考えられ得る。ブロック４３０では、そのように、推測モデルは「ａｐｐ」と実質的に等しいと決定され得る。方法３００のブロック３１４に関して上述したように、ある実施形態では、ブロック４３０において推測モデル「モデル」が「ａｐｐ」と実質的に等しいと決定された時、推測モデル「モデル」はＧＵＩに基づくアプリケーション「ａｐｐ」に対するＤＦＳＭモデルとして出力され得る。
【００６２】
修正、追加又は省略は、本開示の範囲を逸脱することなく方法４００に対してなされ得る。例えば、当業者は、方法４００に対して、実行される機能が異なる順番で実装され得ることを認識するだろう。更に、概説されたステップ及び動作は、例として提供されるだけであり、開示された実施形態を損なうことなく、いくつかのステップ及び動作は、任意であり、より少ないステップ及び動作に結合されるか、又は、追加のステップ及び動作に拡張され得る。例えば、ある実施形態では、特定のルールパターンを満たす特定の数の経路が検証されて、ブロック４２２、４２４及び４２６を介して不一致がないことが見つけられた後、方法４００は、特定のルールパターンを満たす全ての経路が検証されていなくとも、ブロック４１２上へ移動し得る。
【００６３】
上述したように、方法３００及び４００は、ＧＵＩに基づくアプリケーションに対するＤＦＳＭモデルを生成し且つ検証するために使用され得る。例えば、図５Ａは、図２Ａのサンプルアプリケーション２０１の例示の推測モデル５００ａを示す。推測モデル５００ａは、方法３００のブロック３０２、３０４及び３０６を用いて生成され得る。また、方法４００の１つ又は複数のブロックは、推測モデル５００ａがサンプルアプリケーション２０１と実質的に等しいか否かを検証するために使用され得る。
【００６４】
例えば、ある実施形態では、図１Ａの計算システム１０４は、サンプルアプリケーション２０１、推測モデル５００ａ及び一組のルールパターンを、方法４００のブロック４０２、４０４及び４０６毎に受け取り得る。一組のルールパターンは、図１Ｂ及び１Ｃそれぞれのルールパターン１１１を含み得る。また、ルールパターン１１８は上述したようにルールパターン１１１よりも特異であり得るので、一組のルールパターンは、ルールパターン１１８がルールパターン１１１の上に（ｏｖｅｒ  ｔｈｅ  ｒｕｌｅ−ｐａｔｔｅｒｎ  １１１）、優先順位づけられ得るという特異性に基づいて順番付けされ得る。
【００６５】
また、方法４００のブロック４０８及び４１０毎に、計算システム１０４は、推測モデル５００ａの実行されていない経路を決定し、推測モデル５００ａの実行されていない経路に対する優先順位の重みを計算し得る。図示の例では、優先順位の重みは、実行されていない経路の状態に関して、入力辺の数に基づいて決定され得る。
【００６６】
ブロック４１２、４１４及び４１６毎に、計算システム１０４は、まず、一組のルールパターンからのルールパターン１１８を読み出し、推測モデル５００ａ内の経路がルールパターン１１８と一致するか否かを決定し得る。図示の例では、ルールパターン１１８と一致する経路が推測モデル５００ａ内には存在しないだろう。従って、計算システムは、次に、一組のルールパターンからのルールパターン１１１を読みだし、推測モデルの経路がルールパターン１１１と一致するか否かを決定し得る。図示の実施形態では、推測モデル５００ａは、ルールパターン１１１と一致する３４経路を含み得る。計算システム１０４は、ルールパターン１１８及び１１１の優先順位付けに基づいて示される順番で、ルールパターン１１８及び１１１を適用しようとし得る。
【００６７】
ブロック４１８及び４２０毎に、計算システム１０４は、ルールパターン１１１と一致する経路を読み出し、それらの優先順位の重みに従ってそれらに順番付けし得る。例えば、下記の表１は、ルールパターン１１１と一致する３４経路の内のトップ１０（最大の優先順位の重みに従って）の動作列を含む。
【００６８】
【表１】
2016004576.tif 000003
【００６９】
ブロック４２２及び４２４毎に、計算システム１０４は、優先順位の重みに基づき得る経路の順番に基づいて、まず、表１に示される経路「１」を選択し、経路「１」がサンプルアプリケーション２０１と一致するか否かを決定し得る。ブロック４２６毎に、計算システム１０４は、経路「１」がサンプルアプリケーション２０１と一致するか否かを決定し得る。図示の例では、経路「１」は、サンプルアプリケーション２０１と一致し得る。従って、計算システム１０４は、サンプルアプリケーション２０１に関して一致するものとして、経路「１」を出力し得る。
【００７０】
経路「１」と関連した不一致に基づいて、ある実施形態では、計算システム１０４は、方法３００へ戻り、ブロック３１０、３１２及び３０６毎に新しい推測モデルを生成し得る。図５Ｂは、経路「１」と関連した不一致に基づいて生成され得る図２Ｂのサンプルアプリケーション２０１の例示の推測モデル５００ｂを示す。
【００７１】
計算システム１０４は、次に、方法４００へ戻り、サンプルアプリケーション２０１、推測モデル５００ｂ及び方法４００のブロック４０２、４０４及び４０６毎に一組のルールパターンを受け取り得る。推測モデル５００ａに関する方法４００のアプリケーションと同様に、一組のルールパターンは、図１Ｂ及び１Ｃそれぞれのルールパターン１１１及び１１８を含み得る。また、一組のルールパターンは、ルールパターン１１８が上述したようにルールパターン１１１よりも特異であるので、ルールパターン１１８がルールパターン１１１の上に優先順位付けされ得る特異性に基づいて順序づけられ得る。
【００７２】
方法４００のブロック４０８及び４１０毎に、計算システム１０４は、推測モデル５００ｂの実行されていない経路を決定し、推測モデル５００ｂの実行されていない経路に対する優先順位の重みを計算し得る。図示の例では、優先順位の重みは、実行されていない経路の状態に関する入力辺の数に基づいて決定され得る。
【００７３】
ブロック４１２、４１４及び４１６毎に、計算システム１０４は、まず、一組のルールパターンからのルールパターン１１８を読み出し、推測モデル５００ｂ内の経路がルールパターン１１８と一致するか否かを決定し得る。図示の例では、「最近接」→「トグル」→「戻る」という動作列に従う推測モデル５００ｂの経路５０３は、ルールパターン１１８と一致し得る。ブロック４１８毎に、計算システム１０４は、ルールパターン１１８と一致する経路５０３を読み出し得る。図示の例では、経路５０３はルールパターン１１８に従うただ１つの経路なので、ブロック４２０は、スキップされ得る。
【００７４】
ブロック４２２、４２４及び４２６毎に、計算システム１０４は、経路５０３がサンプルアプリケーション２０１と不一致であるか否かを決定し得る。図示の例では、経路５０３は、サンプルアプリケーション２０１と不一致であり得る。従って、計算システム１０４は、サンプルアプリケーション２０１に関して不一致するものとして経路５０３を出力し得る。
【００７５】
ある実施形態では、経路５０３に関連する不一致に基づいて、計算システム１０４は、方法３００に戻り、ブロック３１０、３１２及び３０６毎に新しい推測モデルを生成し得る。ある実施形態では、計算システム１０４は、推測モデルとして、図２Ａのモデル２００を出力し得る。計算システム１０４は、次に、方法４００をモデル２００に適用して、モデル２００がサンプルアプリケーション２０１と実質的に等しいと決定し得る。そのように、計算システム１０４は、サンプルアプリケーション２０１のＤＦＳＭモデルとして、モデル２００を出力し得る。
【００７６】
サンプルアプリケーションに対する上述した説明は、単なる例であり、制限することを意味するものではない。また、ステップの順番は、単なる例である。関係するステップ及び処理は、異なる順番で処理され、より多くの又はより少ないステップを含み得る。
【００７７】
当業者は、本明細書に説明されるこの手順及び方法並びに他の手順及び方法に対して、処理及び方法で実行される機能は、他の順番で実装され得ることを認識するだろう。更に、概説されたステップ及び動作は、例として提供されるだけであり、開示された実施形態を損なうことなく、いくつかのステップ及び動作は、任意であり、より少ないステップ及び動作に結合されるか、又は、追加のステップ及び動作に拡張され得る。
【００７８】
上述したように、ここに説明される実施形態は、より詳細には後述されるように様々なコンピュータ・ハードウェア又はソフトウェア・モジュールを含む特別な目的又は多目的なコンピュータ（例えば図１のプロセッサ１０８）の使用を含み得る。
【００７９】
また、上述したように、ここに説明される実施形態は、内部に記憶されたコンピュータ実行可能な命令又はデータ構造を運ぶ又は有するコンピュータ可読媒体（例えば図１のメモリ１１０）を用いて、実装され得る。そのようなコンピュータ可読媒体は、多目的又は特別な目的のコンピュータによってアクセスされ得る任意の利用可能な媒体であり得る。例えば、制限されることなく、そのようなコンピュータ可読媒体は、コンピュータ実行可能な命令又はデータ構造の形で所望のプログラムコードを運ぶ又は記憶するために使用され、且つ多目的又は特別な目的のコンピュータによってアクセスされ得る、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、ＣＤ−ＲＯＭ又は他の光ディスクメモリ、磁気ディスクメモリ又は他の磁気記憶装置、フラッシュメモリ（例えばソリッドステートメモリ装置）又は他の任意の記憶媒体を含む非一時的なコンピュータ可読媒体を有し得る。上記の組み合わせは、また、コンピュータ可読媒体の範囲内に含まれ得る。
【００８０】
コンピュータ実行可能な命令は、例えば、多目的のコンピュータ、特別な目的のコンピュータ、又は特別な目的の処理装置（例えば１つ又は複数のプロセッサ）に対して、所定の機能又は機能の群を実行させる命令及びデータを有し得る。主題は、特有の言語において構造的な特徴及び／又は方法論的な行為に対して説明されているが、添付の請求項において定義される主題は、上述された特別な特徴又は行為に制限される必要のないことを理解されたい。むしろ、上述された特別な特徴及び行為は、請求項を実装する例示の形として開示される。
【００８１】
本明細書では、「モジュール」又は「構成要素（コンポーネント）」という用語は、モジュール又は構成部品の動作、及び／又は、コンピュータシステムの多目的なハードウェア（例えばコンピュータ可読媒体、処理装置等）によって記憶及び／又は実行され得るソフトウェアオブジェクト又はソフトウェアルーチンを実行するように構成された特定のハードウェアの実装に言及し得る。ある実施形態では、本明細書で説明される異なる構成要素、モジュール、エンジン及びサービスは、コンピュータシステム上で実行するオブジェクト又は処理（例えば、分離したスレッドとして）として実装され得る。本明細書で説明されるシステム及び方法は、ソフトウェア（多目的のハードウェアによって記憶及び／又は実行される）で実装されることが好ましいが、特定のハードウェアの実装、又はソフトウェア及びハードウェアの組み合わせにおける実装も可能であり且つ考慮される。本明細書の記載では、「コンピューティングエンティティ（計算実体）」は、上述したように本明細書で定義されるように任意の計算システム、又は任意のモジュール、又はコンピュータシステム上で動作するモジュールの組み合わせであり得る。
【００８２】
ここで述べられた全ての例及び条件付きの言葉は、読者が、発明者によって寄与された発明及び概念を技術を深めて理解することを助けるための教育的な目的を意図しており、そのような具体的に述べられた例及び条件に限定されることなく解釈されるべきである。本発明の実施形態は詳細に説明されているが、その様々な変更、置き換え又は修正が本発明の精神及び範囲を逸脱しない限り行われ得ることが理解されるべきである。
【図１Ａ】
2016004576.tif 000004
【図１Ｂ】
2016004576.tif 000005
【図１Ｃ】
2016004576.tif 000006
【図２Ａ】
2016004576.tif 000007
【図２Ｂ】
2016004576.tif 000008
【図３】
2016004576.tif 000009
【図４Ａ】
2016004576.tif 000010
【図４Ｂ】
2016004576.tif 000011
【図５Ａ】
2016004576.tif 000012
【図５Ｂ】
2016004576.tif 000013