|
|
JAIST Repository >
b. 情報科学研究科・情報科学系 >
b10. 学術雑誌論文等 >
b10-1. 雑誌掲載論文 >
このアイテムの引用には次の識別子を使用してください:
http://hdl.handle.net/10119/4584
|
| タイトル: | 項書き換えシステムにおける可簡約演算子とその応用 |
| 著者: | 中村, 正樹
緒方, 和博
二木, 厚吉 |
| 発行日: | 2005-04-15 |
| 出版者: | 情報処理学会 |
| 誌名: | 情報処理学会論文誌 |
| 巻: | 46 |
| 号: | SIG 6 (PRO25) |
| 開始ページ: | 47 |
| 終了ページ: | 59 |
| 抄録: | 項書き換えシステムでは, 書き換え規則の適用によって簡約できる項は可約項と呼ばれる.本研究では, この可簡約の概念を演算子に適用し, 可簡約演算子の性質を明らかにする.可簡約演算子とは, その演算子を含む項が可簡約であることと定義する.項は演算子をノードに持つ木構造であり, 項の簡約のしくみには演算子間の区別はない.しかし通常, システムの記述者はモデル上の要素を構成する構成子とその上の関数を表す演算子を区別して考える.可簡約演算子とは, 後者の関数としての演算子が持つべき性質である.本研究では, (1)通常の項, (2)基底項(変数を含まない), (3)あるソートに属する項を簡約対象とした場合に, 演算子が可簡約であるための必要十分条件を示す.直接の成果として, 文脈依存書き換えの正当性の十分条件を得ることができる.文脈依存書き換えは, 書き換えポジションが制限された書き換え関係であり, 正当性は, 書き換え結果が必ず正規形であるという性質である.正当性の十分条件は, 無駄な書き換えや停止しない簡約を避けて正規形を得るための方法を与える.応用として, 隠蔽代数に基づく振舞い仕様に対する可簡約演算子の定義を与える.隠蔽代数における可簡約演算子が, 隠蔽代数において重要な性質であるコヒーレント性の十分条件を与えることを示す. : In term rewriting, a term to which some rewrite rule can be applied is called a reducible term. We apply the notion of reducibility to an operation symbol. A reducible operation symbol is defined as follows: a term having a reducible operation symbol is reducible. A term is a tree-structure whose nodes are operation symbols, and there is no difference between them for mechanism of reduction of terms by rewrite rules. However, when describing a system, the designer should divide them into ones denoting constructors of elements in the model and others denoting functions on the set of the elements. The latter should be given as reducible operation symbols. In this study we give a definition of reducible operation symbols for each of (1) ordinary terms, (2) ground (variable-free) terms, and (3) terms of some sorts. Reducible operation symbols give us a sufficient condition for the correctness of context-sensitive rewriting. This gives us a method to reduce terms into normal form with no waste or non-terminating reduction. As another application of reducibility we also a sufficient condition for behavioral coherence of the hidden algebra. |
| Rights: | 社団法人 情報処理学会, 中村正樹, 緒方和博, 二木厚吉, 情報処理学会論文誌, 46(SIG 6 (PRO25)), 2005, 47-59. ここに掲載した著作物の利用に関する注意: 本著作物の著作権は（社）情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。 Notice for the use of this material: The copyright of this material is retained by the Information Processing Society of Japan (IPSJ). This material is published on this web site with the agreement of the author (s) and the IPSJ. Please be complied with Copyright Law of Japan and the Code of Ethics of the IPSJ if any users wish to reproduce, make derivative work, distribute or make available to the public any part or whole thereof. All Rights Reserved, Copyright (C) Information Processing Society of Japan. |
| URI: | http://hdl.handle.net/10119/4584 |
| 資料タイプ: | publisher |
| 出現コレクション: | b10-1. 雑誌掲載論文 (Journal Articles)
|
このアイテムのファイル:
| ファイル |
記述 |
サイズ | 形式 |
|---|
| 6466.pdf | | 218Kb | Adobe PDF | 見る/開く |
|
当システムに保管されているアイテムはすべて著作権により保護されています。
|
