JPH04333969A - 状態遷移検索装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、状態遷移モデルをベー
スとしたリアルタイムシステムの開発を支援する状態遷
移検索装置に関するものである。

【０００２】

【従来の技術】大規模なリアルタイムシステムでは、そ
の動作仕様となるドキュメント（状態遷移図）を作成す
る場合、論理的には一つの状態遷移でも、一般に、何枚
ものドキュメントに分けて作成される。

【０００３】このとき、複数に分割された状態遷移図間
の論理的なつながりを表すために、遷移（入口）ラベル
名と遷移先の情報からなるラベルテーブルを用いた手法
が広く使われている。さらに、状態遷移の遷移先（出口
）ラベルの広範囲に渡る検索を効率的に行なうために、
以下のような方式が取られている。

【０００４】すなわち、まず、ラベルに対し、そのラベ
ルが全ドキュメント内で有効となる範囲を規定したスコ
ープをもたせる。例えば、全ドキュメント内で有効なラ
ベルとか、１つのドキュメント内でのみ有効なラベルと
いうようなスコープをラベルにもたせる。

【０００５】また、スコープに対応したラベルテーブル
を階層的な木構造として管理する。ここで、ルートノー
ドにはスコープが全ドキュメントに渡るラベルテーブル
を、リーフノードには１ドキュメント内でのみ有効なラ
ベルテーブルを割り当てる。中間ノードのラベルテーブ
ルに対しては、ラベルのスコープを自由に設定してかま
わない。

【０００６】このような構成では、ドキュメント内の遷
移先（出口）ラベルに対応する遷移（入口）ラベルの検
索を行なうには、そのドキュメントに対応した木構造の
最下位のラベルテーブルからルートの方へ階層毎のラベ
ルテーブルを探していく。

【０００７】

【発明が解決しようとする課題】しかしながら、上述し
た従来の状態遷移検索装置では、状態遷移図の分割／統
合に対する遷移ラベル定義の柔軟な対応ができないとい
う問題があった。すなわち、大規模な状態遷移図の場合
、機能の追加修正があるたびに、１ドキュメント内で収
まっていた部分的な状態遷移が複数の部分的な状態遷移
図に分割されたり、複数の状態遷移図を一つにまとめる
ことが頻繁に行なわれるが、従来の装置では、これに対
応して、遷移ラベルのスコープもその都度変更する必要
があるという欠点があった。

【０００８】また、分割された状態遷移図に対して高度
な解析を行なう場合、ラベル参照の頻度が多くなるので
、遷移ラベルの検索時間を短縮させることが難かしいと
いう欠点があった。

【０００９】本発明の目的は、遷移ラベルの修正を行な
わずに状態遷移図の分割／統合を可能にすると同時にラ
ベルの検索時間を従来よりも短縮することが可能な状態
遷移検索装置を提供することにある。

【００１０】

【課題を解決するための手段】本発明の状態遷移検索装
置は、状態遷移情報を保持するための状態遷移記憶手段
と、ラベルテーブルを階層的な木構造として保持するた
めのラベルテーブル記憶手段と、ラベルタイプに対応す
る木構造のレベルを保持するためのラベルタイプ情報記
憶手段と、前記状態遷移記憶手段に保持された状態遷移
情報と前記ラベルタイプ情報記憶手段に保持されたラベ
ルタイプ情報と前記ラベルテーブル記憶手段に保持され
たラベル情報とをもとに状態遷移情報を検索するための
状態遷移検索手段とを有している。

【００１１】

【作用】本発明では、状態遷移記憶手段に保持された状
態遷移情報とラベルタイプ情報記憶手段に保持されたラ
ベルタイプ情報とラベルテーブル記憶手段に保持された
ラベル情報とをもとに状態遷移情報を検索し、遷移ラベ
ルにタイプを導入することで、遷移ラベルの修正を行わ
ずに状態遷移図の分割／統合が可能となり、また、階層
ごとにラベルテーブルを検索することなしにラベルタイ
プ情報から直接ラベルが格納されている階層のラベルテ
ーブルを求めることで、ラベルの検索時間を従来よりも
短縮できる。

【００１２】

