| Presentation | 2021-03-03 Weighted Multiple Context-free Grammars and their Properties Yusuke Inoue, Hiroyuki Seki, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | weighted multiple context-free grammar / membership / emptiness / closure property / algebraic power series |
| Paper # | SS2020-28 |
| Date of Issue | 2021-02-24 (SS) |
| Conference Information | |
| Committee | SS |
|---|---|
| Conference Date | 2021/3/3(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Takashi Kobayashi(Tokyo Inst. of Tech.) |
| Vice Chair | Kozo Okano(Shinshu Univ.) |
| Secretary | Kozo Okano(Hiroshima City Univ.) |
| Assistant | Shinpei Ogata(Shinshu Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Software Science |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Weighted Multiple Context-free Grammars and their Properties |
| Sub Title (in English) | |
| Keyword(1) | weighted multiple context-free grammar |
| Keyword(2) | membership |
| Keyword(3) | emptiness |
| Keyword(4) | closure property |
| Keyword(5) | algebraic power series |
| 1st Author's Name | Yusuke Inoue |
| 1st Author's Affiliation | Nagoya University(Nagoya Univ.) |
| 2nd Author's Name | Hiroyuki Seki |
| 2nd Author's Affiliation | Nagoya University(Nagoya Univ.) |
| Date | 2021-03-03 |
| Paper # | SS2020-28 |
| Volume (vol) | vol.120 |
| Number (no) | SS-407 |
| Page | pp.pp.1-6(SS), |
| #Pages | 6 |
| Date of Issue | 2021-02-24 (SS) |