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 Parallel Multiple Context-Free Grammars and for Their Subclasses
Yuichi KAJI Ryuichi NAKANISHI Hiroyuki SEKI Tadao KASAMI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1992/07/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Automaton, Language and Theory of Computing
parallel multiple context-free grammars, universal recognition problem, computational complexity, formal language,
Full Text: PDF(810.4KB)>>
Parallel multiple context-free grammars (pmcfg's) and multiple context-free grammars (mcfg's) were introduced as extensions of context-free grammars to describe the syntax of natural languages. Pmcfg's and mcfg's deal with tuples of strings, and it has been shown that the universal recognition problem for mcfg's is EXP-POLY time-complete where the universal recognition problem is the problem to decide whether G generates w for a given grammar G and string w. In this paper, the universal recognition problems for the class of pmcfg's and for the subclass of pmcfg's with the information-lossless condition are shown to be EXP-POLY time-complete and PSPACE-complete, respectively. It is also shown that the problems for pmcfg's and for mcfg's with a bounded dimension are both -complete and those for pmcfg's and for mcfg's with a bounded degree are both -complete. As a corollary, the problem for modified head grammars introduced by Vijay-Shanker, et al. to define the syntax of natural languages is shown to be in deterministic polynomial time.