Abstract
This paper introduces s-graph grammars, a novel formalism designed to bridge the gap between classical, linguistically-grounded semantic construction and modern, data-driven graph parsing. By integrating Interpreted Regular Tree Grammars (IRTGs) with a specialized graph algebra, this approach allows for mapping natural language strings to complex semantic graphs, such as Abstract Meaning Representation (AMR), using rules that are both computationally efficient and linguistically interpretable.
Introduction
Computational semantics has increasingly moved toward graph-based representations like AMR to capture sentence meaning. While these "sembanks" are effective for training statistical parsers, a disconnect remains between modern data-driven methods and decades of linguistic research. Current statistical parsers often utilize Hyperedge Replacement Grammars (HRGs), which, while powerful, are difficult to reconcile with linguistic concepts like thematic roles (e.g., subject or object). Conversely, classical Montague Grammar relies on lambda calculus, which does not naturally produce the graph structures found in modern corpora. This work proposes s-graph grammars as a middle ground: a formalism that is learnable from data yet remains transparent to linguists.
Methods: The Algebra of s-graphs
The s-graph grammar framework is built upon two pillars: Interpreted Regular Tree Grammars (IRTGs) and the Algebra of s-graphs (HR Algebra). In this synchronous framework, a single derivation tree is simultaneously interpreted into multiple formats—typically a string (the sentence) and a graph (the meaning).
Unlike abstract hyperedges in standard HRGs, s-graph grammars use "source names" (e.g., subj, obj, or root) to mark specific nodes. These names serve as "hooks" for combining graph fragments. The grammar employs three primary operations to build graphs bottom-up:
- Merge (||): Fuses two graphs by joining nodes with identical source names.
- Rename: Alters a source name to facilitate new attachments (e.g., turning a
rootinto asubj). - Forget: Removes a source name once an argument position is filled, preventing further incorrect attachments.
Key Insights and Formal Properties
A central advantage of s-graph grammars is their linguistic interpretability. Persistent, meaningful names for argument positions allow for straightforward modeling of complex phenomena like control verbs, where one entity fills multiple roles. Furthermore, the bottom-up construction mirrors classical compositional theories of meaning.
Crucially, the author establishes the formal equivalence between s-graph grammars and HRGs. This ensures that the linguistic clarity of named sources does not come at the cost of computational tractability. The parsing complexity for these grammars is $O((n \cdot 3^d)^s \cdot ds)$, where $n$ is the number of nodes, $d$ is the maximum degree, and $s$ is the number of sources, matching known HRG benchmarks.
Results and Applications
The paper demonstrates the versatility of s-graph grammars through several linguistic case studies, including complements, control and raising, and modifiers. By showing how a single underlying structure can map to different surface realizations, the framework proves its utility for cross-linguistic semantic modeling.
While the current work focuses on theoretical foundations, it is designed for compatibility with large-scale annotated corpora such as AMR-Bank, the SemEval 2014 Shared Task, and the Groningen Meaning Bank.
Conclusion and Future Work
S-graph grammars provide a robust theoretical framework for semantic construction. However, empirical evaluation on large datasets remains a primary area for future research. Subsequent work will focus on the automatic induction of these grammars from existing sembanks and the development of statistical parsing models to handle natural language ambiguity.
Summary updated