| 講演名 | 1997/7/15 簡単な書き換えシステムの共通構造について 赤間 清, 繁田 良則, 宮本 衛市, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 項, 文字列, グラフ, アトムの論理積を含む種々の書き換えシステムが計算機科学や人工知能の分野で使われている. しかし, それらの共通の数学的基礎は確立されていない. 書き換えシステムの理論は, 現在, 書き換え対象ごとに個別に作られている. これまでの理論では, 抽象書き換えシステムがすべての書換えシステムの共通の性質を議論するために使われている. しかしそれは抽象的すぎて, 書換え対象の部分構造を捉えることができない. 本論文では, 書換えシステムの統一的な定式化に至る最初の段階の理論を与える. β書換えシステムと呼ばれる書換えシステムのクラスを提案する. それは公理的に定義された構造(β構造)の上に定義される. β構造は, 多くの書換えシステムの共通構造である「文脈」と「置き換え」の概念を定式化するために使われる. 半Thueシステムやペトリネットなど多くの重要な書換えシステムをβ書換えシステムと見なすことができる. |
| 抄録(英) | Many rewriting systems, including those of terms, strings, graphs, and conjunction of atoms, are used throughout computer science and artificial intelligence. However, there does not exist a common foundation for such systems. At the present time, many of the theories are constructed independently, one for each kind of rewritten object. In the conventional approach, abstract rewriting systems are used to discuss common properties of all rewriting systems. However, they are too abstract to capture properties relating to substructures of objects. This paper aims to provide a first step towards a unified formalization of rewriting systems. A class of rewriting systems, called β rewriting systems, is proposed. It is defined on axiomatically formulated base structures, called β structures, which are used to formalize the concepts of "contexts" and "replacement" common to many rewritten objects. rule class of β rewriting system includes very important systems such as semi-Thue systems and Petri Nets. |
| キーワード(和) | 書き換えシステム / 半Thueシステム / ペトリネット / 抽象書き換えシステム |
| キーワード(英) | rewriting system / semi-Thue system / Petri Net / abstract rewriting system |
| 資料番号 | SS97-14 |
| 発行日 |
| 研究会情報 | |
| 研究会 | SS |
|---|---|
| 開催期間 | 1997/7/15(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Software Science (SS) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 簡単な書き換えシステムの共通構造について |
| サブタイトル（和） | |
| タイトル（英） | On the Common Structure of Simple Rewriting Systems |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 書き換えシステム / rewriting system |
| キーワード(2)（和/英） | 半Thueシステム / semi-Thue system |
| キーワード(3)（和/英） | ペトリネット / Petri Net |
| キーワード(4)（和/英） | 抽象書き換えシステム / abstract rewriting system |
| 第 1 著者 氏名（和/英） | 赤間 清 / Kiyoshi Akama |
| 第 1 著者 所属（和/英） | 北海道大学工学部システム情報工学専攻 Division of System and Information Engineering, Hokkaido University |
| 第 2 著者 氏名（和/英） | 繁田 良則 / Yoshinori Shigeta |
| 第 2 著者 所属（和/英） | 北海道大学工学部システム情報工学専攻 Division of System and Information Engineering, Hokkaido University |
| 第 3 著者 氏名（和/英） | 宮本 衛市 / Eiichi Miyamoto |
| 第 3 著者 所属（和/英） | 北海道大学工学部システム情報工学専攻 Division of System and Information Engineering, Hokkaido University |
| 発表年月日 | 1997/7/15 |
| 資料番号 | SS97-14 |
| 巻番号（vol） | vol.97 |
| 号番号（no） | 163 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |