JPS62114358A

JPS62114358A - 通信プロトコル合成方式

Info

Publication number: JPS62114358A
Application number: JP60253640A
Authority: JP
Inventors: Yoshiaki Tsunoda; 良明角田; Yasushi Wakahara; 若原　恭; Masamitsu Norikoshi; 乗越　雅光
Original assignee: Kokusai Denshin Denwa KK
Current assignee: KDDI Corp
Priority date: 1985-11-14
Filing date: 1985-11-14
Publication date: 1987-05-26
Also published as: US4802162A; JPH0443461B2

Abstract

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

Description

【発明の詳細な説明】（産業上の利用分野）本発明は、機能的に不足部分を含むプロトコル仕様を人
力して不足部分を自動的に追加生成してプロトコル仕様
を完全なものとして出力するプロトコルの自動合成方式
に関する。

（従来技術）プロトコル自動合成は、論理矛盾のないプロトコル仕様
を効率良く設計する技術である。その自動合成過程は、
先ず機能的に完全でないが論理矛盾のないプロトコル仕
様を与え、次にその不足部分を自動生成して全体として
論理矛盾のないプロトコル仕様を出力するように構成さ
れる。

図１は実用化されているＡＢプロトコル（Ａｌｔｅｒｎ
ａｔｉｎｇ　Ｂｉｔ　Ｐｒｏｔｏｃｏｌ）を図示したも
のである。このＡＢプロトコルは通信システムのプロト
コル仕様を表すもので、（ａｌに示すプロセス１　（送
信側プロセス）、（ｂ）に示すプロセス２　（ネットワ
ークプロセス）及び（Ｃ１に示すプロセス３　（受信側
プロセス）の３つのプロセスから構成されている例であ
る。ここで、通信システムとは例えば、プロセスが交換
機及び端末装置等の物理的実体に対応するものでもよい
し、プロセスがＣＰＵ及びメモリ内の論理的実体に対応
するものであってもよい。即ち、他の機能ブロックと信
号の送受信を行う処理単位をプロセスと呼ぶ。

図１において、丸印はプロセスの状態、矢印は状態遷移
、ｄｏ、ｄｉ、ａＯ，ａｌ及びａｅは送受信する信号（
これらの信号をまとめて、「信号Ｘ」と称す）、矢印上
のラベル−Ｘ及び＋Ｘはそれぞれ信号Ｘの送信及び受信
を表す。各プロセスの初期状態はＯである。プロセス１
はＯを初期状態として、プロセス２に対し信号ｄＯを送
信すれば状態ｌに状態遷移し、その状態で信号ａＯを受
信すれば状態２に状態遷移する等の動作をする。また、
プロセス２はＯを初期状態として、プロセス１から信号
ｄｏを受信すれば状態１に状態遷移し、その状態でプロ
セス３へ信号ｄＯを送信すれば状態０に状態遷移する動
作である。プロセス３も同様である。このように、各プ
ロセスの動作は比較的容易に設計できる。しかし、プロ
セス１，２及び３の相互間に論理矛盾がないようにプロ
トコルを設計することは容易ではない。従って、複数の
プロセス間に論理矛盾が生じないようにプロトコルを設
計する方法が必要である。

従来提案されているプロトコル合成法は次の３つに分け
られる。

■Ｎ（≧２）プロセスで構成されるプロトコルをインタ
ラクティブに合成する方法である。即ち、プロトコル仕
様の不足部分を生成したものにプロトコル検証技術を適
用したものである。しかし、プロトコルを自動合成でき
ないという欠点に加え、論理矛盾がなければ更に不足部
分の生成を続行できるが、論理矛盾があれば既に生成さ
れている部分を修正しなければならないという欠点があ
る。

■プロトコル検証技術を併用せずプロトコルを自動的に
合成する方法である。しかし、この方法では対象とする
プロトコルは２プロセスに限られている。しかも、閉路
受信遷移系列を含むプロトコルは論理矛盾を起こしてし
まい合成できない等、合成対象に制限があるという欠点
がある。

■Ｎ（≧２）プロセスで構成されるプロトコルを自動合
成する方法が同一発明者により提案されている（特願昭
６０−４１１８５号）。しかし、この方法も２プロセス
毎に独立に合成するのでプロセス数の増加に伴い合成さ
れるプロトコルの状態数及び状態遷移数が指数関数的に
増加するという欠点があった。

上述した従来技術では、プロセス数の増加に伴い合成さ
れるプロトコルの状態数及び状態遷移数は指数関数的に
増加するという欠点があり、閉路受信遷移系列を含ん“
だプロセスは合成できず、かつ合成されるプロセス数に
よりプロトコルを自動合成できないという問題があった
。

従って、合成されるプロセス数に関係な（効率良く、か
つ閉路受信系列を含んだプロセスを任意の数だけ合成が
できるプロトコル自動合成方式が強（望まれていた。

（発明の目的と特徴）本発明は、上述した従来技術の欠点に鑑みなられたもの
で、論理矛盾が起こらず、プロセス数に応じて合成され
るプロトコルの状態数及び状態遷移数が大幅に増加する
ことなく、かつ閉路受信系列を含めた任意のプロセス数
を効率良く自動合成することができるプロトコルの自動
合成方式を提供することを目的とする。

本発明の特徴は、不完全な状態遷移図の論理矛盾を検査
する手段と、複数のプロセスのうちｉ番目（但し、１＜
Ｈ≦Ｎ）のプロセスの不完全な状態遷移図に対応した他
のプロセスの状態遷移図をｉ番目の不完全な状態遷移図
に埋込む手段と、埋込まれた状態遷移図に基づいて残り
の（ｉ＋ｌ）番目以降全てのプロセスを合わせた状態遷
移図を自動生成する手段と、自動生成された全てのプロ
セスのうち（ｉ＋１）番目のプロセスの状態遷移図とそ
れ以外のプロセスの状態遷移図とに分割する手段を少な
くとも有し、上記４つの手段を（Ｎ−１）回繰り返すこ
とにより各プロセスの状態遷移を完全化してプロトコル
自動合成することにある。

（発明の原理）以下、ＡＢプロトコルを例にとり、本発明の原理につい
て説明する。ここで、プロトコル仕様を説明のための用
語について整理しておく。

大規模なプロトコルは、通常複数のプロセスの集まりで
あるブロックに分けて記述される。ブロックは更に小さ
なブロックに分けて記述されることもある。そこで、プ
ロトコルを次のように階層的に定義する。

レベル１−１　　（１≧１）の１つのプロ・ツク（Ｂ、
Ｃ，Ｌ）で表す。但し、ブロックＢ”　（ＢＩ＋’−−
−’＋　　ＢＮ　）　、　チャネ／Ｌ／ＣＣＢｘＢ　　
。

Ｃｉ　ｊに沿って送受される信号の集合を表す。レベル
０のブロックＢ０をプロトコルといいＲとかく。

Ｂ、＝　（φ、φ、φ）であるレベルｌのブロックをプ
ロセスといいＰ、とかく。Ｒに含まれる全プロセス数を
Ｎとする。なお、プロトコルＲの階層ロックＢ、のレベ
ルだけで示す木構造で表示することができる。図１のＡ
Ｂプロトコルを上述した有向グラフで表すと図２となる
。

プロトコルの記述において、次の仮定をおく。

■　プロセス間の信号伝送に要する時間は有限な非負数
値とする。

■　プロセス内の状Ｂ遷移は決定的で、それに要する時
間は零とする。

■　プロセス相互間で送受される信号の受信順序は送信
順序と同じである。

ブロックの信号、送受信による状態変化は状態遷移図で
表す。レベルｌのブロックＢ、の状態遷き起こす信号の
送受信を表す。記述の便宜上、−ｍｉはＢ（から出るチ
ャネルに沿っての信号の！送信、＋ｍ、はＢ、に入るチャネルに沿っての信！号の受信、ＱｍｌはＢ、の内に含まれるブロックｌ′ Ｂ、　　Ｂ’　＜１）間のチャネルに沿っての信号ａ＋の送受信を表す。例えば、図１のＡＢプロトコルはブロ
ックがプロセスの場合の状態遷移図を表す。

