|
|
Please login using the form on menu list.
It is required to login for Full-Text PDF.
|
On the Generative Power of Grammars for RNA Secondary Structure
Yuki KATO
Hiroyuki SEKI
Tadao KASAMI
Publication
IEICE TRANSACTIONS on Information and Systems Vol.E88-D No.1 pp.53-64
Publication Date: 2005/01/01
Online ISSN:
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category:
Keyword:
RNA secondary structure,
pseudoknot,
multiple context-free grammar,
tree adjoining grammar,
Full Text: PDF(389.8KB)
Summary:
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.
|
|
