文献

J-GLOBAL ID：202202233221322797   整理番号：22A1074711

重み付き文脈自由文法の曖昧さ階層について

An Ambiguity Hierarchy of Weighted Context-free Grammars

著者 (3件)： INOUE Yusuke (Nagoya Univ.) ,  HASHIMOTO Kenji (Nagoya Univ.) ,  SEKI Hiroyuki (Nagoya Univ.)
資料名： 電子情報通信学会技術研究報告(Web)  (IEICE Technical Report (Web))
巻： 121  号： 407(COMP2021 31-39)  ページ： 1-7 (WEB ONLY)  発行年： 2022年02月27日 
JST資料番号： U2030A  ISSN： 2432-6380  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 重み付き文脈自由文法(WCFG)とは,文脈自由文法(CFG)の重み付きの拡張であり,その性質について盛んに研究が行われている.また,重み付きオートマトン(WA)に関する性質として,tropical半環上の無曖昧なWA,有限曖昧なWA,多項式曖昧なWA,一般のWAが,それぞれ異なる表現能力を持つことが知られている.そこで,tropical半環上のWCFGについても同様の曖昧さ階層が存在することを,拡張されたOgden’s lemmaを用いて証明する.さらに証明された曖昧さ階層が,CFGの既知の曖昧さ階層とは異なるものであることを示す.(著者抄録)

シソーラス用語： *文脈自由文法 ,  *曖昧さ ,  *階層構造 ,  重みづけ ,  代数系 ,  定理
準シソーラス用語： 階層 ,  半環 ,  補題

分類 (1件)： 自然語処理  (JE06000L)

引用文献 (9件)：

• A. Chattopadhyay, F. Mazowiecki, A. Muscholl and C. Riveros, Pumping Lemmas for Weighted Automata, CoRR abs/2001.06272,2020.
• N. Chomsky and M. P. Schützenberger, The Algebraic Theory of Context-free Languages, Studies in Logic and the Foundations of Mathematics 26, 118-161, 1959.
• M. Droste, W. Kuich and H. Vogler, Handbook ofWeighted Automata, Springer Science & Business Media, 2009.
• R. Durbin, S. R. Eddy, A. Krogh and G. Mitchison, Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids, Cambridge University Press, 1998.
• J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.

タイトルに関連する用語 (3件)： 文脈自由文法 ,  曖昧さ ,  階層