Ｓｓ　”’　（ｓ＋　＋　−−−＊　　Ｓｓ　　）＋Ｃ
ｃ　＝　（Ｃ＋＋−＋ンネルに残った信号の系列である
。

初期状態（Ｓｏ　、Ｃｏ　）はＳｏ　＝　（Ｏｌ、　−
・。

件は次の３つの場合のいずれかが満たされることとする
。

から信号を受信する。（場合３）ブロックＢ、に含まれ
るブロックＢ、（１’　＜１）間のチャネルｚ＋で信号を送信あるいは受信する。状態Ｇが初期状態から
０個以上の状態遷移で到達できるとき、Ｇは到達可能で
あるという。

ブロックＢ１の状態遷移図において状態３ｉ　　ｅ！取いばＢ、から信号を受信（十ｍ）あるいはＢ。

Ｉ　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　ｌに含まれるブロック間の
信号の送受信（Ｏｍ）を表す状態遷移があればｍは定義
されているという。

Ｇ＝　（Ｓ、Ｃ）、Ｓ＝　（ｓ＋　、−−、Ｓｉ　ｌ−
。

あるいはＢ、に含まれるブロック間の信号の送信あるい
は受信（Ｏｍ）は実行可能であるという。

Ｇ＝（Ｓ、Ｃ）＋　　Ｓ＝Ｃ”＋　、−１Ｓｒ　＋　−
’−２到達可能であり、かつＣｊ　ｉの信号の系列の先
頭にｍがあれば、Ｂｊからの受信（十ｍ）は実行可能で
あるという。

本発明で合成されるプロトコル仕様では、入力される各
プロセスの状態遷移図に誤りがなければ、次の４項目の
論理矛盾が生じないようにすることができる。

（１）未定義受信プロトコル仕様で定義されていないが、実行可能である
受信を表す状態遷移。

（２）実行不能送受信プロトコル仕様で定義されているが、実行可能でない送
信あるいは受信を表す状態遷移。

（３）デッドロック全てのプロセスの状態遷移が実行可能でなく、かつプロ
セス間のチャネルに゛残っている信号が全熱ない到達可
能な状態。

（４）無限オーバーフロープロセス間のチャネルに残る信号が無限となる状態。

に分割する。

Ｄ（Ｂｉ）Ｊ　　　　　　　Ｊ　　　　　　　　　　　　　Ｉｌｌ
　　ｉは次のように構成される。

号でなければ、Ｂ、内のブロック間の信号送受信！移部分をそれらの順序性を保持しながら取出したものと
考えることができる。

プロトコルＲの合成問題はプロセス毎の不完全な状態遷
移図が与えられたときにその不足部分を自動生成し各プ
ロセスの完全な状態遷移図を合成する問題として定義す
る。但し、プロセス毎の不完全な状態遷移図の対応は各
プロセスの状態の対応で指定しであると仮定する。しか
し、各プロセスの全ての状態の対応をとる必要はないこ
とに注意されたい。不完全な状態遷移図の状態とその状
態遷移図に基づいて自分生成される状態遷移図の状態は
自動的に対応づけできる。

以上が本発明で用いる用語並びに前提条件である。次に
本発明によるプロトコルの自動合成について、基本原理
を説明する。図３及び図４は本発明による３プロセスの
プロトコルの自動合成方法を説明するための図であり、
図３は（ａｌは予め定められた各プロセス間の信号送受
信関係図、図３（ｂ）は完全化されたプロトコルの合成
例、図４はこれから自動合成を行う必要がある不完全な
プロトコルの図である。従って、以下の説明では図４の
不完全なプロトコルをどのようにして図３（ｂ）の完全
なプロトコルにするかについて説明する。各プロセスの
状態の対応をＰｉ、　Ｐ２．　Ｐ３の状態の３項組で表
す。図４に示すように、プロセス毎の不完全な状態遷移
図として、実線で示すＰｌの送信遷移−１゜Ｐ２の送信
遷移−２，Ｐ３の送信遷移−３が与えられているとする
。ＰＩ、　Ｐ２．　Ｐ３の状態は（０，０，０）。

