An algorithm for the construction of dependency trees

Gerrit F. van der Hoeven

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

    Abstract

    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 publicationCLIN 3
    Subtitle of host publication3rd Computational Linguistics in the Netherlands Meeting
    Place of PublicationTilburg
    PublisherTilburg University Press
    Pages59-70
    Publication statusPublished - 25 Jan 1993
    Event3rd Meeting on Computational Linguistics in the Netherlands, CLIN 1992 - Tilburg, Netherlands
    Duration: 30 Oct 199230 Oct 1992

    Conference

    Conference3rd Meeting on Computational Linguistics in the Netherlands, CLIN 1992
    Abbreviated titleCLIN
    CountryNetherlands
    CityTilburg
    Period30/10/9230/10/92

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

  • Cite this

    van der Hoeven, G. F. (1993). An algorithm for the construction of dependency trees. In CLIN 3: 3rd Computational Linguistics in the Netherlands Meeting (pp. 59-70). Tilburg: Tilburg University Press.