For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On the Generative Power of Multiple Context-Free Grammars and Macro Grammars
Hiroyuki SEKI Yuki KATO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2008/02/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Formal Language Theory
multiple context-free grammar, macro grammar, context-free tree grammar, generative power, linearity,
Full Text: PDF(347.8KB)>>
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.