（１，１，０）、（１，２，１）、　　（２，２，２）
の順番で対応すると仮定する。これらの対応付けが指定
されると、送信遷移−１，−２，−３のみが与えられる
だけで受信遷移＋１．＋２．＋３が自動生成され、結果
としてプロトコルが自動合成される。詳細な合成手順は
次の通りである。まずＰｌの不完全なプロトコル仕様と
して、初期状態Ｏから状態１への送信遷移−１が与えら
れるとする。

すると、これに基づいてＰ２とＰ３を合わせた状Ｂ遷移
図として初期状ＢＯから状態１への受信遷移＋１を自動
生成する。このとき、ＰＬの状ＢＯ及び１はＰ２の状態
Ｏ及び１にそれぞれ対応づけられる。

この状態遷移図を分割して、Ｐ２の状態遷移図として初
期状態０から状態１への受信遷移＋１並びにＰ３の状態
遷移図として初期状ＢＯが得られる。このとき、Ｐ２の
状Ｅｌ及び状態２とＰ３の状態０及び状態１とがそれぞ
れ対応づけられる。

次に、Ｐ２の不完全なプロトコル仕様として、状態ｌか
ら状態２への送信遷移−２が与えられるとする。これを
分割して得られたＰ２の状態遷移図の状態１に送信遷移
−２を埋込むと、Ｐ２の完全なプロトコル仕様として初
期状態Ｏから状態１への受信遷移＋１と状Ｂ１から状Ｂ
２への送信遷移−２が得られる。Ｐ２の状Ｂ１とＰ３の
状！４５０は対応しているので、Ｐ２の状態１に埋込ま
れた送信遷移−２に基づいて受信遷移＋２が自動生成さ
れＰ３の状態０に埋込まれる。このとき、Ｐｌの状Ｂ１
はＰ２の状態１に対応し、Ｐ２の状態ｌはＰ３の状態Ｏ
に対応して、Ｐ３の状態Ｏに受信遷移＋２が埋込まれた
ので、Ｐｌの状態１はＰ３の状態ｌに対応づけされる。

最後に、Ｐ３の不完全なプロトコル仕様として、状態１
から状態２への送信遷移−３が与えられるとする。する
と、Ｐ３の完全なプロトコル仕様として初期状態Ｏから
状態１への受信遷移＋２と状態１から状態２への送信遷
移−３が得られる。又、ＰＬの状態１はＰ３の状態ｌに
対応するので、送信遷移−３に基づいて受信遷移＋３が
自動生成され、Ｐｌの状態１に埋込まれる。するとＰｌ
の完全なプロトコル仕様として初期状態Ｏから１への送
信遷移−１と状態１から状態２への受信遷移＋３が得ら
れる。以上でＰｉ　、　Ｐ２　、Ｐ３で構成されるプロ
トコルが自動合成され、図３（ｂ）に示す完全なプロト
コルが得られる。しかも、各プロセスの状態の対応づけ
は自動的に行われる。

上述の合成手順は次に示す合成２分木に従って行われた
ことになる。

プロトコルＲの階層構造を根付き有向木で表す。

有向木のレベルがプロトコルの階層レベルに対応する。

この有向木が次の条件を満たせば合成２分木という。

（条件）各節点はちょうど２つの子箱点をもち、かつ、
そのうち少なくとも１つの節点は葉節点である。ブロッ
クＢ２　（０≦ｉ≦Ｎ−３）を表す節（ｉ＋１番目のプ
ロセス）を表し、右節点はＮは全プロセス数を表す。

合成２分木に従い各プロセスの不完全なプロトコル仕様
に基づいて完全なプロトコル仕様を合成の完全な状態遷
移図を合成する問題としてとらえることができる。

れるが、両者の状態の対応がとれれば、完全なを生成す
ることができる。そこで、プロトコルの合成問題を次の
ような問題に帰着できる。

