An algorithm for the construction of dependency trees

Gerrit van der Hoeven

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


    A casting system is a dictionary which contains information about words, and relations that can exist between words in sentences. A casting system allows the construction of dependency trees for sentences. They are trees which have words in roles at their nodes, and arcs which correspond to dependency relations. The trees are related to dependency trees in classical dependency syntax, but they are not the same. Formally, casting systems define a family of languages which is a proper subset of the contextfree languages. It is richer than the family of regular languages however. The interest in casting systems arose from an experiment in which it was investigated whether a dictionary of words and word-relations created by a group of experts on the basis of the analysis of a corpus of titles of scientific publications, would suffice to automatically produce reasonable but maybe superficial syntactical analyses of such titles. The results of the experiment were encouraging, but not clear enough to draw firm conclusions. A technical question which arose during the experiment, concerns the choice of a proper algorithm to construct the forest of dependency trees for a given sentence. It turns out that Earley’s well-known algorithm for the parsing of contextfree languages can be adapted to construct dependency trees on the basis of a casting system. The adaptation is of cubic complexity. In fact one can show that contextfree grammars and dictionaries of words and word-relations like casting systems, both belong to a more general family of systems, which associate trees with sequences of tokens. Earley’s algorithm cannot just be adapted to work for casting systems, but it can be generalized to work for the entire large family.
    Original languageEnglish
    Title of host publicationProceedings of the Third International Workshop on Parsing Technologies (IWPT'93)
    Subtitle of host publicationTilburg, Netherlands and Durbuy, Belgium
    Place of PublicationTilburg
    PublisherTilburg University Press
    Publication statusPublished - 27 Jan 1993
    Event3rd International Workshop on Parsing Technologies, IWPT 1993 - Tilburg, Netherlands/Durbuy, Belgium, Netherlands
    Duration: 10 Aug 199313 Aug 1993
    Conference number: 3


    Conference3rd International Workshop on Parsing Technologies, IWPT 1993
    Abbreviated titleIWPT
    CityTilburg, Netherlands/Durbuy, Belgium


    Dive into the research topics of 'An algorithm for the construction of dependency trees'. Together they form a unique fingerprint.

    Cite this