| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2019-01-16 09:50 項書換えにおけるナローイング計算木のベーシックナローイングへの拡張 ○前田侑也・西田直樹・酒井正彦・小林倫也（名大）  MSS2018-68 SS2018-39 |
|
| 抄録 | （和） | 項書換え系（TRS）のナローイング計算とは，書換えに必要な代入を単一化により求め，その代入を適用して書換えを行う計算であり，すべての最内ナローイングにより導出される代入すべてを表す有限の木（ナローイング計算木）を生成する方法が提案されている．先行研究で構文決定的な条件付き項書換え系（SDCTRS）に拡張されたナローイング計算木は，与えられた最初の項からの最内ナローイング計算の解（代入）のすべてを生成する正規木文法で表現される．しかし，最内ナローイングに対応する書換えは構成子書換えに限定されている．%ため，ナローイング計算木を利用して解析できる書換えは構成子書換えに限定されていた．本稿では，ナローイング計算木が扱うナローイング計算をベーシックナローイングに拡張する．そして，紐解き後に右線形なTRSになるSDCTRSの書換えをベーシック書換えで模倣できることを示し，拡張したナローイング計算木を利用してそのようなSDCTRSの書換えの解析を可能にする．具体的には，右線形な正規CTRSの合流性証明への応用を示す． |
| （英） | Narrowing computation of a term rewriting system is an extension of rewriting by replacing matching with unification, which computes a most general unifier to apply a rewrite rule, resulting in a term obtained by applying the rewrite rule. A method to, given a system and an initial goal, generate a finite tree, so-called a narrowing tree, that represents all possible substitutions derived by innermost narrowing has been proposed. A narrowing tree that has been extended to syntactically deterministic conditional term rewriting systems (SDCTRSs) in our previous work can be represented as a regular tree grammar that generates all possible constructor substitutions obtained from innermost narrowing derivations from a given initial term to a ground term corresponding to an expected goal. Unfortunately innermost narrowing is a counterpart of constructor-based rewriting. In this article, we extend narrowing trees to basic narrowing. We show that every rewriting sequence of a terminating ultra-right-linear SDCTRS can be simulated by basic rewriting, and thus the extension enables us to apply the extended narrowing trees to analysis of such SDCTRSs. To be more precise, we show an application of extended narrowing trees to proving confluence of a right-linear normal CTRS. | |
| キーワード | （和） | 条件付き項書換え系 / ナローイング / 正規木文法 / 合流性 / / / / |
| （英） | conditional term rewriting system / narrowing / regular tree grammar / confluence / / / / | |
| 文献情報 | 信学技報, vol. 118, no. 385, SS2018-39, pp. 73-78, 2019年1月. | |
| 資料番号 | SS2018-39 | |
| 発行日 | 2019-01-08 (MSS, SS) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | MSS2018-68 SS2018-39 |
|
| 研究会情報 | |
| 研究会 | MSS SS |
| 開催期間 | 2019-01-15 - 2019-01-16 |
| 開催地（和） | 沖縄県青年会館 |
| 開催地（英） | |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | SS |
| 会議コード | 2019-01-MSS-SS |
| 本文の言語 | 日本語 |
| タイトル（和） | 項書換えにおけるナローイング計算木のベーシックナローイングへの拡張 |
| サブタイトル（和） | |
| タイトル（英） | Extending Narrowing Trees to Basic Narrowing in Term Rewriting |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 条件付き項書換え系 / conditional term rewriting system |
| キーワード(2)（和/英） | ナローイング / narrowing |
| キーワード(3)（和/英） | 正規木文法 / regular tree grammar |
| キーワード(4)（和/英） | 合流性 / confluence |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 前田 侑也 / Yuya Maeda / マエダ ユウヤ |
| 第1著者 所属（和/英） | 名古屋大学 (略称： 名大) Nagoya University (略称： Nagoya Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 西田 直樹 / Naoki Nishida / ニシダ ナオキ |
| 第2著者 所属（和/英） | 名古屋大学 (略称： 名大) Nagoya University (略称： Nagoya Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 酒井 正彦 / Masahiko Sakai / サカイ マサヒコ |
| 第3著者 所属（和/英） | 名古屋大学 (略称： 名大) Nagoya University (略称： Nagoya Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 小林 倫也 / Tomoya Kobayashi / コバヤシ トモヤ |
| 第4著者 所属（和/英） | 名古屋大学 (略称： 名大) Nagoya University (略称： Nagoya Univ.) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2019-01-16 09:50:00 |
| 発表時間 | 25分 |
| 申込先研究会 | SS |
| 資料番号 | MSS2018-68, SS2018-39 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | no.384(MSS), no.385(SS) |
| ページ範囲 | pp.73-78 |
| ページ数 | 6 |
| 発行日 | 2019-01-08 (MSS, SS) |
[研究会発表申込システムのトップページに戻る]