R. Nakanishi et al., Efficient recognition algorithms for parallel multiple context-free languages and for multiple context-free languages, IEICE T INF, E81D(11), 1998, pp. 1148-1161
Parallel multiple context-free grammar (PMCFG) and multiple context-free gr
ammar (MCFG) were introduced to denote the syntax of natural languages. By
the known fastest algorithm, the recognition problem for multiple context-f
ree language (MCFL) and parallel multiple context-free language (PMCFL) can
be solved in O(n(e)) time and O(n(e+1)) time, respectively, where e is a c
onstant which depends only on a given MCFG or PMCFG. In this paper. we prop
ose the following two algorithms. (1) An algorithm which reduces the recogn
ition problem for MCFL to the boolean matrices multiplication problem. (2)
An algorithm which reduces the recognition problem for PMCFL to the recogni
tion problem for MCFL. The time complexity of these algorithms is O(n(e'-3i
'+1).M(n(i'))) where e' and i' are constants which depend only on a given M
CFG or PMCFG, and M(k) is the time needed for multiplying two k x k boolean
matrices. The proposed algorithms are faster than the known fastest algori
thms unless e' = e, i' = 1 for MCFG, and e' = e, i' = 0 for PMCFG.