In this paper, we present algorithms for parsing general tree-adjoinin
g languages (TALs). Tree-adjoining grammars (TAGs) have been proposed
as an elegant formalism for natural languages. It was an open question
for the past ten years as to whether TAL parsing can be done in time
o(n(6)). We settle this question affirmatively by presenting an O(n(3)
M(n))-time algorithm, where M (k) is the time needed for multiplying
two Boolean matrices of size k x k each. Since O (k(2.376)) is the cur
rent best-known value for M(k), the time bound of our algorithm is O(n
(5.376)). On an exclusive-read exclusive-write parallel random-access
machine (EREW PRAM), our algorithm runs in time O(n log n) using (n(2)
M(n))/log n processors. In comparison, the best-known previous paralle
l algorithm had a run time of O(n) using n(5) processors (on a systoli
c-array machine). We also present algorithms for parsing context-free
languages (CFLs) and TALs whose worst-case run times are O(n(3)) and O
(n(6)), respectively, but whose average run times are better. Therefor
e, these algorithms may be of practical interest.