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.
Introduction
Semantic parsing—the task of translating natural language into formal representations like graphs or logic formulas—often relies on compositional mechanisms. These systems build meaning step-by-step based on a sentence's syntax. A long-standing intuition in linguistics suggests a trade-off between syntactic structure (projectivity) and the "memory" (placeholders) required to maintain semantic coherence.
This paper provides a formal theoretical foundation for this intuition. The authors demonstrate that "projective" parsers, which only combine adjacent words, require an unbounded number of placeholders to represent complex linguistic relations. Consequently, popular "bounded memory" systems, such as those based on unification or fixed-size graph algebras, are fundamentally less expressive than non-projective systems or those utilizing lambda calculus.
The Projectivity-Memory Trade-off
Two major design choices define semantic parsers:
- Projectivity: Whether the parser combines only adjacent substrings (projective) or can skip around (non-projective).
- Memory (Placeholders): How the parser handles arguments that haven't appeared yet. Some systems allow infinite placeholders (e.g., lambda calculus), while others (e.g., HR graph algebras) assume a fixed, bounded number.
The authors investigate whether restricting a parser to be both projective and memory-bounded limits its expressivity. While linguists have suspected this, particularly regarding "cross-serial dependencies" (CSD) in languages like Swiss German, this work provides the first formal proof of this gap.
Methods and Formalisms
The study compares two classes of grammars that generate the same set of strings but differ in their structural derivations:
- Tree Adjoining Grammars (TAG): A non-projective formalism.
- Linear Monadic Context-Free Tree Grammars (LM-CFTG): A projective formalism.
The authors evaluate these grammars on their string-graph relations using the Hyperedge Replacement (HR) graph algebra. To prove the expressive gap, they define the CSD Relation, a synthetic dataset mapping strings to graphs where dependencies cross, forcing projective parsers to maintain multiple "open" placeholders.
The CSD Relation and the Pumping Lemma
The core of the proof involves showing that a projective grammar eventually "runs out of memory" as the sentence length increases. The authors use a pumping lemma to demonstrate that for any fixed number of sources (memory slots), there exists a CSD relation that the projective grammar cannot generate.
Key Results
The theoretical findings are summarized in two primary theorems:
- Theorem 1: Projective grammars with a fixed number of sources ($k$) cannot represent the CSD relation if tokens and edges are aligned.
- Theorem 2: Even without alignment assumptions, projective LM-CFTGs cannot simulate non-projective TAGs with only two sources for the CSD relation.
The "Aha" moment of the research is that a TAG with only two sources is more semantically expressive than a projective grammar with any fixed number of sources $k$.
Discussion and Impact
This "projectivity tax" implies that if a system insists on projective syntax, it must pay in semantic memory. This has significant implications for neural parsers. Many transition-based models are projective (using a stack and buffer); this research suggests such models may be fundamentally unable to capture certain semantic structures without incorporating non-projective "jump" actions or more flexible semantic algebras.
While the CSD relation is a mathematical construction, it mirrors real-world phenomena. Empirical work on AMRBank and Geoquery suggests that roughly 37% of Abstract Meaning Representation (AMR) data requires non-projective derivations, highlighting the practical relevance of these theoretical bounds. Future work may explore how bounded systems can be adapted to regain expressivity without sacrificing computational efficiency.
Summary updated