(57)【要約】【課題】フラットで巨大なステートチャートを、人間が理解しやすいように自動的に、階層化・並列化されたステートチャート図を求める、階層化・並列化装置を提供する。【解決手段】対象となるフラットな元のステートチャート図を入力し、元のステートチャート図の全ての遷移を、それぞれ結果となる２つのステートチャート図のどちらか、もしくは両方に振分け、階層化もしくは並列化したステートチャート図のペアを候補リストとして生成する階層化・並列化候補生成部を備え、候補リストを用いて、階層化・並列化されたステートチャート図を求める。【選択図】図９
2015153275.tif 000002
【特許請求の範囲】
【請求項１】
対象となるフラットな元のステートチャート図を入力し、
前記元のステートチャート図の全ての遷移を、それぞれ結果となる２つのステートチャート図のどちらか、もしくは両方に振分け、階層化もしくは並列化したステートチャート図のペアを候補リストとして生成する階層化・並列化候補生成部を備え、
前記候補リストを用いて、階層化・並列化されたステートチャート図を求める、階層化・並列化装置。
【請求項２】
前記候補リストについて、保守性が高いか否かを判定し、保守性の高いものを高保守性候補リストとして生成する不適格候補棄却部と、
前記高保守性候補リストについて、より保守性の高いものに絞り込み、最適候補リストとして生成する最適候補選択部とを備える請求項１に記載の階層化・並列化装置。
【請求項３】
前記階層化は、
前記ステートチャート図の現在の状態が、ある状態であるとき、その状態の中で、さらに詳細なステートチャート図を入れ子にして記述する通常階層化、あるいは、履歴状態もしくは深履歴状態が置かれた履歴階層化に類型化し、
前記履歴状態は、最後にその置かれた階層から出た時の、その階層の状態を表し、
前記深履歴状態は、最後にその置かれた階層から出た時の、その階層とその全ての下位階層の状態を表す請求項１又は請求項２に記載の階層化・並列化装置。
【請求項４】
前記階層化・並列化候補生成部は、階層化と並列化が可能な場合には階層化を優先する請求項１乃至請求項３のいずれか1項に記載の階層化・並列化装置。
【請求項５】
前記不適格候補棄却部は、
前記ステートチャート図のペアが、同時に起こることの無い状態で同じイベントを受ける遷移が存在する場合には、保守性が低いと判定する低保守性判定部と、
前記ステートチャート図のペアが、前記通常階層化の場合以外で、同じイベントを結果となる両方のステートチャート図が同時に受け取るものを不適と判定する不適判定部で構成する請求項２乃至請求項４のいずれか1項に記載の階層化・並列化装置。
【請求項６】
前記最適候補選択部は、前記ステートチャート図のペアについて保守性に関する指標値を利用して絞り込みを行う請求項２乃至請求項４のいずれか1項に記載の階層化・並列化装置。
【請求項７】
前記保守性に関する指標値は、依存関係のある並列化＜依存関係が無い並列化＜履歴階層化＜通常階層化の順に重み付けする請求項６に記載の階層化・並列化装置。
【請求項８】
前記元のステートチャート図を示すステートチャートデータを格納するステートチャートデータ格納部と、
前記候補リストを格納する候補リスト格納部と、
前記最適候補リストを格納する最適候補リスト格納部を備える請求項１乃至請求項７のいずれか1項に記載の階層化・並列化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、階層化・並列化されたステートチャート図を求める、階層化・並列化装置に関する。
【背景技術】
【０００２】
ステートチャート図は、システム等に存在する状態やシステムの状態変化に着目した図で、特定のシステムに注目して、その生成から消滅までのライフサイクルをモデリングする。ステートチャート図は、各種のシステムにおける状態遷移を表すのに好適である。
【０００３】
特に、ステートチャート図での設計経験の浅い設計者が作成するステートチャート図は、階層や並列表現を含まない巨大でフラットとなる傾向があり、読解性・理解性等の保守性が悪い、という問題があった。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１１−１２３５８８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明が解決しようとする課題は、フラットで巨大なステートチャートを、人間が理解しやすいように自動的に、階層化・並列化されたステートチャート図を求める、階層化・並列化装置を提供することである。
【課題を解決するための手段】
【０００６】
実施形態の階層化・並列化装置は、対象となるフラットな元のステートチャート図を入力し、前記元のステートチャート図の全ての遷移を、それぞれ結果となる２つのステートチャート図のどちらか、もしくは両方に振分け、階層化もしくは並列化したステートチャート図のペアを候補リストとして生成する階層化・並列化候補生成部を備え、前記候補リストを用いて、階層化・並列化されたステートチャート図を求める。
【図面の簡単な説明】
【０００７】
【図１】ＵＭＬによるステートチャート図を示す図である。
【図２】本実施形態におけるステートチャート図の階層化を説明する図である。
【図３】本実施形態におけるステートチャート図の通常階層化を説明する図である。
【図４】本実施形態におけるステートチャート図の履歴階層化を説明する図である。
【図５】本実施形態におけるステートチャート図の並列化を説明する図である。
【図６】並列化の特殊ケース１を説明する図である。
【図７】並列化の特殊ケース２を説明する図である。
【図８】複数の候補の生成を説明する図である。
【図９】本発明の実施形態に係る階層化・並列化装置の概略構成を示すブロック図である。
【図１０】本実施形態において表れる各データの構造を示す図である。
【図１１】動作例の説明において使用する元となるステートチャート図を示す図である。
【図１２】図１１の動作例に示すステートチャート図におけるデータ構造を示す図である。
【図１３】図１１に示す動作例において、初期状態の作成を説明する図である。
【図１４】動作例の遷移「ＯＮ」を振り分けるパターンの作成を説明する図である。
【図１５】動作例の「冷房中」から「暖房中」への遷移「冷暖切替」を振り分けるパターンの作成を説明する図である。
【図１６】動作例の遷移「ＯＦＦ」を振り分けるパターンの作成を説明する図である。
【図１７】矛盾のチェックを説明する図である。
【図１８】パターン（i）、（iii）、（ii）に対して、動作例の「暖房中」から「冷房中」への遷移「冷暖切替」を振り分けるパターンの作成を説明する図である。
【図１９】パターン（i）、（iii）、（ii）、（iii）に対して、動作例の「暖房中」から「停止中」への遷移「ＯＦＦ」を振り分けるパターンの作成を説明する図である。
【図２０】遷移条件の整理を説明する図である。
【図２１】候補の階層化を説明する図である。
【図２２】結果となる候補リストを生成する階層化・並列化候補生成処理におけるデータ構造を表す図である。
【図２３】階層化・並列化候補生成処理の詳細例を示すフローチャートである。
【図２４】不適格候補棄却処理の流れを示すフローチャートである。
【図２５】類型ａの場合の不適判定処理の流れを示すフローチャートである。
【図２６】類型ｂの場合の不適判定処理の流れを示すフローチャートである。
【図２７】最適候補選択処理の流れを示すフローチャートである。
【図２８】保守性に関する指標値による最適候補の分類処理の流れを示すフローチャートである。
【図２９】指標値による最適候補選択の一例を示す図である。
【図３０】全自動洗濯機の状態遷移をフラットなステートチャート図で示した図である。
【図３１】候補絞り込み機能に基づいて選択したステートチャート図の一例を示す図である。
【図３２】候補絞り込み機能に基づいて選択したステートチャート図の一例を示す図である。
【図３３】ソースコードからステートチャート図への変換の一例を示す図である。
【図３４】図３３に示す例について、階層化・並列化後のステートチャート図である。
【発明を実施するための形態】
【０００８】
以下、本発明の一実施の形態について、図面を参照して説明する。尚、各図において同一箇所については同一の符号を付すとともに、重複した説明は省略する。
【０００９】
まず、本実施形態で用いる主要な用語について説明する。
【００１０】
「ＵＭＬ（Unified Modeling Language）のステートチャート図」
ＵＭＬは、オブジェクト指向によるモデリングのための表記法を統一したものである。図１に、ＵＭＬによるステートチャート図を示す。
【００１１】
ＵＭＬによるステートチャート図では、オブジェクトの状態は角丸四角で表し、中に状態名を記入する。初期状態（開始状態）は黒丸で示す。ある状態から別の状態への状態遷移は矢印で関係付ける。状態遷移を引き起こすイベント（条件）を矢印の横に記述する。遷移に付随する操作は、アクションとしてイベント（条件）の横に記述する。状態遷移の入口と出口にアクションが記述可能である。遷移は、例えば、“開始状態”、“終了状態”、“イベント”、“条件”、“アクション”のデータから成る。ある状態に入る全ての遷移に共通のアクションがある場合、遷移に同一のアクションを記述するかわりに、entry/入場アクション、exit/退場アクションとして記述できる。また、完了までに時間を要し継続的に行う動作は、do/アクティビティとして記述する。また、ステートチャート図では、階層表現や並列表現もサポートする。さらに、変数の記述も可能である。本実施形態では、アクションや、条件はC言語の形式（制約あり）で記述する。
【００１２】
「ステートチャート図の階層化（通常階層化）」
ステートチャート図では、ステートチャート図の現在の状態が、ある状態であるとき、その状態の中で、さらに詳細なステートチャート図を入れ子にして記述することができる。これを階層と呼ぶ。階層のないステートチャートに対し、これと同じ挙動をする階層を持ったステートチャートが存在する場合、そのようなステートチャートに書き換えることを、“階層化”といい、後述する“履歴階層化”と区別するため“通常階層化”と呼ぶ。階層のないステートチャートが階層化できる場合には、階層を持ったステートチャートの方が読みやすい場合が多い。
【００１３】
図２は、本実施形態におけるステートチャート図の階層化を説明する図である。図２に示すように、元となるステートチャート図を上位階層、詳細なステートチャート図を下位階層と呼ぶ。階層をつなぐ上位階層の状態を、“階層化状態”と呼ぶ。図２に示すように、上位階層で、現在の状態が階層化状態（図２に示す例では、「動作中」）になるたびに、下位階層のステートチャートは初期状態（図２に示す例では、「冷房中」）から開始する。上位階層で、現在の状態が階層化状態（図２に示す例では、「動作中」）で、他の状態（図２に示す例では、「停止中」）に移動する遷移（図２に示す例では、「ＯＦＦ」）が起きた時、下位階層は終了する。
【００１４】
図３は、本実施形態におけるステートチャート図の通常階層化を説明する図である。図３（ａ）に示すフラットなステートチャート図を、図３（ｂ）に示す通常階層化したステートチャート図に書換えても同じ挙動をする。
【００１５】
「ステートチャート図の階層化（履歴階層化）」
ステートチャート図の階層には“履歴状態”、“深履歴状態”を置くことができる。“履歴状態”は、最後にその置かれた階層から出た時の、その階層の状態を表す。“深履歴状態”は、最後にその置かれた階層から出た時の、その階層とその全ての下位階層の状態を表す。階層の外部から“履歴状態”、“深履歴状態”への遷移は、その遷移の際のその階層の戻り先の状態が、それぞれ“履歴状態”、“深履歴状態”の表わす状態であることを示す。この階層を履歴階層と呼ぶ。階層のないステートチャートに対し、これと同じ挙動をする履歴階層を持ったステートチャートが存在する場合、そのようなステートチャートに書き換えることを、“履歴階層化”という。同じ挙動をするように履歴階層化できる場合には、履歴階層化したほうが読みやすくなる場合が多い。
【００１６】
図４は、本実施形態におけるステートチャート図の履歴階層化を説明する図である。図４（ａ）に示すフラットなステートチャート図を、図４（ｂ）に示す履歴階層化したステートチャート図に書換えても同じ挙動をする。履歴階層状態は、Ｈを楕円で囲んだ記号、深履歴階層状態は、Ｈに+を付けた記号で表す。
【００１７】
図４（ｂ）に示す深履歴状態の例では、「停止中」の状態で遷移「ＯＮ」が起きると、以前に「動作中」の状態から遷移する（ＯＦＦとなる）際の最後の状態（「冷房中」もしくは「暖房中」）から動作することを表している。
【００１８】
「ステートチャート図の並列化」
ステートチャート図では、二つのステートチャート図を並列に記述して表記できる。元のステートチャート図から独立に動作する要素を切り出し、同じ挙動をする二つのステートチャート図を並列に記述したものに書き換えることを “並列化”と呼ぶ。
【００１９】
図５は、本実施形態におけるステートチャート図の並列化を説明する図である。図５（ａ）に示すフラットなステートチャート図を、図５（ｂ）に示す並列化したステートチャート図に書換えても同じ挙動をする。図５（ｂ）に示す例では、「冷暖房状態」と「送風状態」は、独立して動作することを示している。
【００２０】
＜階層化と並列化の関係＞
本実施形態においては、“階層化”は、“並列化”の特殊ケースとしてみなすことができる。以下、場合分けして説明する。
【００２１】
（１）通常階層化（特殊ケース１）
通常階層化は、次の条件（通常階層化条件）を満たした並列化と、同じ挙動をする。
【００２２】
ａ．下位に対応するステートチャートの初期状態からの遷移（“初期遷移”）は、全て、上位の階層化状態の時のみ起きる。
【００２３】
ｂ．上位の階層化状態からの遷移と、同じイベント、同じ条件で、下位ステートチャートの全ての状態から初期状態への遷移（“階層脱出遷移”という）がある。
【００２４】
図６は、並列化の特殊ケース１を説明する図である。図６（ａ）は、状態「ａ３」の下にＢの下位ステートチャートがある場合と同じ並列階層の例を示している。図６（ａ）に示す例では、下位ステートチャートＢにおいて、状態「ｂ１」から状態「ｂ２」への遷移「ｅ１」は、上位ステートチャートＡにおいて、状態「ａ３」との条件が満たされることを契機とすることがわかる。図６（ｂ）は、図６（ａ）に示す並列化したステートチャート図と同じ挙動をする通常階層化したステートチャート図の例を示している。
【００２５】
（２）履歴階層化（特殊ケース２）
履歴階層化は、次の条件（履歴階層化条件）を満たした並列化と、同じ挙動をする。
【００２６】
ａ．下位に対応するステートチャート図の全ての遷移は、全て、上位の階層化状態の時のみ起きる。
【００２７】
図７は、並列化の特殊ケース２を説明する図である。図７（ａ）は、状態「ａ３」の下にＢの下位ステートチャートがある場合と同じ並列階層の例を示している。図７（ｂ）は、図７（ａ）に示す並列化したステートチャート図と同じ挙動をする履歴階層化したステートチャート図の例を示している。
【００２８】
本実施形態においては、対象となるフラットなステートチャート図の“遷移”を、二つのステートチャート図に振り分け、階層化もしくは並列化した結果を候補として生成する。階層化、並列化で分割する際、同じイベントは必ず同じステートチャート図で処理されるように行う。さらに、階層化と並列化が可能な場合には階層化を優先する。生成されるステートチャート図を読みやすくするためである。
【００２９】
一般的に、フラットなステートチャート図を同じ挙動をするように階層化もしくは並列化する場合、複数のステートチャート図のペアが“候補”として生成される。図８は、複数の候補の生成を説明する図である。後述するように、本実施形態では、複数の“候補”から最適候補に絞り込む。
【００３０】
図９は、本発明の実施形態に係る階層化・並列化装置の概略構成を示すブロック図である。この装置は汎用のコンピュータ（例えばパーソナルコンピュータ（ＰＣ）等）と、同コンピュータ上で動作するソフトウェアとを用いて実現される。コンピュータとしては、ＣＡＤ（Computer Aided Design）やＣＡＥ（Computer Aided Engineering）に好適なエンジニアリングワークステーション（ＥＷＳ）等も含む。本実施形態はこのようなコンピュータに、対象となるステートチャート図の“遷移”を、二つのステートチャート図に振り分け、階層化もしくは並列化した結果を候補として生成するプログラムとして実施することもできる。
【００３１】
図９に示すように、本実施形態に係る階層化・並列化装置１００は、主として、入力部１０、階層化・並列化候補生成部２０、不適格候補棄却部３０、最適候補選択部４０、ステートチャートデータ格納部５０、候補リスト格納部６０、最適候補リスト格納部７０から構成されている。
【００３２】
入力部１０は、ステートチャートデータ格納部５０に格納されている“ステートチャートデータ”を取り込む。“ステートチャートデータ”は、ステートチャート図を表現するためのコンピュータ上のデータ形式である。例えば、“状態リスト”、“遷移リスト”、“（初期）状態”のデータから成る。
【００３３】
階層化・並列化候補生成部２０は、元のステートチャート図の全ての遷移を、それぞれ結果となる２つのステートチャート図のどちらか、もしくは両方に振分け、“状態対応データ”に矛盾が生じないように整合性の判定を繰り返すことで、階層化・並列化した２つのステートチャート図を一つの“候補”として生成する。ここで、“状態対応データ”は、例えば、“（元のステートチャート図の）状態”、“（作成された１番目のステートチャート図の）状態”、“（作成された２番目のステートチャート図の）状態”のデータから成る。また、“候補”は、階層化・並列化の結果の一つ一つであって、例えば、“（１番目の）ステートチャートデータ”、“（２番目の）ステートチャートデータ”、“状態対応データリスト”、“種別”、“階層化状態”から成る。“状態対応データリスト”は、状態対応データが一つ以上並んだものである。“種別”は、“依存関係のある並列化”、“依存関係が無い並列化”、“履歴階層化”、“通常階層化”のいずれに該当するかの情報である。“階層化状態”は、階層化している“状態”を具体的に示す。
【００３４】
ステートチャート図の階層化およびステートチャート図の並列化については、後述する。
【００３５】
不適格候補棄却部３０は、階層化・並列化候補生成部２０で生成された２つのステートチャート図の“候補”について、保守性が高いか否かを判定し、保守性の高いものを残して、生成する。ここで、「保守性が高い」とは、換言すれば、生成したステートチャート図が、「読みやすい」ことを意味している。
【００３６】
不適格候補棄却部３０は、低保守性判定部３１と、不適判定部３２で構成することができる。低保守性判定部３１は、生成された２つのステートチャート図が「同時に起こることの無い状態」で同じイベントを受ける遷移が存在するか検査し、存在する場合には、保守性が低いと判定する。「同時に起こることの無い状態」は、状態対応データリストから得る。不適判定部３２は、生成された２つのステートチャート図の、通常階層化の“階層脱出遷移”以外で、同じイベントを結果となる両方のステートチャート図が同時に受け取るものを不適と判定する。
【００３７】
最適候補選択部４０は、生成された複数の候補（ステートチャート図のペア）について、より保守性の高いものに絞り込む。より保守性の高いものの絞り込みには、ステートチャート図のペアについて保守性に関する指標値を利用するのが好適である。保守性に関する指標値は、例えば、依存関係のある並列化＜依存関係が無い並列化＜履歴階層化＜通常階層化のように、重み付けするのが好適である。絞り込まれた結果は、最適候補リストとなる。絞り込みについては、後述する。
【００３８】
ステートチャートデータ格納部５０は、ステートチャートデータを格納する。
【００３９】
候補リスト格納部６０は、“候補リスト”を格納する。“候補リスト”は、階層化・並列化の結果である“候補”が複数並んだものである。
【００４０】
最適候補リスト格納部７０は、最適候補選択部４０で絞り込まれた最適候補リストを格納する。
【００４１】
＜動作例＞
次に、以上のように構成された階層化・並列化装置の動作例を説明する。まず、図１０は、本実施形態において表れる各データの構造を示す図である。図１０において、「＊」は当該データが１つ以上並んだものを表す。また、下線が付されたデータは、それ以上分解されないデータで、文字列で表される。
【００４２】
図１１は、動作例の説明において使用する元となるステートチャート図を示す図である。図１１（ａ）に示すステートチャート図は、図１１（ｂ）に示すツリー形式でも表現することができる。図１１の動作例に示すステートチャート図におけるデータ構造は、図１２に示すようになる。
【００４３】
階層化・並列化装置の動作は、大別すると、（１）階層化・並列化候補生成処理、（２）不適格候補棄却処理、（３）最適候補選択処理となり、（２）不適格候補棄却処理は、（２ａ）低保守性判定処理、（２ｂ）不適判定処理に細分される。
【００４４】
＜階層化・並列化候補生成処理＞
階層化・並列化候補生成部２０は、元になるステートチャート図Sを入力として、これから階層化・並列化候補であるステートチャート図A,Bを生成する。以下に候補生成のアルゴリズムの大略を記すが、検索パターン（i）、（ii）、（iii）のどれかの選択を繰返しながら候補を生成する。選択肢をすべて網羅することで全ての候補を見つけることができる。A(ai)は、ステートチャート図Aの状態がaiの時、「真」であり、B(bj)はステートチャート図Bの状態がbjの時、「真」である。これを、“状態制約”と呼ぶ。
【００４５】
（手順１）Ａ、Ｂの初期状態を作成する。初期状態の作成は、元になるステートチャート図S初期状態から、その状態を始点とする各遷移を２つのステートチャート図Ａ、Ｂに振り分けていく。振り分けを幅優先でおこない、全ての遷移を処理したら終了する。尚、図１１に示す動作例では、遷移は簡単のため、イベントのみで構成されるとして記述している。図１３は、図１１に示す動作例において、初期状態の作成を説明する図である。図１３に示すように、作成された初期状態から、状態の対応関係がわかる。元になるステートチャート図Ｓが「停止中」であるとは、ステートチャート図Ａがａ１の状態で、ステートチャート図Ｂがｂ１の状態であることに対応している。
【００４６】
（手順２）Ａの状態の集合ＪＡ、Ｂの状態の集合ＪＢ、元のステートチャート図Sと作成されるステートチャート図Ａ、Ｂの“状態の対応”を示すデータＪＴ、最終的な状態対応データリストの結果ＪＴ’として、ＪＴ、ＪＴ’の初期状態を決める。
【００４７】
（手順３）ＪＴから“状態の対応”を１つ取り出す。図１２に示す状態の対応関係は、手順３のＪＴ’に対応している。ＪＴが空なら手順８へ移行する。
【００４８】
（手順４）取り出した状態対応データの元のステートチャート図Sの“状態”から、“遷移”を１つ取り出し、以下の検索パターン（i）、（ii）、（iii）のどれかを選び実行する。
【００４９】
（i）取り出した“遷移”を、ステートチャート図Ａに割り振る。
【００５０】
（ii）取り出した“遷移”を、ステートチャート図Ａ、Ｂに割り振る。
【００５１】
（iii）取り出した“遷移”を、ステートチャート図Ｂに割り振る。 
図１４は、動作例の遷移「ＯＮ」を振り分けるパターンの作成を説明する図である。図１４に示すように、状態リストは、各ステートチャート図を構成する状態を表す。ここでは、ＪＡ＝｛ａ１、ａ２｝、ＪＢ＝｛ｂ１｝となっている。
【００５２】
図１５は、動作例の「冷房中」から「暖房中」への遷移「冷暖切替」を振り分けるパターンの作成を説明する図である。各パターンに対して、遷移「冷暖切替」に対応する遷移を作成していくが、図１５に示す例では、パターン（i）を抜粋して示している。振り分け後の、状態の対応関係は、図示のようになる。
【００５３】
図１６は、動作例の遷移「ＯＦＦ」を振り分けるパターンの作成を説明する図である。各パターンに対して、遷移「ＯＦＦ」に対応する遷移を作成していくが、図１６に示す例では、パターン（i）、（iii）を抜粋して示している。振り分け後の、状態の対応関係は、図示のようになる。
【００５４】
“遷移”が空になったら手順３へ移行する。
【００５５】
（手順５）矛盾があれば、当該振り分けパターンは捨てる。図１６に示す例では、振り分け後のパターン（i）、（iii）、（i）において、「停止中」に状態の対応関係｛ａ１、ｂ２｝が割り当てられるが、既に｛ａ１、ｂ１｝も割り当てられている。同様に、振り分け後のパターン（i）、（iii）、（iii）において、「停止中」に状態の対応関係｛ａ２、ｂ２｝が割り当てられるが、既に｛ａ１、ｂ１｝も割り当てられている。図１７は、矛盾のチェックを説明する図である。パターン（i）、（iii）、（i）において、「停止中」の際のステートチャート図Ｂの状態がｂ１の場合とｂ２の場合ができてしまい、矛盾する。そこで、パターン（i）、（iii）、（i）は捨てる。同様に、パターン（i）、（iii）、（iii）において、「停止中」の際のステートチャート図Ａの状態がａ１の場合とａ２の場合ができてしまい、矛盾する。そこで、パターン（i）、（iii）、（iii）は捨てる。
【００５６】
（手順６）手順３ へ移行する。
【００５７】
図１８は、パターン（i）、（iii）、（ii）に対して、動作例の「暖房中」から「冷房中」への遷移「冷暖切替」を振り分けるパターンの作成を説明する図である。図１８に示すように、「冷暖切替」は既にステートチャート図Ｂへ割り付けられているので、最終的に不適格候補棄却部３０により捨てられる。
【００５８】
次に、図１９は、パターン（i）、（iii）、（ii）、（iii）に対して、動作例の「暖房中」から「停止中」への遷移「ＯＦＦ」を振り分けるパターンの作成を説明する図である。図１９に示すように、「ＯＦＦ」は既にステートチャート図Ａ、Ｂに割り付けられているので、パターン（i）、（iii）、（ii）、（iii）、（i）とパターン（i）、（iii）、（ii）、（iii）、（iii）は最終的に不適格候補棄却部３０により捨てられる。
【００５９】
（手順７）まとめられる遷移をまとめる。
【００６０】
（手順８）取り除ける状態制約は取り除く。
【００６１】
図２０は、遷移条件の整理を説明する図である。ステートチャート図Ｂの状態ｂ２は、状態対応データから、暖房中＝｛ａ２、ｂ２｝のときにのみ成立する。つまり、ｂ２の状態であれば必ずａ２の状態であることがわかる。したがって、図２０（ｂ）に示すように、状態ｂ２からのエッジの条件Ａ（ａ２）は、常に「真」なので省略することができる。
【００６２】
（手順９）通常階層化条件、履歴階層化条件に従って、階層化できるものは階層表現に変える。図２１は、候補の階層化を説明する図である。上述してきた手順１〜手順８を経て、最終的に図２１（ａ）に示すステートチャート図Ａ、Ｂが生成される。生成されたステートチャート図Ａ、Ｂは、通常階層化条件を満たしている。そこで、読みやすくするために階層化した形に書き換えると、図２１（ｂ）に示すようになる。
【００６３】
上述してきた動作例では、最終的に出来上がった候補は１つだけなので、以上で階層化・並列化候補生成処理を終わる。
【００６４】
図２２は、結果となる候補リストを生成する階層化・並列化候補生成処理におけるデータ構造を表す図である。
【００６５】
＜階層化・並列化候補生成処理の詳細フロー＞
図２３は、階層化・並列化候補生成処理の詳細例を示すフローチャートである。
【００６６】
まず、元のステートチャート図Sの初期状態をｓ１、ｓ１以外の状態の集合をＪＳ、ステートチャート図Ａの初期状態をａ１、ステートチャート図Ｂの初期状態をｂ１であるとする。
【００６７】
ステートチャート図Ａの状態の集合（状態リスト）をＪＡ、ステートチャート図Ｂの状態の集合（状態リスト）をＪＢ、元のステートチャート図Ｓと作成されるステートチャート図Ａ、Ｂの状態対応を示すデータをJT={(s1.(a1,b1))}、最終的に状態対応データリストの結果となるJT’をJT’={(s1.(a1,b1))}とする（ステップＳ２３１）。
【００６８】
続いて、状態対応データリストＪＴから状態対応データを１つ取り出し、これを、(si , (as,bs))とする（ステップＳ２３２）。状態対応データリストJTが空ならばステップＳ２３６へ移行する。
【００６９】
次に、元のステートチャート図Sの遷移リストから、siからの遷移を１つ取り出し、これをsi―E/[C]F→sjとする（ステップＳ２３３）。遷移リストが空ならばステップＳ２３２へ移行する。
【００７０】
以下の検索パターン（i）、（ii）、（iii）のどれかを選び実行する（ステップＳ２３４）。
【００７１】
（i）sj=(at,bs)としてステートチャート図Aに遷移as―E/[C∧B(bs)]F→atと状態atを加える。JT、JT’に(sj, (at,bs))を加える。
【００７２】
（ii）sj=(as,bt) としてステートチャート図Ｂに遷移bs―E/[C∧A(as)]F→btと状態btを加える。JT 、JT’に(sj, (as,bt))を加える。
【００７３】
（iii）sj=(at,bt) としてステートチャート図Aに遷移as―E/[C∧B(bs)]F→atと状態atを加え、ステートチャート図Bに遷移bs―E/[C∧A(as)]F→btと状態btを加える。 JT、JT’に(sj, (at,bt))を加える。 
次に、それぞれ、あるai,biに対し(sj , (ai,bi))∈JT’ならば、sj =(ai,bi)として整合性をチェックする（ステップＳ２３５）。つまり、（i）の場合であれば、at=ai,bs=bi、（ii）の場合であれば、as=at,bt=biとして、矛盾の有無をチェックする。元のステートチャート図Sでは異なる状態sn,smが、どちらもあるaj bjに対してsn=(aj,bj), sm=(aj,bj)となる場合、もしくは、ある状態snが異なるajbj、ajbjに対して(どちらか一方だけでも可)、sn=(aj,bj), sn=(aj,bj)となる場合には、矛盾することになる。整合性が取れていないならば失敗である。
【００７４】
次に、同じ状態からの遷移で、条件の状態制約のみが違うものは∨を使って１つにまとめる（ステップＳ２３６）。例えば、as―E/[C∧B(bs)]F→at、as―E/[C∧B(bu)]F→atをまとめると、as―E/[C∧(B(bs)∨B(bu))]F→atとなる。
【００７５】
次に、各状態に対して、JT’から同時に起こる他方のステートチャート図の状態の集合を見つける。この際、この状態からの遷移で、条件の状態制約とこの集合が一致するものがあれば、この遷移の状態制約を取り除く（ステップＳ２３７）。
【００７６】
その後、通常階層化条件、履歴階層化条件に従って、階層化できるものは階層表現に変える。
【００７７】
上述したアルゴリズムが成功で終了した場合に、１つの分割パターンが見つかる。失敗した場合、選択候補が残っているもっとも近い検索パターン（i）、（ii）、（iii）の選択まで戻り、別の候補を網羅的に探索することにより、全ての分割パターンを見つけることができる。
【００７８】
＜不適格候補棄却処理＞
図２４は、不適格候補棄却処理の流れを示すフローチャートである。不適格候補棄却処理においては、階層化・並列化候補生成部２０で、階層化・並列化された候補（ステートチャートデータのペア）が生成される毎に、当該候補を取り込み（ステップＳ２４１）、当該候補について、所定の判定基準に基づいて、不適格な候補として棄却すべきか否かを判定する（ステップＳ２４２）。判定基準としては、保守性の良好性如何で判定するのが好適である。不適格でないものが、１つの階層化・並列化候補（２つのステートチャート）として出力される。
【００７９】
＜不適判定処理＞
本実施形態では、以下に該当する場合に、階層化・並列化された候補（ステートチャートデータのペア）が「不適」と判定する。
【００８０】
（類型ａ）２つのステートチャート図への分割の際、同じイベントをステートチャート図Ａのみが受けたり、ステートチャート図Ｂのみが受ける等、受けるステートチャート図が状況によって異なるもの。
【００８１】
（類型ｂ）通常階層化での階層状態から通常状態への遷移以外で、ステートチャート図Ａと、ステートチャート図Ｂが同じイベントを受け取るもの。
【００８２】
図２５は、類型ａの場合の不適判定処理の流れを示すフローチャートである。
【００８３】
まず、二つのステートチャート図Ａ，Ｂが受け取る全てのイベントを検索、このイベントの集合をEとする（ステップＳ２５０１）。
【００８４】
各イベントe∈Eに対し（ステップＳ２５０２）、ステートチャート図Ａ、Ｂの一方のみにしかeによる遷移が無いか否かを判定する（ステップＳ２５０３）。一方のみにしかeによる遷移が無いならば不適ではないので、次の候補（ステートチャート図のペア）についての判定へ移行する。
【００８５】
ステートチャート図Ａ、Ｂの両方にeによる遷移がある場合、ステートチャート図Ａ、Ｂのそれぞれeによる遷移の集合をA(e),B(e)とする（ステップＳ２５０４）。
【００８６】
各ｓ∈A(e)に対し（ステップＳ２５０５）、sの開始状態をk(s)とおく。状態対応データからｋ(s)と同時に起こるBの状態を全て取り出し、これをB_k(s)とする（ステップＳ２５０６）。
【００８７】
各t∈B_k(s)に対し（ステップＳ２５０７）、tからsと同じイベント、条件による遷移が無いか否かを判定する（ステップＳ２５０８）。該当する遷移がなければ不適と判定する。
【００８８】
該当する遷移があれば、各u∈B(e)に対し（ステップＳ２５０９）、uの開始状態をk(u)とおく。状態対応データからｋ(u)と同時に起こるAの状態を全て取り出し、これを A_k(u) とする（ステップＳ２５１０）。
【００８９】
各v∈A_k(u)に対し（ステップＳ２５１１）、vからuと同じイベント、条件による遷移が無いか否かを判定する（ステップＳ２５１２）。該当する遷移がなければ不適と判定する。該当する遷移があれば、「適」と判定する。
【００９０】
図２６は、類型ｂの場合の不適判定処理の流れを示すフローチャートである。
【００９１】
まず、通常階層化か否かを判定する（ステップＳ２６０１）。通常階層化ならば、「適」と判定する。
【００９２】
通常階層化でないとき、各イベントe∈Eに対し（ステップＳ２６０２）、ステートチャート図Ａ、Ｂの一方のみにしかeによる遷移が無いかを判定する（ステップＳ２６０３）。一方のみにしかeによる遷移が無いならば、履歴階層化ではないので、次の候補（ステートチャート図のペア）についての判定へ移行する。
【００９３】
ステートチャート図Ａ、Ｂの両方にeによる遷移がある場合、Ａ、Ｂそれぞれeによる遷移の集合をA(e), B(e)とする（ステップＳ２６０４）。
【００９４】
各ｓ∈A(e)に対し（ステップＳ２６０５）、sの開始状態をk(s)とおく。
【００９５】
状態対応データからｋ(s)と同時に起こるBの状態を全て取り出し、B_k(s)とする（ステップＳ２６０６）。
【００９６】
各t∈B_k(s)に対し（ステップＳ２６０７）、tからsと同じイベント、条件による遷移があるか否かを判定する（ステップＳ２６０８）。あれば不適と判定する。
【００９７】
各u∈B(e)に対し（ステップＳ２６０９）、
uの開始状態をk(u)とおく。状態対応データからｋ(u)と同時に起こるAの状態を全て取り出し、A_k(u)とする（ステップＳ２６１０）。
【００９８】
各v∈A_k(u)に対し（ステップＳ２６１１）、
vからuと同じイベント、条件による遷移があるか否かを判定する（ステップＳ２６１２）。
【００９９】
該当する遷移があれば不適と判定する。該当する遷移がなければ、「適」と判定する。
【０１００】
＜最適候補選択処理＞
図２７は、最適候補選択処理の流れを示すフローチャートである。最適候補選択処理においては、階層化・並列化候補生成部２０で、階層化・並列化された候補（ステートチャートデータのペア）が生成される毎に（ステップＳ２７１）、次の候補の有無を判定する（ステップＳ２７２）。
【０１０１】
全ての候補の生成が終わると（ステップＳ２７２でＮＯ）、最適候補選択部４０において、全ての候補を、“保守性比較手段”で整列する（ステップＳ２７３）。“保守性比較手段”は、例えば、階層化・並列化されたステートチャート図のペアに対し、所定の指標値により、そのペアに対する保守性の良い・悪いを表す全順序を付与するものである。
【０１０２】
次に、最も良い候補（複数ある場合には複数）の集合を選択して（ステップＳ２７４）、出力する。
【０１０３】
＜指標値による選択処理＞
最適候補選択部４０において、階層化・並列化された候補（ステートチャートデータのペア）を、依存関係のある並列化、依存関係が無い並列化、履歴階層化、通常階層化に分類し、通常階層化＞履歴階層化＞依存関係が無い並列化＞依存関係のある並列化と順序を判定する。図２８は、保守性に関する指標値による最適候補の分類処理の流れを示すフローチャートである。
【０１０４】
まず、（ａ）下位に対応するステートチャート図の初期状態からの遷移は、全て、上位の階層化状態の時のみ起きる、（ｂ）上位の階層化状態からの遷移と、同じイベント、同じ条件で、下位ステートチャート図の全ての状態から初期状態への遷移がある、の条件を満たすか否かを判定する（ステップＳ２８１）。上記条件を満たす（ステップＳ２８１でＹｅｓ）場合には、“通常階層”と判定する（ステップＳ２８２）。
【０１０５】
次に、下位に対応するステートチャート図の全ての遷移は、全て、上位の階層化状態の時のみ起きるか否かを判定する（ステップＳ２８３）。係る条件を満たす（ステップＳ２８３でＹｅｓ）場合には、“履歴階層”と判定する（ステップＳ２８４）。
【０１０６】
次に、全ての遷移に、もう一方の状態を参照する条件が含まれていないか否かを判定する（ステップＳ２８５）。係る条件を満たす（ステップＳ２８５でＹｅｓ）場合には、“依存関係が無い並列化”と判定する（ステップＳ２８６）。
【０１０７】
上記のいずれにも分類されない候補は、“依存関係のある並列化”と判定する（ステップＳ２８７）。
【０１０８】
＜最適候補選択の一例＞
最適候補選択部４０における最適候補選択の一例を説明する。図２９は、指標値による最適候補選択の一例を示す図である。図２９（ａ）に示す元のステートチャート図から、図２９（ｂ）に示す候補１、図２９（ｃ）に示す候補２が生成される。図２９（ｂ）に示すように、候補１は、履歴階層化したステートチャートデータのペアである。図２９（ｃ）に示すように、候補２は、依存関係のある並列化したステートチャートデータのペアである。よって、候補１が最適候補として選択される。
【０１０９】
＜実施例＞
ここでは、脱水機能が「強」と「弱」を選べる全自動洗濯機における状態遷移を例にとって図示する。図３０は、全自動洗濯機の状態遷移をフラットなステートチャート図で示した図である。図３０に示す元のステートチャート図からは、通常階層化と依存関係のある階層化が可能である。そこで、候補絞り込み機能に基づいて通常階層化を選択する。図３１は、候補絞り込み機能に基づいて選択したステートチャート図の一例を示す図である。
【０１１０】
さらに、状態“ＯＮ”の下位階層のステートチャート図を階層化・並列化することが可能である。係る処理結果からは、さらに履歴階層化と依存関係のある並列化したものが候補となりうる。そこで、候補絞り込み機能に基づいて通常階層化を選択する。図３２は、候補絞り込み機能に基づいて選択したステートチャート図の一例を示す図である。
【０１１１】
以上説明したように、本実施形態によれば、対象となるフラットなステートチャート図の遷移を、意味・挙動が把握しやすい階層化もしくは並列化したステートチャート図を候補として生成することができる。
【０１１２】
図３３は、ソースコードからステートチャート図への変換の一例を示す図である。図３３に示す例では、洗濯機を例にとり、状態数が２０、遷移数が約１７０、元のソースコードが４００行のものをステートチャート図へ変換している。図３３に示すステートチャート図は、一見すると何を示しているか理解するのは難しいものとなっている。図３４は、図３３に示す例について、階層化・並列化後のステートチャート図である。図３４を見ると、意味・挙動が把握しやすいものとなっている。
【０１１３】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１１４】
１００・・・階層化・並列化装置
１０・・・入力部
２０・・・階層化・並列化候補生成部
３０・・・不適格候補棄却部
４０・・・最適候補選択部
５０・・・ステートチャートデータ格納部
６０・・・候補リスト格納部
７０・・・最適候補リスト格納部
【図１】
2015153275.tif 000003
【図２】
2015153275.tif 000004
【図３】
2015153275.tif 000005
【図４】
2015153275.tif 000006
【図５】
2015153275.tif 000007
【図６】
2015153275.tif 000008
【図７】
2015153275.tif 000009
【図９】
2015153275.tif 000010
【図１０】
2015153275.tif 000011
【図１１】
2015153275.tif 000012
【図１２】
2015153275.tif 000013
【図１３】
2015153275.tif 000014
【図１４】
2015153275.tif 000015
【図１７】
2015153275.tif 000016
【図１８】
2015153275.tif 000017
【図１９】
2015153275.tif 000018
【図２０】
2015153275.tif 000019
【図２１】
2015153275.tif 000020
【図２２】
2015153275.tif 000021
【図２３】
2015153275.tif 000022
【図２４】
2015153275.tif 000023
【図２５】
2015153275.tif 000024
【図２６】
2015153275.tif 000025
【図２７】
2015153275.tif 000026
【図２８】
2015153275.tif 000027
【図２９】
2015153275.tif 000028
【図８】
2015153275.tif 000029
【図１５】
2015153275.tif 000030
【図１６】
2015153275.tif 000031
【図３０】
2015153275.tif 000032
【図３１】
2015153275.tif 000033
【図３２】
2015153275.tif 000034
【図３３】
2015153275.tif 000035
【図３４】
2015153275.tif 000036