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   Vol.E75-D   No.4   pp.499-508
Publication Date: 1992/07/25
Online ISSN: 
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)>>
Buy this Article

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.