合成２分木において、Ｐ、のＢ２に対する状態遷移図Ｄ
　（Ｐ＋　　；　Ｂ２　）＝Ｄ　（Ｐ＋　）、Ｐｚの遷
移図Ｄ　（ＰＨ−１；ＰＨ）が与えられたとき、Ｐ２の
完全な状態遷移図Ｄ　（Ｐｇ　）、Ｐｓの完全な状態遷
移図Ｄ　（ＰＩ　）　、・・・＋ＰＮの完全な状態遷移
図Ｄ（ＰＭ）を自動生成して、未定義受信、実行不能送
受信、デッドロック、無限オーバーフローのないプロト
コルＲを合成させる。

本発明で提案する、Ｎ（≧２）プロセスで構成されるプ
ロトコルの合成法は合成２分木に従い、次の３つのステ
ップでｉ＝ｌからＮ−１まで反復実行される。

以下の記述で、Ｂ＝Ｐ＋　ｕ−・−ＵｐｉはブロックＢ
はプロセスＰ　ｒ　、　’−・、Ｐｉで構成されること
を表す。

ステップ１：Ｐｉ（１≦ｉ≦Ｎ−１）のＢｚ　＝Ｐ、。

１　Ｕ・−・ｕＰ、に対する状態遷移図Ｄ（Ｐｔ；Ｂ２
）が与えられて、Ｄ　（Ｐｚ　　；　Ｐ、ｕ−ＬＩＰｔ
−１）の状態にＤ（Ｐｉ；Ｂｚ）を埋込み、Ｄ　（Ｐ、
　）を合成する。

ステップ２：Ｄ（Ｐ、；Ｂ２）に基づいてＤ　（Ｂｚ　
　ｉＰｔ　）を自動生成し、Ｄ　（Ｐｉ　　；Ｐ　Ｉ　
　Ｕ−、ｐ　ｉ−１）に対応するＤ　（ＢＺ　　；　Ｐ
Ｉ　　Ｕ−、Ｕｐ、−、）の状態に埋込み、Ｄ　（Ｂ　
ｚ　　ジＰ、ｕ−ｕＰ、）を合成する。

ステップ３　：　Ｄ　（Ｂ２　　；　ＰＩ　Ｌｌ−ｕｐ
ｌ　）を分割Ｐ＋　　Ｕ−−Ｕｐｉ　）とする。但し、
ｉ＝１のときはステップ１は必要なく、ステップ２．３
のみでよい。また、１＝Ｎ−１のときはステップ３は必
要がなく、ステップ１．２のみでよい。

ステップ１では■に示すように５つの制限を満たすＤ（
Ｐｔ；Ｂｚ）を■の定義通りに埋込む。

■　与えられるＰ、のＢ２に対する状態遷移図には初め
から論理矛盾を含まないものとする。すなわち、論理矛
盾を含まない状態遷移とは通常衣に示す５つの制限が必
要である。

制限１：図５（ａ）に示すように状態ｋからｉへの送信
遷移−Ｘが存在し、状態ｋからβへの受信遷移系列＋Ｙ
が存在すれば、必ず状態ｉからある状Ｂｊへの受信遷移
系列＋Ｙが存在する。このとき、状Ｃｔからｊへの＋Ｙ
を伝播受信遷移系列という。

制限２：図５山）に示すように状態ｋからｉへの受信遷
移＋Ｘが存在し、状態ｋからｌへの受信遷移系列＋Ｙが
存在し、かつ、ＸとＹの受信チャネルが異なれば、必ず
状態ｉからある状態ｊへの受信遷移系列十Ｙが存在する
。このとき、状態ｉからｊへの＋Ｙを伝播受信遷移系列
という。

制限３：全ての状態は初期状態から０個以上の状態遷移
で到達可能である。

制限４：図５（Ｃ）に示すようにある状ｆｉｋから同じ
状ｇｋへの閉路送信遷移系列−Ｚがない。

制限５：伝播受信遷移系列でないかあるいは有限回の実
行を意味しない閉路受信遷移系列がない。

■　本発明におけるＤ　（Ｐｉ　　；　ＰＩＬｌ−−−
−ＵＰｉ−＋ンの状態ＳにＤ　（Ｐｚ　　；　Ｂｚ　）を埋込むとは次の条件を満
たすように状ＵＳをＤ（Ｐｔ；Ｂｚ）に置換えることで
ある。

