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.
The Universal Recognition Problems for Multiple Context-Free Grammars and for Linear Context-Free Rewriting Systems
Yuichi KAJI Ryuichi NAKANISI Hiroyuki SEKI Tadao KASAMI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1992/01/25
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Theoretical Foundations of Computing)
multiple context-free grammars, recognition problem, computational complexity, formal language,
Full Text: PDF(881.6KB)>>
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.