通信プロトコルにおけるオーバーフローの多項式時間検証法 （並行分散システムの記述と検証）

• Item type: SIG Technical Reports(1)
• 公開日: 1986-12-12
• タイトル: 通信プロトコルにおけるオーバーフローの多項式時間検証法 （並行分散システムの記述と検証）
• タイトル / 言語: en
• タイトル: A Polynomial Time Validation Algorithm for Overflows in Communication Protocols
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京工業大学物理情報工学専攻
• 著者所属: 東京工業大学物理情報工学専攻
• 著者所属(英): en
• 著者所属(英): Dpt. of Information Processing Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Dpt. of Information Processing Tokyo Institute of Technology
• 著者名: 菅沼, 知久; 黒沢, 馨
• 著者名(英): Tomohisa, Suganuma; Kaoru, Kurosawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 通信プロトコルは、多くの場合、2つの有限状態機械間の通信という形でモデル化される。この様にモデル化されたプロトコルにおいて、メッセージが一種類の場合、デッドロックの検証は状態数に関する多項式時間でできることが既に証明されている。本稿はメッセージが一種類の場合、無限オーバーフローの検証も多項式時間でできることを示すものである。この結果は、有限オーバーフローの検証時間の上限をあたえるとともに、全てのメッセージを一種類に変換したプロトコルにオーバーフローが存在しなければ、元のプロトコルにもオーバーフローが存在しないという意味において重要である。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Many communication protocols are modeled by two communicating finite state machines. A polynomial time algorithm for deadlock detection has been known for the protocols with one type message. This paper shows a polynomial time algorithm which detects infinite overflows in such protocols. The result is useful because any protocol is free from overfolows if its all different messages are converted to one type and no overflow exists in the modified protocol.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10485570
• 書誌情報: 情報処理学会研究報告プログラミング（PRO）; 巻 1986, 号 83(1986-PRO-009), p. 17-24, 発行日 1986-12-12
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会