Parallel On-line Parsing in Constant Time per Word

Nicolaas Sikkel

    Research output: Contribution to journalArticleAcademicpeer-review

    2 Citations (Scopus)
    106 Downloads (Pure)


    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.
    Original languageUndefined
    Pages (from-to)303-310
    Number of pages8
    JournalTheoretical computer science
    Issue number2
    Publication statusPublished - 1993


    • EWI-10845
    • IR-18047
    • METIS-118566
    • HMI-SLT: Speech and Language Technology

    Cite this