| 講演名 | 1999/12/10 Semi-Right-Terminating : 一意解析可能文法による決定性文脈自由言語族の特徴付け 森田 憲一, 李 佳, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 一意解析可能文法(UPG)は、バックトラックなしに構文解析が実行できるようなある種の生成文法であり、それとその3つの部分族が「決定性Chomsky階層」を形成することが知られている。本論文では、semi-right-terminating文法(SR-G)および、semi-right-terminating一意解析可能文法(SR-UPG)と呼ぶ枠組みを新たに提案し、それらがそれぞれ、文脈自由言語族と決定性文脈自由言語族を正確に特徴づけることを証明する。 |
| 抄録(英) | A uniquely parsable grammar (UPG) introduced by Morita et.al (1997) is a kind of phrase structure grammar, in which parsing can be performed without backtracking. It is known that UPGs and their three subclasses form a "deterministic Chomsky hierarchy". In this paper, we newly introduce a semi-right-terminating grammar (SR-G) and a semi-right-terminating UPG (SR-UPG). We show that the classes of SR-Gs and SR-UPGs exactly characterize the classes of context-free languages and deterministic context-free languages, respectively. |
| キーワード(和) | 決定性文脈自由言語 / 決定性プッシュダウン・オートマトン / 一意解析可能文法 |
| キーワード(英) | deterministic context-free language / uniquely parsable grammar |
| 資料番号 | COMP99-64 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1999/12/10(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | Semi-Right-Terminating : 一意解析可能文法による決定性文脈自由言語族の特徴付け |
| サブタイトル（和） | |
| タイトル（英） | Characterizing the Class of Deterministic Context-Free Languages by Semi-Right-Terminating Uniquely Parsable Grammars |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 決定性文脈自由言語 / deterministic context-free language |
| キーワード(2)（和/英） | 決定性プッシュダウン・オートマトン / uniquely parsable grammar |
| キーワード(3)（和/英） | 一意解析可能文法 |
| 第 1 著者 氏名（和/英） | 森田 憲一 / Kenichi MORITA |
| 第 1 著者 所属（和/英） | 広島大学工学部 Faculty of Engineering Hiroshima University |
| 第 2 著者 氏名（和/英） | 李 佳 / Jia LEE |
| 第 2 著者 所属（和/英） | 広島大学工学部 Faculty of Engineering Hiroshima University |
| 発表年月日 | 1999/12/10 |
| 資料番号 | COMP99-64 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 492 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |