Generalized Augmented Transition Network Grammars for Generation from Semantic Networks

Stuart C. ShapiroACL 1979 · DOI

Introduction

In the late 1970s, Augmented Transition Networks (ATNs) were the established standard for natural language parsing—the process of converting linear sentences into structured data. However, using this same formalism for natural language generation remained a significant hurdle. Researchers typically maintained two separate systems: one to "understand" and another to "speak." Stuart C. Shapiro’s 1979 paper addresses this inefficiency by introducing a generalized ATN formalism that unifies parsing and generation within a single interpreter.

The Problem of Asymmetric Systems

The primary challenge in unifying these processes lies in the nature of the input. Parsing deals with a linear sequence of words where the next item is implicit. Conversely, generation begins with a complex semantic network where the next node to be processed must be explicitly selected from a web of connections. Previous generation attempts often relied on modified, inconsistent versions of ATNs, leading to redundant lexicons and fragmented architectures.

The Generalized ATN Formalism

Shapiro’s solution is to treat the input as a stack-based buffer, regardless of whether the system is reading a string of words or traversing a graph. This generalization allows the same logic to apply to both directions of translation. Key technical innovations include:

  • New Arc Types: The introduction of the CALL arc (a generalization of the standard PUSH arc) and the TO arc allows the grammar to explicitly specify which node in a semantic network should be examined next.
  • The GETA Form: A specialized function used to retrieve specific nodes (e.g., identifying the "AGENT" or "OBJECT" of a verb) to guide the generation process.
  • Input Buffer Management: The * register is redefined to point to the top of the input buffer. In generation, "consuming" an symbol entails moving from one node in the semantic network to another.
A unified parsing-generating grammar using the generalized ATN formalism.

Semantic Integration with SNePS

The system utilizes the Semantic Network Processing System (SNePS) for knowledge representation. By viewing the input as a stack, the system handles recursive calls elegantly. For instance, when the generator describes a complex noun phrase, it "pushes" the relevant nodes onto the stack, processes them, and then "pops" back to the primary sentence structure.

Semantic network representation of the sentence 'A dog kissed young Lucy'.

Key Insights and Results

The most profound insight of this work is the "symmetry of language": parsing and generation are two sides of the same coin. A grammar for one can often serve as a sub-network for the other. Shapiro demonstrated this by building a question-answering system where the parse of a question directly informed the generation of its answer.

Qualitative evaluations showed the system could:

  1. Parse statements and store them in a SNePS network.
  2. Parse questions, perform deductions to find answers, and generate natural language responses.
  3. Maintain linguistic consistency, such as responding in the same voice (active or passive) as the input question.

Conclusion and Future Work

While the system was tested on relatively simple "toy" examples and required manual grammar construction, it proved that a unified approach was computationally feasible. The generalized ATN provided a path toward more cohesive natural language interfaces, though scaling the system to the full complexity of human language remained a task for future research.

Summary updated

BibTeX
@inproceedings{shapiro1979generalized,
  author = {Stuart C. Shapiro},
  title = {{Generalized Augmented Transition Network Grammars for Generation from Semantic Networks}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1979},
  doi = {10.3115/982163.982171},
}
Figure