NAISTAR
Advanced Search
Japanese | English

naistar (NAIST Academic Repository) >
学術リポジトリ naistar / NAIST Academic Repository naistar >
テクニカルレポート / Technical Report >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10061/3667

Title: On the generative power of multiple context-free grammars and macro grammars
Authors: Seki, Hiroyuki
Kato, Yuki
セキ, ヒロユキ
カトウ, ユウキ
関, 浩之
加藤, 有己
Issue Date: Sep-2006
Publisher: Nara Institute of Science and Technology
Series/Report no.: Information Science Technical Report ~ TR2006007
Abstract: Several grammars of which generative power is between context-free grammar and context-sensitive grammar were proposed. Among them, multiple context-free grammar and variable-linear macro grammar are known to be recognizable in polynomial time. In this paper, the generative power of some subclasses of variable-linear macro grammar and that of multiple context-free grammar are compared in details. We also mention an application of parsing methods for these grammars to structure prediction of biological sequences.
URI: http://hdl.handle.net/10061/3667
URI: http://library.naist.jp/mylimedio/dllimedio/show.cgi?bookid=100050031&oldid=92673
Fulltext: http://library.naist.jp/mylimedio/dllimedio/show.cgi?bookid=100050031&oldid=92673
ISSN: 0919-9527
Appears in Collections:テクニカルレポート / Technical Report

Files in This Item:

There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Copyright (c) 2007-2012 Nara Institute of Science and Technology All Rights Reserved.
DSpace Software Copyright © 2002-2010  Duraspace - Feedback