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.- Anthology ID:
- 1993.iwpt-1.9
- Volume:
- Proceedings of the Third International Workshop on Parsing Technologies
- Month:
- August 10-13
- Year:
- 1993
- Address:
- Tilburg, Netherlands and Durbuy, Belgium
- Editors:
- Harry Bunt, Robert Berwick, Ken Church, Aravind Joshi, Ronald Kaplan, Martin Kay, Bernard Lang, Makoto Nagao, Anton Nijholt, Mark Steedman, Henry Thompson, Masaru Tomita, K. Vijay-Shanker, Yorick Wilks, Kent Wittenburg
- Venue:
- IWPT
- SIG:
- SIGPARSE
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 89–100
- Language:
- URL:
- https://aclanthology.org/1993.iwpt-1.9
- DOI:
- Cite (ACL):
- Gerrit F. van der Hoeven. 1993. An Algorithm for the Construction of Dependency Trees. In Proceedings of the Third International Workshop on Parsing Technologies, pages 89–100, Tilburg, Netherlands and Durbuy, Belgium. Association for Computational Linguistics.
- Cite (Informal):
- An Algorithm for the Construction of Dependency Trees (van der Hoeven, IWPT 1993)
- PDF:
- https://preview.aclanthology.org/nschneid-patch-4/1993.iwpt-1.9.pdf