The Universal Recognition Problems for Multiple Context-Free Grammars and for Linear Context-Free Rewriting Systems

Yuichi KAJI  Ryuichi NAKANISI  Hiroyuki SEKI  Tadao KASAMI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E75-D   No.1   pp.78-88
Publication Date: 1992/01/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Theoretical Foundations of Computing)
Category: 
Keyword: 
multiple context-free grammars,  recognition problem,  computational complexity,  formal language,  

Full Text: PDF(881.6KB)>>
Buy this Article



Summary: 
Multiple context-free grammars (mcfg's) are a subclass of generalized context-free grammars introduced by Pollard in order to describe the syntax of natural languages. First, this paper shows that the universal recognition problem for mcfg's is EXP-POLY time-complete, where the universal recognition problem is the one to decide whether G generates w for a given grammar G and string w. Next, it is shown that the problem for linear context-free rewriting systems introduced by Vijay-Shanker et al., which is a proper subclass of mcfg's, is PSPACE-complete.