Efficient Recognition Algorithms for Parallel Multiple Context-Free Languages and for Multiple Context-Free Languages

Ryuichi NAKANISHI  Keita TAKADA  Hideki NII  Hiroyuki SEKI  

IEICE TRANSACTIONS on Information and Systems   Vol.E81-D   No.11   pp.1148-1161
Publication Date: 1998/11/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Automata,Languages and Theory of Computing
parallel multiple context-free grammar,  multiple context-free grammar,  boolean matrices multiplication,  recognition algorithm,  formal grammar,  

Full Text: PDF(1MB)>>
Buy this Article

Parallel multiple context-free grammar (PMCFG) and multiple context-free grammar (MCFG) were introduced to denote the syntax of natural languages. By the known fastest algorithm, the recognition problem for multiple context-free language (MCFL) and parallel multiple context-free language (PMCFL) can be solved in O(ne) time and O(ne+1) time, respectively, where e is a constant which depends only on a given MCFG or PMCFG. In this paper, we propose the following two algorithms. (1) An algorithm which reduces the recognition problem for MCFL to the boolean matrices multiplication problem. (2) An algorithm which reduces the recognition problem for PMCFL to the recognition problem for MCFL. The time complexity of these algorithms is O(ne-3i+1 M(ni)) where e and i are constants which depend only on a given MCFG or PMCFG, and M(k) is the time needed for multiplying two k k boolean matrices. The proposed algorithms are faster than the known fastest algorithms unless e=e, i=1 for MCFG, and e=e, i=0 for PMCFG.