逐次性v.s.ストリクト性 －非線形項書換え系の最適戦略にむけて－ （コンパイル技術および一般）

• Item type: SIG Technical Reports(1)
• 公開日: 1996-10-31
• タイトル: 逐次性v.s.ストリクト性 －非線形項書換え系の最適戦略にむけて－ （コンパイル技術および一般）
• タイトル / 言語: en
• タイトル: Sequentiality v.s. Strictness Towards an optimal strategy for nonlinear TRSs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: NTT基礎研究所
• 著者所属(英): en
• 著者所属(英): NTT Basic Research laboratories
• 著者名: 小川, 瑞史
• 著者名(英): Mizuhito, Ogawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，メンバーシップ条件付き非線形項書換え系の最適書換え戦略について，逐次性とストリクト性の観点力から考察し，その二つを比較する．(）逐次性については，正規形の集合によるメンバーシップ条件付き項書換え系が，・制限付き非線形かつ無曖昧ならば，正規形でない項は必須リデックスを持つ．・制限付き非線形ならばNV?逐次性は決定可能であり，さらに無曖昧ならば指標書換え戦略は計算可能である．を示す．(）ストリクト性については，構成子基底の集合によるメンバーシップ条件付き構成子項書換え系が，・制限付き非線形かつ無曖昧ならば，正規形でない項はストリクトリデックスを持つ．を示し，さらに項書換え系に対するストリクト性解析を新たに提案する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper investigates an optimal reduction strategy for a nonlinear term rewriting system (TRS) from sequentiality and strictness viewpoints, and these two are compared. Main results are: (1) For a TRS with membership conditions wrt normal forms, ・if restricted-nonlinear and nonoverlapping, a term not in normal forms has a needed redex. ・ if restricted-nonlinear, NV-suquentiality is decidable. Furthermore, if restricted-nonlinear and nonoverlapping, the index reduction is computable. (2) For a TRS with membership conditions wrt ground constructor terms, ・ If restricted-nonlinear and nonoverlapping, a term not in normal forms has a strict redex. ・ Strictness analysis in the reduction framework is newly proposed.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10485570
• 書誌情報: 情報処理学会研究報告プログラミング（PRO）; 巻 1996, 号 107(1996-PRO-010), p. 67-72, 発行日 1996-10-31
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会