【実施例】次に本発明について図面を参照して詳細に説
明する。図１は、本発明の一実施例のブロック図である
。図１を参照すると、状態遷移記憶装置１１は、ドキュ
メントごとに遷移情報と対応する木構造のリーフノード
アドレスを保持するようになっている。また、ラベルテ
ーブル記憶装置１２は、ラベルタイプに対応したラベル
テーブルを階層的な木構造として保持するようになって
いる。ラベルタイプ情報記憶装置１３は、ラベルタイプ
と木構造のレベルとの対応関係を保持するようになって
いる。また、状態遷移検索装置１４は、ラベルタイプか
ら遷移（入口）ラベルが格納されているラベルテーブル
の階層レベルを見つけ、その階層レベルにあるラベルテ
ーブルから対応するラベルの遷移先ラベル情報を検索し
出力するようになっている。

【００１３】図２は、ラベルタイプ情報記憶装置１３に
格納される情報の構造を示した図である。ラベルタイプ
情報は、ラベルのタイプ２１、木構造レベル情報リスト
ヘのポインタ２２からなる。木構造レベル情報は、木構
造のレベル２３、レベルが絶対レベルが相対レベルかを
区別するためのレベルタイプ２４からなっている。

【００１４】図３は、ラベルテーブル記憶装置１２のデ
ータ構造の概観を示した図であり、図４は、図３の各ノ
ードに格納される情報の構造を示した図である。各ノー
ド情報は、親ノードへのポインタ４１、子ノードへのポ
インタリスト４２、木構造の階層を示す絶対レベル４３
、ラベルテーブルへのポインタ４４からなっている。ま
た、ラベルテーブルは、ラベル名４５、遷移先（出口）
ラベル情報リストへのポインタ４６からなり、遷移先ラ
ベル情報は、遷移先ラベルがあるドキュメントの番号４
７と、ドキュメント内で一意に決まるノード番号４８か
らなっている。

【００１５】図５は、状態遷移記憶装置１１に格納され
るドキュメント情報の構造を示した図である。ドキュメ
ント情報は、ドキュメント番号５１、木構造のリーフノ
ードへのポインタ５２、遷移情報リストへのポインタ５
３からなり、遷移情報は、ノード番号５４とそのノード
からの遷移先ノード番号リスト５５からなっている。

【００１６】次にこのような構成の状態遷移検索装置の
動作について図６乃至図８により説明する。

【００１７】図６は、状態遷移検索装置１４の処理手順
の概要を示したものである。状態遷移検索装置１４は、
まず、状態遷移記憶装置１１に格納されているドキュメ
ント情報から該当するドキュメントの木構造リーフノー
ドポインタを取り出す（ステップ６１）。次に、ドキュ
メントに格納されているノード情報から遷移先（出口）
ラベル名に対応するラベルタイプを求める（ステップ６
２）。このようにして求めたリーフノードポインタ、ラ
ベルタイプおよびラベルタイプ情報からそのラベルの階
層レベルを求め（ステップ６３）、さらに、求めた階層
レベルにあるラベルテーブルから遷移（入口）ラベル名
に対応する遷移先ノードリストを求める。

【００１８】図７は、ステップ６３の処理の詳細な手順
を示したものである。ステップ６３の処理においては、
まず、ラベルタイプ情報記憶装置１３からラベルタイプ
に対応する木構造レベル情報リストを取り出す（ステッ
プ７１）。また、リーフノードの階層レベルをａＴｒｅ
ｅＬｅｂｅｌに設定しておく（ステップ７２）。次いで
、取り出した木構造レベル情報リストから最初の木構造
レベル情報を取り出し（ステップ７３）、木構造レベル
のタイプが絶対レベルでなければ、すなわち相対レベル
ならばａＴｒｅｅＬｅｖｅｌから絶対レベルに変換する
（ステップ７５）。また、レベルａＴｒｅｅＬｅｖｅｌ
以下であれば（ステップ７６）、現在の木構造レベルを
返し終了する（ステップ７７）。それ以外の場合は、次
の木構造レベル情報を取り出し（ステップ７８）、ステ
ップ７４に戻る。

【００１９】図８は、ステップ６４の処理の詳細な手順
を示したものである。ステップ６４の処理においては、
まず、リーフノードをカレントノードに設定する（ステ
ップ８１）。次に、ステップ６３で求めた検索対象の遷
移ラベルの階層レベルをａＬｅｂｅｌに設定する（ステ
ップ８２）。さらに、カレントノードの階層レベルをａ
ＴｒｅｅＬｅｂｅｌに設定する（ステップ８３）。もし
、ａＴｒｅｅＬｅｖｅｌがａＬｅｂｅｌに等しければ（
ステップ８４）、そのレベルのラベルテーブルを取り出
し（ステップ８５）、そのラベルテーブルから指定遷移
ラベル名に対応する遷移先ラベル情報を取り出し終了す
る（ステップ８６）。逆に、等しくなければ、カレント
ノードから親ノードを取り出してカレントノードに設定
し（ステップ８７）、ステップ８３の処理に戻る。

【００２０】いま、例えば図９，図１０に示すような状
態遷移図を考える。ここで、図９は、上下２枚に分かれ
ていたドキュメントを１枚のドキュメントにまとめたと
ころを表している。また、ラベルタイプ情報記憶装置１
３には、図１１に示すようにラベルタイプＡ，Ｂ，Ｃが
定義されているものとする。ラベルタイプＡには、木構
造レベルとして絶対レベル１、ラベルタイプＢには、木
構造レベルとしてまず絶対レベル“２”、次に相対レベ
ル“１”、ラベルタイプＣには、木構造レベルとしてま
ず絶対レベル“３”、次に相対レベル“１”がそれぞれ
登録されている。ラベルタイプＡのスコープは、ドキュ
メント全体に渡るものとする。ラベルタイプＢのスコー
プは、図９のドキュメント内とする。ラベルタイプＣの
スコープは、一枚のドキュメント内のみとする。

【００２１】また、状態遷移記憶装置１１には、図９お
よび図１０で示される状態遷移図の各ドキュメント毎の
遷移情報が、図１２のように格納されている。例えばド
キュメント番号Ｄ＃１のノード番号８の遷移ラベルＣ＃
１は、ノード番号５のノードに遷移していることを表し
ている。

【００２２】さらに、ラベルテーブル記憶装置１２には
、図１３に示すような木構造のラベルテーブル情報が格
納されているものとする。すなわち、ルートノード１３
１　にはラベルテーブル情報が図１４に示すように格納
されているものとし、リーフノード１３２にはラベルテ
ーブル情報が図１５に示すように格納されているものと
し、リーフノード１３３　にはラベルテーブル情報が、
図１６に示すように格納されているものとする。

【００２３】このような状況下で、図９で遷移ラベルＡ
＃１（ノード番号“１０”）の遷移先ノードを検索する
場合、まず状態遷移記憶装置１１からドキュメント番号
Ｄ＃１のリーフノードポインタ（１３２　）を取り出す
（ステップ６１）。つぎに、ドキュメントのノード情報
から遷移ラベルＡ＃１のラベルタイプＡを取り出す（ス
テップ６２）。

【００２４】取り出したリーフノードポインタ（１３２
　）とラベルタイプＡをもとにラベルタイプ情報記憶装
置１３から階層レベルを求める（ステップ６３）。この
場合、リーフノード１３１　のレベル“２”で、ノード
のラベルタイプがＡであるので階層レベル“１”が求め
られることになる。

【００２５】最後に、リーフノード１３２　から上位階
層へたどり、階層レベル“１”にあるルートノード１３
２　のラベルテーブル（図１４）から遷移ラベルＡ＃１
に対応する遷移先ノードリストを求める（ステップ６４
）。遷移先ノードは、ドキュメントＤ＃２のノード番号
“１１”のノードとなる。

【００２６】同様に、図９で遷移ラベルＣ＃１（ノード
番号“１２”）の遷移先ノードを検索する場合、先ず状
態遷移記憶装置１１からドキュメント番号Ｄ＃１のリー
フノードポインタ（１３２　）を取り出す（ステップ６
１）。つぎに、ドキュメントのノード情報から遷移ラベ
ルＣ＃１のラベルタイプＣを取り出す（ステップ６２）
。

