ω書き換えシステムの準同型定理と到達不可能性

• 赤間 清

  北海道大学 工学部 システム情報工学専攻

• 繁田 良則

  北海道大学 工学部 システム情報工学専攻

• 宮本 衛市

  北海道大学 工学部 システム情報工学専攻

書誌事項

タイトル別名

• Homomorphisms Theorem and Unreachability for ω Rewriting Systems

抄録

ω構造と呼ばれる抽象構造は,多くの書換えシステムに共通の概念である「代入」、「文脈」、「置き換え」を定式化するために使われる.ω書換えシステムと呼ばれる書き換えシステムのクラスは、ω構造の上に定義され、項書き換えシステム,文字列書き換えシステム,ペトリネットなどの重要な書き換えシステムを含んでいる。本論文では、ω構造に対する準同型写像を導入し、ω書換えシステムに関する準同型定理を証明する。また、準同型定理をω書換えシステムの到達不可能問題の解決に応用する方法を示す。
An abstract structure called ω structure is used to formalize the concepts of "substitutions," "contexts," and "replacement" common to many rewriting systems. A class of rewriting systems, called ω rewriting systems, has been defined on ω structures and includes very important systems such as term rewriting systems, string rewriting systems, and Petri Nets. In this paper, we introduce a concept of homomorphism for ω rewriting systems and prove a homomorphism theorem for ω rewriting systems. We also explain how to apply the homomorphism theorem to solve unreachability problems for ω rewriting systems.

収録刊行物

• 電子情報通信学会技術研究報告. KBSE, 知能ソフトウェア工学

  電子情報通信学会技術研究報告. KBSE, 知能ソフトウェア工学 99 (426), 39-46, 1999-11-12

  一般社団法人電子情報通信学会

キーワード

• 書き換えシステム
• 準同型写像
• 準同型定理
• 到達不可能性

詳細情報

• CRID: 1571698602294157824
• NII論文ID: 110003299463
• NII書誌ID: AN10386841
• 本文言語コード: en
• データソース種別:
  • CiNii Articles