A Relational Syntax-Semantics Interface Based on Dependency Grammar

Ralph Debusmann, Denys Duchier, Alexander Koller, Marco Kuhlmann, Gert Smolka, Stefan ThaterCOLING 2004 · OpenReview

Abstract: Ralph Debusmann, Denys Duchier, Alexander Koller, Marco Kuhlmann, Gert Smolka, Stefan Thater. COLING 2004: Proceedings of the 20th International Conference on Computational Linguistics. 2004.

Introduction

In traditional linguistic frameworks, such as Montague grammar, the mapping from syntax to semantics is typically treated as a functional one-way process: the syntactic structure of a sentence deterministically dictates its meaning. However, natural language often defies this simple mapping due to semantic ambiguity (e.g., quantifier scope) and generation ambiguity (multiple syntactic realizations for one meaning). This paper introduces Extensible Dependency Grammar (XDG), a framework that reimagines this interface as a multi-way relation. By employing constraint-based parsing, XDG allows information to flow concurrently between linguistic levels, enabling semantic insights to resolve syntactic ambiguities and vice versa.

Methodology: Extensible Dependency Grammar

The core of XDG lies in its representation of sentences as multi-dimensional graphs. Rather than a single tree, a sentence is modeled as a collection of graphs across various dimensions, such as Immediate Dominance (ID), Linear Precedence (LP), and Predicate-Argument structure.

Multi-dimensional dependency graphs and lexicon entries for 'what does John eat'.

Crucially, all dimensions share the same set of nodes—the words of the sentence. The lexicon acts as a synchronizer, defining word properties across all dimensions simultaneously. XDG utilizes multi-dimensional principles to constrain interactions between these layers. For instance, a linking principle might require a semantic "agent" to correspond to a syntactic "subject."

Parsing in XDG is implemented as a Constraint Satisfaction Problem (CSP) using the Mozart/Oz system. Instead of a linear pipeline, the parser uses propagation: confirming information in one dimension immediately prunes the search space in others.

Linguistic Applications and Disambiguation

The authors demonstrate XDG's capabilities through hand-crafted grammar fragments for English, focusing on complex phenomena like quantifier scope ambiguity and prepositional phrase attachment.

Predicate-argument structure for 'every student reads a book'.

In the case of "Every student reads a book," XDG can represent multiple semantic readings while maintaining a single syntactic structure. The relational nature of the interface allows the system to handle $m$-to-$n$ mappings naturally, facilitating both parsing (text to meaning) and generation (meaning to text) within the same constraint-based framework.

Key Insights and Results

The "aha moment" of XDG is concurrent information flow. Semantic selectional preferences can flow "backwards" to prune incorrect syntactic parses early in the process. This generalizes the concept of underspecification, allowing partial information on any dimension to resolve ambiguity elsewhere.

Key achievements include:

  • Formal Integration: Successful mapping of graph-based semantic representations to Montague-style semantics and the Constraint Language for Lambda Structures (CLLS).
  • Disambiguation Power: Qualitative demonstration of how semantic dominance constraints resolve syntactic attachment ambiguities.
  • Efficiency: Despite the NP-complete nature of general XDG parsing, the constraint solver remains efficient for practical fragments due to the pruning power of multi-dimensional propagation.

Conclusion

While XDG offers a powerful relational interface, its computational complexity remains a challenge. Future work aims to identify polynomial-time fragments and scale the framework to broad-coverage grammars induced from large treebanks. By treating syntax and semantics as equal partners, XDG provides a robust foundation for bidirectional natural language processing.

Summary updated

Abstract

Ralph Debusmann, Denys Duchier, Alexander Koller, Marco Kuhlmann, Gert Smolka, Stefan Thater. COLING 2004: Proceedings of the 20th International Conference on Computational Linguistics. 2004.
BibTeX
@inproceedings{debusmann2004relational,
  author = {Ralph Debusmann and Denys Duchier and Alexander Koller and Marco Kuhlmann and Gert Smolka and Stefan Thater},
  title = {{A Relational Syntax-Semantics Interface Based on Dependency Grammar}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2004},
  url = {https://openreview.net/forum?id=UdEmpr_qlmb},
}
Figure