- 著者
-
KATO Yuki
SEKI Hiroyuki
KASAMI Tadao
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- IEICE transactions on information and systems (ISSN:09168532)
- 巻号頁・発行日
- vol.88, no.1, pp.53-64, 2005-01-01
- 被引用文献数
-
7
Several grammars have been proposed for representing RNA secondary structure including pseudoknots such as simple linear tree adjoining grammar (sl-tag), extended sl-tag (esl-tag) and RNA pseudoknot grammar (rpg). The main purpose of this paper is to compare the generative power of these grammars by identifying them as subclasses of multiple context-free grammars (mcfg). Specifically, it is shown that the class of languages generated by esl-tag (ESL-TAL) properly includes the class of languages generated by sl-tag (SL-TAL) and the class of languages generated by cfg. Also, we show that the class of languages generated by rpg coincides with the class of languages generated by mcfg with dimension one or two and rank one or two. Furthermore, it is shown that SL-TAL is a full trio and ESL-TAL is a substitution closed full AFL.