| 講演名 | 2021-03-03 重み付き多重文脈自由文法とその性質について 井上 裕介(名大), 関 浩之(名大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 多重文脈自由文法(MCFG)は文字列の組を生成できるようにCFGを拡張した形式文法であり, 構文記述, 生物系列解析等へ応用されている. 本稿では, MCFGの拡張として重み付き多重文脈自由文法(WMCFG)を定義し, 所属問題や空問題といった基本問題の判定可能性や, 和や積などの演算に対する閉包性について考察した. また, 代数的べき級数の拡張として, 多重代数的べき級数を定義し, WMCFGが定義する形式べき級数との等価性を示した. |
| 抄録(英) | Multiple context-free grammar (MCFG) is an extension of context-free grammar that generates tuples of strings. MCFG has been applied to syntax analysis of natural language and RNA structure prediction. This paper gives a definition of weighted multiple context-free grammar (WMCFG) by introducing weights toMCFG. Then, we give polynomial-time algorithms for membership and emptiness problems, and also show the closure properties under operations such as sum, product, and so on. Furthermore, we define multiple algebraic power series, then we show that it is equivalent to formal power series defined by MCFG. |
| キーワード(和) | 重み付き多重文脈自由文法 / 所属問題 / 空問題 / 閉包性 / 代数的べき級数 |
| キーワード(英) | weighted multiple context-free grammar / membership / emptiness / closure property / algebraic power series |
| 資料番号 | SS2020-28 |
| 発行日 | 2021-02-24 (SS) |
| 研究会情報 | |
| 研究会 | SS |
|---|---|
| 開催期間 | 2021/3/3(から2日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 委員長氏名（和） | 小林 隆志(東工大) |
| 委員長氏名（英） | Takashi Kobayashi(Tokyo Inst. of Tech.) |
| 副委員長氏名（和） | 岡野 浩三(信州大) |
| 副委員長氏名（英） | Kozo Okano(Shinshu Univ.) |
| 幹事氏名（和） | 島 和之(広島市大) / 林 晋平(東工大) |
| 幹事氏名（英） | Kazuyuki Shima(Hiroshima City Univ.) / Shinpei Hayashi(Tokyo Inst. of Tech.) |
| 幹事補佐氏名（和） | 小形 真平(信州大) |
| 幹事補佐氏名（英） | Shinpei Ogata(Shinshu Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Software Science |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 重み付き多重文脈自由文法とその性質について |
| サブタイトル（和） | |
| タイトル（英） | Weighted Multiple Context-free Grammars and their Properties |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 重み付き多重文脈自由文法 / weighted multiple context-free grammar |
| キーワード(2)（和/英） | 所属問題 / membership |
| キーワード(3)（和/英） | 空問題 / emptiness |
| キーワード(4)（和/英） | 閉包性 / closure property |
| キーワード(5)（和/英） | 代数的べき級数 / algebraic power series |
| 第 1 著者 氏名（和/英） | 井上 裕介 / Yusuke Inoue |
| 第 1 著者 所属（和/英） | 名古屋大学(略称：名大) Nagoya University(略称：Nagoya Univ.) |
| 第 2 著者 氏名（和/英） | 関 浩之 / Hiroyuki Seki |
| 第 2 著者 所属（和/英） | 名古屋大学(略称：名大) Nagoya University(略称：Nagoya Univ.) |
| 発表年月日 | 2021-03-03 |
| 資料番号 | SS2020-28 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | SS-407 |
| ページ範囲 | pp.1-6(SS), |
| ページ数 | 6 |
| 発行日 | 2021-02-24 (SS) |