Saarland University
Informatics
Programming Systems
Jochen Setz
Bachelor Thesis
Analyses in the Extensible Dependency Grammar (XDG) framework for dependency grammars are represented in XDG by multigraphs. Grammars consist of a lexicon and a set of principles, and restrict the possible multigraphs. Example principles are "no cycles", "one root" and "zero or one mother", which act together to constrain a dimension of the multigraph to be a tree. Other principles stipulate valency and order constraints. Principles are formalized in a specialized first-order logic.
The XDG Development Kit (XDK) is a grammar development kit for XDG, including a parser implemented using constraint programming in Mozart/Oz. The XDK comes with a principle library of predefined principles, from which grammars can be built as with lego bricks. All principles of the XDG principle library, as laid out in Debusmann 2006, are implemented efficiently as Mozart/Oz constraints.
However, the transformation of a principle formalized in first-order logic into an efficient implementation as a Mozart/Oz constraint is far from trivial, and can only be managed by experts in both Mozart/Oz and the XDK, and even for them, the task is tiresome. This also prohibits typical grammar writers, e.g. computational linguists, from extending the principle library, and testing out new ideas.
In the thesis, we plan to bridge the gap between logically described principles and their efficient implementation as Mozart/Oz constraints by developing a compiler called "PrincipleWriter".
The PrincipleWriter will automatically compile principles specified in first-order logic into efficient implementations as Mozart/Oz constraints. This will allow a larger userbase to make full use of the "extensibility" aspect of XDG, i.e., to add and test new ideas for principles.
Starting from a first prototype, the main objective of the thesis will be on finding out how to automatically optimize the compiled principles. It will be interesting to find out how close these optimization can bring us to the level of efficiency of the already implemented principles in the XDK principle library.
A side objective of the thesis will be the integration of PrincipleWriter with the XDK principle library, e.g. with a GUI to easily add/remove/change/compile principles to the system.