On the Generative Power of Grammars for RNA Secondary Structure

Yuki KATO; Hiroyuki SEKI; Tadao KASAMI

doi:10.1093/ietisy/e88-d.1.53

On the Generative Power of Grammars for RNA Secondary Structure

Yuki KATO, Hiroyuki SEKI, Tadao KASAMI

Full Text Views

0

Share
Cite this

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.

Publication: IEICE TRANSACTIONS on Information Vol.E88-D No.1 pp.53-64

Publication Date: 2005/01/01

Publicized

Online ISSN

DOI: 10.1093/ietisy/e88-d.1.53

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)

Category

Cite this

Copy

Yuki KATO, Hiroyuki SEKI, Tadao KASAMI, "On the Generative Power of Grammars for RNA Secondary Structure" in IEICE TRANSACTIONS on Information, vol. E88-D, no. 1, pp. 53-64, January 2005, doi: 10.1093/ietisy/e88-d.1.53.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/information/10.1093/ietisy/e88-d.1.53/_p

Copy

@ARTICLE{e88-d_1_53,
author={Yuki KATO, Hiroyuki SEKI, Tadao KASAMI, },
journal={IEICE TRANSACTIONS on Information},
title={On the Generative Power of Grammars for RNA Secondary Structure},
year={2005},
volume={E88-D},
number={1},
pages={53-64},
abstract={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.},
keywords={},
doi={10.1093/ietisy/e88-d.1.53},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - On the Generative Power of Grammars for RNA Secondary Structure
T2 - IEICE TRANSACTIONS on Information
SP - 53
EP - 64
AU - Yuki KATO
AU - Hiroyuki SEKI
AU - Tadao KASAMI
PY - 2005
DO - 10.1093/ietisy/e88-d.1.53
JO - IEICE TRANSACTIONS on Information
SN -
VL - E88-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2005
AB - 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.
ER -