（条件）今、Ｓに入る状態遷移をｔ、ｓから出る状態遷
移をｔｏとする。この゛とき、ｔはｔｏは接続している
という、置換えたＤ（Ｐｚ：　Ｂｚ　）の全ての状態遷
移系列を短絡除去し１つの状態にするとｔとｔｏは接続
している。

ステップ２は次の通り実行される。

図６はプロセスＰｔ　（ｉ　＝１．２．　−・・−、Ｎ
）とプロセスＰ、（ｊ＝１，２．　−・−・−、Ｎでか
っｉ〜ｊ）の変換パターンを図示したものであり、変換
パターン（ａ）〜（ｒ）に基づいて（Ｐｉ；Ｂｚ）を分
解し、分解された部分状態遷移図に対応して部分状態遷
移図を生成し、それらを組立てることによりＤ（Ｂｚｉ
Ｐｉ）を自動生成する。なお、図６の変換パターンは一
例にすぎず、これらの変換パターンを組合わせて新たな
変換パターンを作ることも可能である。

Ｄ　（Ｐｉ、Ｉ　　Ｕ・−ｕＰ、；Ｐ、ｕ・−ｕＰ、）
を分割してＤ　（Ｐ、。＋；Ｐ＋ＬＪ−・・ｕＰ、）と
Ｄ　（ＰＬ。２Ｕ−・ＵＰＮ　；Ｐ＋　　ｕ−ｕＰｔ　
）とする。これは状態遷移図の分割に従う。

（実施例）図７は本発明の実施例であり、プロトコルの自動合成装
置のブロック図である。なお、以降の説明では、各プロ
セスの状態遷移図を順次完全化してプロトコルを自動合
成する方法を例にとり説明する。図７における各回路及
びメモリの説明を行う。１は合成処理に使用する各種変
数の初期値を設定する初期設定回路、２は入力したＤ（
Ｐ、；Ｂ２）（１＜ｉ≦Ｎ−１）を蓄積するメモリ、３
３は５つの制限を検査する制限検査回路、４は５つの制
限を満たすＤ（Ｐｉ；Ｂ２）を蓄積するメモリ、５はＤ
　（Ｐｉ　；ＰＩ　ＬＪ・・・−ｕＰｔ−１）にＤ　（
Ｐ＋　　；　Ｂｚ　）を埋込むための埋込回路、６は出
力されるＤ　（Ｐｉ）を蓄積するメモリ、７は変換パタ
ー７　（ａｌ　〜（ｒｌに従いＤ（Ｐｉ　；　Ｂｚ　）
に基づきＤ　（Ｂ：　　；Ｐｔ　）を生成する生成回路
、８はＤ　（ＢＺ　　ｉ　Ｐｉ）を蓄積するメモリ、９
はＤ（Ｂｚ；Ｐ、ｕ−・−ｐ、−＋）にＤ　（Ｂ、；Ｐ
、）を埋込むための埋込回路、１０はＤ　（Ｂ２　　；
Ｐｔ　ｕ−・−・ｕＰｔ　）を蓄積するメモリ、１１は
合成処理の終了を判定すＰ、ｕ・−ｕＰ；）に分割する
分割回路、１３はＤ　（Ｐｉ。Ｉ；ＰＩＵ−ｕＰ、）を
蓄積するメモリ、１４はＤ　（Ｂ２　　　；　Ｐ＋　　
ｕ・−・ｕＰ、）を蓄積するメモリ、１５は変数ｉを１
つ更新する更新回路、１６はＤ　（Ｐ＋　　；　Ｐ＋　
Ｌｌ・・−ｕＰ□−Ｉ）を蓄積するメモリ、１７はＤ　
（Ｂｚ　　；ＰＨｕ−・ＬｆＰｉ−＋）を蓄積するメモ
リである。なお、図中実線は情報の流れ、点線は制御の
流れをそれぞれ示す。

