On the Generative Power of Grammars for RNA Secondary Structure(<Special Section>Foundations of Computer Science)
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 社団法人電子情報通信学会の論文
- 2005-01-01
著者
-
Kato Yoji
Graduate School Of Human Sci. And Environment Univ. Of Hyogo
-
KATO Yoji
School of Human Science and Environment, University of Hyogo
-
KASAMI Tadao
the Graduate School of Information Science, Nara Institute of Science and Technology
-
KOUMOTO Takuya
Graduate School of Information Science, Nara Institute of Science and Technology
-
Koumoto Takuya
Okayama University
-
Kato Y
School Of Human Science And Environment University Of Hyogo
-
Seki H
Graduate School Of Information Science Nara Institute Of Science And Technology
-
KATO Yuki
the Graduate School of Information Science, Nara Institute of Science and Technology
-
SEKI Hiroyuki
the Graduate School of Information Science, Nara Institute of Science and Technology
-
Kato Yuriko
Department Of Geriatrics Nagoya University Graduate School Of Medicine
-
Koumoto T
Hiroshima City Univ. Hiroshima Jpn
-
Seki Hiroyuki
The Graduate School Of Information Science Nara Institute Of Science And Technology
関連論文
- PJ-310 Exercise Training Alters Left Ventricular Geometry and Improves Heart Failure in Dahl Salt-Sensitive Hypertensive Rats: Possible Role of Coronary Angiogenesis(Heart failure, basic(06)(M),Poster Session(Japanese),The 72nd Annual Scientific Meeting o
- PJ-305 Angiotensin-Converting Enzyme Inhibition Promotes Myocardial Capillary Growth in the Failing Heart of Dahl Salt-Sensitive Hypertensive Rats(Heart failure, basic(06)(M),Poster Session(Japanese),The 72nd Annual Scientific Meeting of the Japanese Circ
- Preparation of Monoclonal Antibodies Cross-Reactive with Orthopoxviruses and Their Application for Direct Immunofluorescence Test
- MAP and LogMAP Decoding Algorithms for Linear Block Codes Using a Code Structure(Special Section on Information Theory and Its Applications)
- A Recursive Maximum Likelihood Decoding Algorithm for Some Transitive Invariant Binary Block Codes
- A Sufficient Condition for Ruling Out Some Useless Test Error Patterns in Iterative Decoding Algorithms
- Low Weight Subtrellises for Binary Linear Block Codes and Their Applications
- Error Performance of Multilevel Block Coded 8-PSK Modulations Using Unequal Error Protection Codes for the Rayleigh Fading Channel
- An Improved Union Bound on Block Error Probability for Closest Coset Decoding
- On Branch Labels of Parallel Components of the L-Section Minimal Trellis Diagrams for Binary Linear Block Codes
- On Structural Complexity of the L-Section Minimal Trellis Diagrams for Binary Linear Block Codes (Special Section on Information Theory and Its Applications)
- Structural Analysis of Minimum Weight Codewords of the Extended (32, 21, 6) and (64, 45, 8) BCH Codes Using Invariance Property(HISC2006)
- The structure of the set of minimum weight codewords of the extended (32,21,6) and (64,45,8) BCH codes
- Sufficient Conditions for Ruling-Out Useless Iterative Steps in a Class of Iterative Decoding Algorithms (Special Section on Information Theory and Its Applications)
- The Weight Distributions of Cosets of the Second-Order Reed-Muller Code of Length 128 in the Third-Order Reed-Muller Code of Length 128
- A Method for Computing the Weight Distribution of a Block Code by Using Its Trellis Diagram (Special Section on Information Theory and Its Applications)
- ヒト血漿超低密度リポ蛋白の酸化とNε-ヘキサノイールリジンの生成
- Immunohistochemical Detection of Oxidative Stress Biomarkers, Dityrosine and N^ε-(hexanoyl)lysine, and C-Reactive Protein in Rabbit Atherosclerotic Lesions
- 6-Methylsulfinylhexyl Isothiocyanate, an Antioxidant Derived from Wasabia japonica MATUM, Ameliorates Diabetic Nephropathy in Type 2 Diabetic Mice
- The Protective Effects of Tetrahydrocurcumin on Oxidative Stress in Cholesterol-fed Rabbits
- Increase in Oxidative Stress in Kidneys of Diabetic Akita Mice(Food & Nutrition Science)
- Cyanidin 3-O-β-D-Glucoside Attenuates the Hepatic Ischemia-Reperfusion Injury through a Decrease in the Neutrophil Chemoattractant Production in Rats
- Effects of Gliclazide on Low-density Lipoprotein Oxidizability and Atherosclerosis in Cholesterol-fed Rabbits
- An Improved Method for Formal Security Verification of Cryptographic Protocols
- A System for Deciding the Security of Cryptographic Protocols (Special Section on Cryptography and Information Security)
- Dose-dependent Changes in Brain 5-Hydroxyindoles Caused by Caffeine in Rats
- Performance Analysis for Binary Image of Linear Block Codes over an Extended Field of GF(2)
- Adaptive Recursive Maximum Likelihood Decoding Based on the Coarsest Parallel Concatenation Decomposition : Evaluation of the Decoding Complexity by Simulation
- Soft-Input Soft-Output Decoding Algorithm Based on Iterative Minimum Distance Search for Reed-Muller Codes
- Selecting the Search Centers of h-Chase Decoding Algorithms by Simulation
- The Optimal Sectionalized Trellises for the Generalized Version of Viterbi Algorithm of Linear Block Codes and Its Application to Reed-Muller Codes
- A Formal Approach to Detecting Security Flaws in Object-Oriented Databases (Special Issue on New Generation Database Technologies)
- An Authorization Model for Object-Oriented Databases and Its Efficient Access Control
- Assignment of Data Types to Words in a Natural Language Specification
- Implementation of Natural Language Specifications of Communication Protocols by Executable Specifications
- A Translation Method from Natural Language Specifications of Communication Protocols into Algebraic Specifications Using Contextual Dependencies
- RNA Pseudoknotted Structure Prediction Using Stochastic Multiple Context-Free Grammar
- On the Generative Power of Grammars for RNA Secondary Structure(Foundations of Computer Science)
- RIGHT-LINEAR FINITE PATH OVERLAPPING REWRITE SYSTEMS EFFECTIVELY PRESERVE RECOGNIZABILITY
- A Soft-Decision Iterative Decoding Algorithm Using a Top-Down and Recursive Minimum Distance Search(Special Section on Information Theory and Its Applications)
- An Evaluation Method of the Block Error Probability by Using a Low-Weight Sub-Trellis Diagram
- Peroxynitrite Scavenging Activities of Aromatic Compounds Isolated from Konnyaku, Amorphophallus konjac K. Koch.(Food & Nutrition Science)
- Effects of Peroxidase and Hydrogen Peroxide on the Dityrosine Formation and the Mixing Characteristics of Wheat-Flour Dough
- Layered Transducing Term Rewriting System and Its Recognizability Preserving Property (Special Issue on Selected Papers from LA Symposium)
- Termination Property of Inverse Finite Path Overlapping Term Rewriting System is Decidable
- A Polynomial-Time Recognizable Subclass of Lexical-Functional Grammars
- A Note on Inadequacy of the Model for Learning from Queries
- Finite State Translation Systems and Parallel Multiple Context-Free Grammars
- The Universal Recognition Problems for Multiple Context-Free Grammars and for Linear Context-Free Rewriting Systems
- Selection Method of Test Patterns in Soft-Decision Iterative Bounded Distance Decoding Algorithms(Coding Theory)(Information Theory and Its Applications)
- Selection of Search Centers in Iterative Soft-Decision Decoding Algorithms(Special Section on Information Theory and Its Applications)
- An Improvement to GMD-Like Decoding Algorithms(Special Section on Information Theory and Its Applications)
- Development and preliminary application of high-performance liquid chromatographic assay of urinary metabolites of diazepam in humans
- Immunochemical Detection of Food-Derived Isothiocyanate as a Lysine Conjugate
- Reduced Complexity Iterative Decoding Using a Sub-Optimum Minimum Distance Search(Cording Theory)(Information Theory and Its Applications)
- On the Generative Power of Multiple Context-Free Grammars and Macro Grammars