Parallel On-line Parsing in Constant Time per Word

An on-line parser processes each word as soon as it is typed by the user, without waiting for the end of the sentence. Thus, in an interactive system, a sentence will be parsed almost immediately after the last word has been presented. The complexity of an on-line parser is determined by the resources needed for the analysis of a single word, as it is assumed that previous words have been processed already. Sequential parsing algorithms like CYK or Earley need $O(n^2)$ time for the $n$-th word. A parallel implementation in $O(n)$ time on $O(n)$ processors is straightforward. In this paper a novel parallel on-line parser is presented that needs $O(1)$ time on $O(n^2)$ processors.