表　　１表１にプロトコル仕様、すなわち、各プロセスる状態遷
移図をメモリ２．６に蓄積する場合の一蓄積形成を表す
。例えば、表１で、プロセス１の状態Ｏで信号ｄｏをプ
ロセス２に送信すると状態１になり、プロセス１の状態
１で信号ａＯをプロセス２から受信すると状態２になる
ことを示す。

送信を−で、受信を十を表す。

図８にＡＢのプロトコルの合成２分木を示す。

又、図９に合成結果を示す。先ず、図９の（ａ）に示す
Ｄ　（Ｐ、　）が与えられるとＤ　（ＰＺＵＰ３；　Ｐ
＋）が変換パターン（ａｌ〜（ｒ）に従い生成される。

次に、図９の（ｂ）に示すようにＤ　（Ｐｚｕ　Ｐｆｆ
　；　ｐ＋）がＤ　（ｐｚ　　；　ＰＩ　）とＤ（Ｐ、
；Ｐ＋）に分割される。最後に、図９の（Ｃ）に示すよ
うに　Ｄ（Ｐｇ；Ｐｌ）にＤ（Ｐｚ；Ｐｌ）を埋込んで
Ｄ　（ｐｇ　）が得られる。同時に、Ｄ　（ｐｚ　　；
　ＰＩ　）に、変換バター７　（ａ）　〜（ｒ）により
Ｄ（Ｐｌ；Ｐ３）から生成されたＤ（Ｐ３　；Ｐｚ）を
埋込んでｏ　（Ｐ３　）が得られる。同図で、点線の状
態遷移はプロセス内の送受信遷移を表す。図９で得られ
たＡＢプロトコルは図１のものと異なるが、実行可能状
態遷移系列は全く等しい。従って、意図されたＡＢプロ
トコルを論理矛盾なく合成できた。

以下、図９の例を用いて図７の実施例の動作を説明する
。状態遷移図Ｄ　（Ｐ□　；Ｂｚ）（１≦ｉ≦Ｎ−１）
は表１の形式で既にメモリ２に蓄積されているとする。

まず、初期設定回路１が動作し、変数ｉを１とし、制限
検査回路３を起動する。制限検査回路３はＤ　（Ｐ；　
　；　Ｂｚ　）が５つの制限をを満たすか否か検査する
。検査に合格すれば、メモリ４に蓄積する。検査に不合
格であれば合成処理を行わない。制限検査回路３で起動
された状態遷移図埋込回路５は、ｉ＝１のときはＤ（Ｐ
、；；Ｂ２　）　＝Ｄ　（ｐ＋　）をそのままメモリ６
に転送蓄積する。ｉ≠１のときはＤ　（Ｐ、；Ｐ、ｕ・
・・ＵＰｔ−＋）の状態にＤ　（Ｐｉ　　；　Ｂ２　）
を埋込んだ結果Ｄ　（Ｐ、）をメモリ６に転送蓄積する
。同時に、制限検査回路３で起動された状態遷移図生成
回路７は変換パターン（ａ）〜（ｒ）に従いＤ（Ｐ、１
Ｂ２）に基づいてＤ　（Ｂ２　；Ｐｉ　）を生成し、メ
モリ８に転送蓄積する。生成回路７は状態遷移図埋込回
路９を起動する。埋込回路９はＤ（Ｂ２；Ｐｉ）をＤ　
＜Ｂｔ　　ｉ　Ｐ　１　　Ｕ・−ｕＰｔ−霞の状態に埋
込んだ結果Ｄ　（Ｂｚ　　；Ｐ、ｕ・−・ｕ　Ｐ　＝　
）をメモリ１０に転送蓄積する。埋込回路９により起動
された合成処理終了の判定回路１１は１＝Ｎ−１であれ
Ｄ（ＰＭ）をメモ１月Ｏに転送蓄積し、合成処理を終了
する。ｉ＃Ｎ−１であれば、状態遷移図分割回路１２を
起動する。分割回路１２はメモリｌＯに蓄積されている
Ｄ　（Ｂｚ　　；Ｐ＋　　ｕ・・−ｕＰｉ）をＰ、ｕ・
−ｕＰｔ）に分割し、それぞれメモリ１３とメモ１月４
に転送蓄積する。分割回路１２は更新回路１５を起動す
る。更新回路１５はｉを１つ増やし更新し、メモリ１３
とメモリ１４に蓄積されているものをそれぞれＤ　（Ｐ
　；　　；　Ｐ　＋　ＬＪ−Ｕ　Ｐ　＋−＋　）とＤ　
（Ｂ２　　；　ＰＩ　　Ｕ’−’ＵＰ（−＋　）　とし
てメモリ１６とメモ１月７に転送蓄積する。同時に、制
限検査回路３を再び起動し、合成処理を続行する。以上
、合成処理が終了するとメＥす６に合成されたプロトコ
ル仕様が蓄積される。

