
For FullText 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.

Efficient Recognition Algorithms for Parallel Multiple ContextFree Languages and for Multiple ContextFree Languages
Ryuichi NAKANISHI Keita TAKADA Hideki NII Hiroyuki SEKI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E81D
No.11
pp.11481161 Publication Date: 1998/11/25 Online ISSN:
DOI: Print ISSN: 09168532 Type of Manuscript: PAPER Category: Automata,Languages and Theory of Computing Keyword: parallel multiple contextfree grammar, multiple contextfree grammar, boolean matrices multiplication, recognition algorithm, formal grammar,
Full Text: PDF(1MB)>>
Summary:
Parallel multiple contextfree grammar (PMCFG) and multiple contextfree grammar (MCFG) were introduced to denote the syntax of natural languages. By the known fastest algorithm, the recognition problem for multiple contextfree language (MCFL) and parallel multiple contextfree language (PMCFL) can be solved in O(n^{e}) time and O(n^{e+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(n^{e3i+1} M(n^{i})) 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.

