PARALLEL ONLINE PARSING IN CONSTANT-TIME PER WORD

An on-line parser processes each word as soon as it is typed by the us er, without waiting for the end of the sentence. Thus, in an interacti ve system, a sentence will be parsed almost immediately after the last word has been presented. The complexity of an on-line parser is deter mined by the resources needed for the analysis of a single word, as it is assumed that previous words have been processed already. Sequentia l parsing algorithms like CYK or Earley need O(n2) time for the nth wo rd. A parallel implementation in 0(n) time on 0(n) processors is strai ghtforward. In this paper a novel parallel on-line parser is presented that needs 0(1) time on 0(n2) processors.