【００２７】取り出したリーフノードポインタ（１３２
　）とラベルタイプＣをもとにラベルタイプ情報記憶装
置１３から階層レベルを求める（ステップ６３）。この
場合、リーフノード１３２　のレベルは“２”で、ノー
ドのラベルタイプがＣとなる。ラベルタイプ情報記憶装
置１３のラベルタイプＣの最初の木構造レベルは絶対レ
ベル“３”でリーフノード１３２　のレベルは“２”よ
りも大きいので（ステップ７６）、その次の木構造レベ
ルを取り出す（ステップ７８）。次の木構造レベルは、
相対レベル“１”なので絶対レベル“２”に変換される
（ステップ７５）。リーフノード１３２　のレベルと等
しいのでレベル“２”を返す（ステップ７７）。

【００２８】最後に、階層レベル“２”のリーフノード
１３２　のラベルテーブル（図１５）から遷移ラベル名
Ｃ＃１に対応する遷移先ノードリストを求める（ステッ
プ６４）。遷移先ノードは、ドキュメントＤ＃１のノー
ド番号“８”のノードとなる。

【００２９】このように、本実施例によれば、ラベルの
検索時間を従来よりも短縮できると同時に頻繁な状態遷
移図の分割／統合が遷移ラベルの修正を行なわずに可能
になった。

【００３０】なお、本実施例では、複数のドキュメント
を１枚のドキュメントに統合した例を示したが、状態遷
移図の分割に対してもラベルタイプ情報記憶装置１３の
ラベルタイプ情報を修正するだけで対応できる。

【００３１】

【発明の効果】以上に説明したように本発明によれば、
遷移ラベルにタイプ情報を導入することにより、遷移ラ
ベルの修正を行なわずに状態遷移図の分割／統合が可能
となり、また階層ごとにラベルテーブルを検索すること
なしにラベルタイプ情報から直接ラベルが格納されてい
る階層のラベルテーブルを求めることで、ラベルの検索
時間を従来よりも短縮することができる。

【図面の簡単な説明】

【図１】本発明の一実施例のブロック図である。

【図２】ラベルタイプ情報記憶装置１３に格納される情
報の構造を示す図である。

【図３】ラベルテーブル記憶装置３のデータ構造を概略
的に示す図である。

【図４】ラベルテーブル記憶装置３の各ノードに格納さ
れる情報のノードを示す図である。

【図５】状態遷移記憶装置１１に格納されるドキュメン
ト情報の構造を示す図である。

【図６】状態遷移検索装置１４の処理手順の概要を示す
フローチャートである。

【図７】リーフノードとラベルタイプとからそのラベル
の階層レベルを求める際の処理手順を示すフローチャー
トである。

【図８】ラベルテーブルから遷移ラベル名に対応する遷
移先ノードリストを求める処理手順を示すフローチャー
トである。

【図９】状態遷移図の一例を示す図である。

【図１０】状態遷移図の一例を示す図である。

【図１１】ラベルタイプ情報記憶装置に格納される内容
の例を示す図である。

【図１２】状態遷移記憶装置に格納される内容の例を示
す図である。

【図１３】木構造のラベルテーブルを示す図である。

【図１４】ルートノード１３１　の内容の例を示す図で
ある。

【図１５】リーフノード１３２　の内容の例を示す図で
ある。

【図１６】リーフノード１３３　の内容の例を示す図で
ある。

【符号の説明】

１１　　　　状態遷移記憶装置 １２　　　　ラベルテーブル記憶装置 １３　　　　ラベルタイプ情報記憶装置１４　　　　状
態遷移検索装置

Claims (1)

【特許請求の範囲】
1. 【請求項１】　　状態遷移情報を保持するための状態遷
   移記憶手段と、ラベルテーブルを階層的な木構造として
   保持するためのラベルテーブル記憶手段と、ラベルタイ
   プに対応する木構造のレベルを保持するためのラベルタ
   イプ情報記憶手段と、前記状態遷移記憶手段に保持され
   た状態遷移情報と前記ラベルタイプ情報記憶手段に保持
   されたラベルタイプ情報と前記ラベルテーブル記憶手段
   に保持されたラベル情報とをもとに状態遷移情報を検索
   するための状態遷移検索手段とを備えていることを特徴
   とする状態遷移検索装置。