本発明で合成されたプロトコルには前述した４つの論理
矛盾がないことが保証される。

以上、各プロセスの状Ｂ遷移図を順次完全化して自動合
成する方式を例にとり説明したが、各プロセスの不完全
な状態遷移図をまとめて最後に完全化する自動合成方式
も可能である。また、ＡＢプロトコルに限定されること
なく、１１ｈ７ＴＵＰ（Ｔｅｌｅｐｈｏｎｅ　Ｕｓｅｒ
　Ｐａｒｔ　：電話ユーザ一部）プロトコルやＩｓ　Ｄ
　Ｎ　（Ｉｎｔｅｇｒａｔｅｄ　５ｅｒｖｉｃｅｓ　Ｄ
ｉ（ＨｉｔａｌＮｅｔｗｏｒｋ　　：総合交換網）プロ
トコル等にも通用できる。

（発明の効果）、以上詳細に説明したように本発明による方式は従来方式
に比較して、■自動合成されるプロトコルのプロセス数
に制限がなく、かつ閉路受信系列を含んだプロセスも可
能で、■不完全なプロトコル仕様に論理矛盾がなければ
その不足部分を自動生成し論理矛盾がない完全なプロト
コル仕様を効率良（自動合成することが可能であり、そ
の効果は極めて大である。

【図面の簡単な説明】

図１は従来から用いられているＡＢプロトコルの状Ｂ遷
移図、図２は本発明を説明するためのＡＢプロトコルの
信号送受信関係図、図３（ａ）は本発明を説明するため
の予め定められたプロセス間の信号送受信関係図、図３
（ｂ）は本発明を説明するための完全化されたプロトコ
ルの合成図、図４は本発明を説明するための不完全なプ
ロトコルの図、図５は本発明を説明するための論理矛盾
のない状態遷移を説明する図、図６（ａ）〜（ｒｌは本
発明を説明するための任意のプロセスにおける変換パタ
ーン図、図７は本発明の実施例を示すブロック図、図３
は本発明を説明するためのＡＢプロトコルの合成２外米
図、図９　（ａｌ　（ｂｌ　（Ｃ）は本発明によるＡＢ
プロトコルを合成する手順を示す図である。

Claims

【特許請求の範囲】

（１）プロトコルが少なくとも２つ以上の機能的に不完
全なプロセスで構成され、該プロセスの不完全な状態遷
移図を入力として、前記プロセスの状態遷移図を完全化
したものを出力とするプロトコル自動合成方式において
、前記不完全な状態遷移図の論理矛盾を検査する手段と
、前記プロセスのうちｉ番目（但し、１≦ｉ≦Ｎ）のプ
ロセスの不完全な状態遷移図に対応した他のプロセスの
状態遷移図を該ｉ番目の不完全な状態遷移図に埋込む手
段と、埋込まれた状態遷移図に基づいて残りの（ｉ＋１
）番目以降全てのプロセスを合わせた状態遷移図を自動
生成する手段と、該自動生成された全てのプロセスのう
ち（ｉ＋１）番目のプロセスの状態遷移図とそれ以外の
プロセスの状態遷移図とに分割する手段とを備え、前記
検査手段と前記埋込み手段と前記自動生成手段及び分割
手段の各動作を（Ｎ−１）回だけ繰り返して前記各プロ
セス毎に状態遷移図を完全化することにより前記プロト
コルを機能的に完全とするように構成されたことを特徴
とするプロトコル自動合成方式。