On the Generative Power of Multiple Context-Free Grammars and Macro Grammars

スポンサーリンク

概要

• 論文の詳細を見る

• Several grammars of which generative power is between context-free grammar and context-sensitive grammar were proposed. Among them are macro grammar and tree adjoining grammar. Multiple context-free grammar is also a natural extension of context-free grammars, and is known to be stronger in its generative power than tree adjoining grammar and yet to be recognizable in polynomial time. In this paper, the generative power of several subclasses of variable-linear macro grammars and that of multiple context-free grammars are compared in details.

• 2008-02-01

著者

• SEKI Hiroyuki

  the Graduate School of Information Science, Nara Institute of Science and Technology

• Kato Yuki

  Bioinformatics Center Institute For Chemical Research Kyoto University

• Seki Hiroyuki

  The Graduate School Of Information Science Nara Institute Of Science And Technology

関連論文

• RNA-RNA Interaction Prediction Using Integer Programming with Threshold Cut
• On the Generative Power of Grammars for RNA Secondary Structure(Foundations of Computer Science)
• Prediction of RNA Secondary Structures with Binding Sites Using Dynamic Programming Algorithm
• On the Generative Power of Multiple Context-Free Grammars and Macro Grammars
• Evaluating Effectiveness of Accessibility to Infer RNA-RNA Interactions

スポンサーリンク