| 講演抄録／キーワード |
| 講演名 |
2006-10-17 13:40
多重文脈自由文法とマクロ文法の生成能力について
○関 浩之・加藤有己（奈良先端大） |
| 抄録 |
（和） |
生成能力が文脈自由文法より大きく文脈規定文法より小さい文法が種々提案されている。
これらの文法のうち、多重文脈自由文法や変数線形(規則右辺に変数が高々1 回しか現れない) マクロ文法はそれらが生成する言語の所属問題が多項式時間可解であることが知られている。
本稿では、変数線形マクロ文法とその部分クラスである両線形マクロ文法について、その生成能力を多重文脈自由文法と比較した結果を述べる。
また、これらの文法に対する構文解析法の生物系列構造予測への応用についても触れる。 |
| （英） |
Several grammars of which generative power is between context-free grammar and context-sensitive grammar were proposed.
Among them, multiple context-free grammar and variable-linear macro grammar are known to be recognizable in polynomial time.
In this paper, the generative power of some subclasses of variable-linear macro grammar and that of multiple context-free grammar are compared in details.
We also mention an application of parsing methods for these grammars
to structure prediction of biological sequences. |
| キーワード |
（和） |
多重文脈自由文法 / マクロ文法 / 文脈自由木文法 / 生成能力 / 線形性 / / / |
| （英） |
multiple context-free grammar / macro grammar / context-free tree grammar / generative power / linearity / / / |
| 文献情報 |
信学技報, vol. 106, no. 289, COMP2006-36, pp. 41-48, 2006年10月. |
| 資料番号 |
COMP2006-36 |
| 発行日 |
2006-10-10 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|