Semantic Expressive Capacity with Bounded Memory

Antoine Venant, Alexander Koller

Abstract

This research addresses a fundamental question in computational linguistics: how does the structural constraint of projectivity affect the memory requirements of a semantic parser? By analyzing the mapping from strings to semantic graphs, specifically focusing on cross-serial dependencies (CSD), we demonstrate that projective parsers with bounded memory are inherently less expressive than non-projective ones. This theoretical result has significant implications for the design of grammar-based and neural semantic parsers.

Introduction

Semantic parsing is the task of translating natural language sentences into formal semantic representations, such as graphs or lambda calculus terms. During the derivation process, parsers often utilize "placeholders" or variables to track arguments that have not yet been encountered in the sentence. Two primary paradigms exist for managing these placeholders: unbounded memory (e.g., Lambda Calculus) and bounded memory (e.g., unification-based systems like HPSG or AM-Algebra).

A key constraint in many parsing formalisms is projectivity, which requires that the parser only combines adjacent substrings. This paper investigates whether this structural constraint, when combined with bounded memory, limits the range of semantic relations a parser can represent.

The Bottleneck of Projectivity

Projectivity forces a parser to "carry" placeholders for long-distance dependencies through every intermediate step of a derivation. In sentences with overlapping dependencies, such as the cross-serial dependencies found in Swiss German, the number of active placeholders can grow with the complexity of the sentence.

Figure 1: Comparison of derivation structures for cross-serial dependencies in Swiss German.

As illustrated in Figure 1, the interleaved nature of objects and verbs in Swiss German (e.g., "d' chind em Hans es huus lönd hälfed aastriiche") presents a challenge for projective parsers. To maintain the correct semantic links, a projective parser must keep multiple placeholders active simultaneously. As the number of objects increases, a fixed-memory projective parser eventually runs out of available "slots."

Methodology: Comparing Grammar Formalisms

The authors employ formal language theory to compare two classes of grammars that are weakly equivalent at the string level but differ in their derivation processes:

  • Tree-Adjoining Grammars (TAG): These are non-projective and can "insert" content into the middle of an existing structure.
  • Linear Monadic Context-Free Tree Grammars (LM-CFTG): These are projective.

The semantic representations are modeled using Hyperedge Replacement (HR) algebra, a framework for constructing graphs. The study focuses on the Cross-Serial Dependency (CSD) relation, which serves as a "stress test" for memory capacity by mapping strings of the form $a^n b^m c^n d^m$ to specific semantic graphs.

Figure 3: Mapping between various grammar formalisms (TAG, projective trees) and semantic graph structures.

Figure 3 highlights the differences in how these formalisms handle the mapping to semantic graphs. While non-projective TAGs can represent the CSD relation using a small, fixed number of placeholders (sources), projective grammars require an increasing number of placeholders as the string length grows.

Theoretical Results

The core of the paper is a mathematical proof showing that projectivity is a semantic bottleneck:

  • Theorem 1: Under the assumption of alignment between words and graph edges, no projective grammar with a bounded number of sources can represent the CSD relation.
  • Theorem 2: This limitation holds even without the alignment assumption for LM-CFTGs.

These theorems establish that while TAG and LM-CFTG might generate the same sets of strings, they are not equivalent in their ability to map those strings to meanings under memory constraints. Projectivity fundamentally forces the parser to "remember" more things at once.

Practical Implications

These findings suggest that popular projective frameworks, such as Combinatory Categorial Grammar (CCG) or standard transition-based neural parsers, may be fundamentally limited in their expressive capacity compared to non-projective alternatives. Unless these systems adopt unbounded memory mechanisms (like lambda-style variables), they may be unable to represent certain complex semantic relations found in natural language.

Conclusion

This work provides the first formal proof regarding the expressive capacity of semantic relations under projectivity and memory constraints. It highlights a critical trade-off in parser design: the efficiency of projective parsing comes at the cost of semantic expressivity when memory is bounded. Future research should focus on bridging this gap, perhaps by developing hybrid mechanisms that combine the strengths of both paradigms.

Summary updated

Abstract

We investigate the capacity of mechanisms for compositional semantic parsing to describe relations between sentences and semantic representations. We prove that in order to represent certain relations, mechanisms which are syntactically projective must be able to remember an unbounded number of locations in the semantic representations, where nonprojective mechanisms need not. This is the first result of this kind, and has consequences both for grammar-based and for neural systems.
BibTeX
@inproceedings{venant2019semantic,
  author = {Antoine Venant and Alexander Koller},
  title = {{Semantic Expressive Capacity with Bounded Memory}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2019},
  doi = {10.18653/v1/p19-1008},
}
Figure